TY - JOUR

T1 - On the number of linear hypergraphs of large girth

AU - Balogh, József

AU - Li, Lina

N1 - Funding Information:
The first author is partially supported by NSF Grant DMS-1500121, the Arnold O. Beckman Research Award (UIUC Campus Research Board 15006), and the Langan Scholor Fund (UIUC). Work was done while the first author was a Visiting Fellow Commoner at Trinity College, Cambridge.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - An r-uniform linear cycle of length l, denoted by Cr l, is an r-graph with edges e1…el such that for every i ∈ [ℓ − 1], ∣ei ∩ ei+1| = 1, |eℓ ∩ e1| = 1, and ei ∩ ej = ∅ for all other pairs {i, j}, i ≠ j. For every r ≥ 3 and ℓ ≥ 4, we show that there exists a constant C depending on r and l such that the number of linear r-graphs of girth l is at most (Formula presented.). Furthermore, we extend the result for l=4, proving that there exists a constant C depending on r such that the number of linear r -graphs without Cr 4 is at most (Formula presented.). The idea of the proof is to reduce the hypergraph enumeration problems to some graph enumeration problems, and then apply a variant of the graph container method, which may be of independent interest. We extend a breakthrough result of Kleitman and Winston on the number of C4 -free graphs, proving that the number of graphs containing at most n2 32 log6 n C4's is at most (Formula presented.), for sufficiently large n. We further show that for every r ≥ 3 and ℓ ≥ 2, the number of graphs such that each of its edges is contained in only O(1) cycles of length at most 2l, is bounded by (Formula presented.) asymptotically.

AB - An r-uniform linear cycle of length l, denoted by Cr l, is an r-graph with edges e1…el such that for every i ∈ [ℓ − 1], ∣ei ∩ ei+1| = 1, |eℓ ∩ e1| = 1, and ei ∩ ej = ∅ for all other pairs {i, j}, i ≠ j. For every r ≥ 3 and ℓ ≥ 4, we show that there exists a constant C depending on r and l such that the number of linear r-graphs of girth l is at most (Formula presented.). Furthermore, we extend the result for l=4, proving that there exists a constant C depending on r such that the number of linear r -graphs without Cr 4 is at most (Formula presented.). The idea of the proof is to reduce the hypergraph enumeration problems to some graph enumeration problems, and then apply a variant of the graph container method, which may be of independent interest. We extend a breakthrough result of Kleitman and Winston on the number of C4 -free graphs, proving that the number of graphs containing at most n2 32 log6 n C4's is at most (Formula presented.), for sufficiently large n. We further show that for every r ≥ 3 and ℓ ≥ 2, the number of graphs such that each of its edges is contained in only O(1) cycles of length at most 2l, is bounded by (Formula presented.) asymptotically.

KW - girth

KW - linear cycles

KW - linear hypergraphs

KW - the graph container method

UR - http://www.scopus.com/inward/record.url?scp=85075224225&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075224225&partnerID=8YFLogxK

U2 - 10.1002/jgt.22477

DO - 10.1002/jgt.22477

M3 - Article

AN - SCOPUS:85075224225

VL - 93

SP - 113

EP - 141

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -