On high-girth layered graphs of large Turán density in a hypercube
Abstract
For a graph H, let ex(Qn, H) be the largest number of edges in a subgraph of the hypercube Qn of dimension n that contains no subgraph isomorphic to H. We define π□(H)=limn→∞ex(Qn,H)/|E(Qn)| as the Turán density of H in the hypercube. Although determining π□(H) for general H remains widely open, Conlon found a large class of graphs with zero Turán density in a hypercube. In this note, we address the case when π□ (H)>0. If a graph H cannot be embedded in an edge layer of a hypercube, then π□ (H)≥ 1/2, as can be seen by taking every other edge layer of Qn. Previously known examples of layered graphs of positive Turán density in a hypercube include graphs containing cycles of length $6$ or $10$, as well as examples of girth $8$. Also, to the best of our knowledge, all previously known examples of graphs with Turán densities arbitrarily close to one are not layered. We show that for every g ≥ 3, there are layered graphs of girth greater than g whose Turán densities in a hypercube are arbitrarily close to one. Moreover, these graphs have an induced embedding into an edge layer of a hypercube.
Related
- On the structure of graphs with given odd girth and large algebraic connectivity
- Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
- Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
- Unbalanced distance-biregular graphs with girth deficiency two
- Proper conflict-free choosability of sparse graphs with girth at least seven
BibTeX
@misc{axenovich2026highgirth,
title = {{On high-girth layered graphs of large Turán density in a hypercube}},
author = {Maria Axenovich and Marko Pejić},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.30544},
eprint = {2608.30544},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30544},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On high-girth layered graphs of large Turán density in a hypercube
AU - Maria Axenovich
AU - Marko Pejić
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2608.30544
UR - https://arxiv.org/abs/2608.30544
AB - For a graph H, let ex(Q_n, H) be the largest number of edges in a subgraph of the hypercube Q_n of dimension n that contains no subgraph isomorphic to H. We define π_□(H)=lim_n→∞ex(Q_n,H)/|E(Q_n)| as the Turán density of H in the hypercube. Although determining π_□(H) for general H remains widely open, Conlon found a large class of graphs with zero Turán density in a hypercube. In this note, we address the case when π_□ (H)>0. If a graph H cannot be embedded in an edge layer of a hypercube, then π_□ (H)≥ 1/2, as can be seen by taking every other edge layer of Q_n. Previously known examples of layered graphs of positive Turán density in a hypercube include graphs containing cycles of length $6$ or $10$, as well as examples of girth $8$. Also, to the best of our knowledge, all previously known examples of graphs with Turán densities arbitrarily close to one are not layered. We show that for every g ≥ 3, there are layered graphs of girth greater than g whose Turán densities in a hypercube are arbitrarily close to one. Moreover, these graphs have an induced embedding into an edge layer of a hypercube.
ER -