























A graph is cubical if it is a subgraph of a hypercube. For a cubical graph $H$ and a hypercube $Q_n$, $ex(Q_n, H)$ is the largest number of edges in an $H$-free subgraph of $Q_n$. If $ex(Q_n, H)$ is at least a positive proportion of the number of edges in $Q_n$, $H$ is said to have a positive Turán density in a hypercube or simply a positive Turán density; otherwise it has a zero Turán density. Determining $ex(Q_n, H)$ and even identifying whether $H$ has a positive or a zero Turán density remains a widely open question for general $H$. By relating extremal numbers in a hypercube and certain corresponding hypergraphs, Conlon found a large class of cubical graphs, ones having so-called partite representation, that have a zero Turán density. He raised a question whether this gives a characterisation, i.e., whether a cubical graph has zero Turán density if and only if it has partite representation. Here, we show that, as suspected by Conlon, this is not the case. We give an example of a class of cubical graphs which have no partite representation, but on the other hand, have a zero Turán density. In addition, we show that any graph whose every block has partite representation has a zero Turán density in a hypercube.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。