2023/08/22 by Maria Axenovich, Axenovich, Maria
Mathematics · Computer Science · #Graph theory and applications #Interconnection Networks and Systems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2308.11366
A graph is cubical if it is a subgraph of a hypercube. For a cubical graph H and a hypercube Qn, ex(Qn, H) is the largest number of edges in an H-free subgraph of Qn. If ex(Qn, H) is at least a positive proportion of the number of edges in Qn, 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(Qn, 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.