A class of graphs of zero Turán density in a hypercube
Open Access
- 5 March 2024
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 33 (3) , 404-410
Abstract
For a graph $H$ and a hypercube $Q_n$ , $\textrm{ex}(Q_n, H)$ is the largest number of edges in an $H$ -free subgraph of $Q_n$ . If $\lim _{n \rightarrow \infty } \textrm{ex}(Q_n, H)/|E(Q_n)| \gt 0$ , $H$ is said to have a positive Turán density in a hypercube or simply a positive Turán density; otherwise, it has zero Turán density. Determining $\textrm{ex}(Q_n, H)$ and even identifying whether $H$ has a positive or 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 graphs, ones having so-called partite representation, that have zero Turán density. He asked whether this gives a characterisation, that is, whether a 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 graphs which have no partite representation, but on the other hand, have zero Turán density. In addition, we show that any graph whose every block has partite representation has zero Turán density in a hypercube.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Extremal numbers for cycles in a hypercubeDiscrete Applied Mathematics, 2023
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercubeEuropean Journal of Combinatorics, 2014
- On even-cycle-free subgraphs of the hypercubeJournal of Combinatorial Theory, Series A, 2011
- On even-cycle-free subgraphs of the hypercubeElectronic Notes in Discrete Mathematics, 2009
- Bounding the size of square-free subgraphs of the hypercubeDiscrete Mathematics, 2009
- Some Turán type results on the hypercubeDiscrete Mathematics, 2008
- On the maximum number of edges in a c4‐free subgraph of qnJournal of Graph Theory, 1995
- Hexagon‐free subgraphs of hypercubesJournal of Graph Theory, 1993
- Subgraphs of a hypercube containing no small even cyclesJournal of Graph Theory, 1992
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964