2025/11/07 by Tian, Fang, Yang, Yiting, Yuan, Xiying
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Digital Image Processing Techniques
paper · doi:10.48550/arxiv.2511.04978
For an integer r\geqslant 3, a hypergraph on vertex set [n] is r-uniform if each edge is a set of r vertices, and is said to be linear if every two distinct edges share at most one vertex. Given a family H of linear r-uniform hypergraphs,let ForbrL(n,H) be the set of linear r-uniform hypergraphs on vertex set [n], which does not contain any member from H as a subgraph. An r-uniform linear cycle of length ℓ, denoted by C_ℓr, is a linear r-uniform hypergraph on (r-1)ℓ vertices whose edges can be ordered as \boldsymbole1,…,\boldsymbole_ℓ such that |\boldsymbolei∩ \boldsymbolej|=1 if j=i± 1 (indices taken modulo ℓ) and |\boldsymbolei∩ \boldsymbolej|=0 otherwise. The linear girth of a linear r-uniform hypergraph is the smallest integer ℓ such that it contains a C_ℓr. Let ForbL(n,r,ℓ)=ForbrL(n,H) when H=\Cir: 3\leqslant i\leqslant ℓ\, that is, ForbL(n,r,ℓ) is the set of all linear r-uniform hypergraphs on [n] with linear girth greater than ℓ. For integers r\geqslant 3 and ℓ\geqslant 4, Balogh and Li [On the number of linear hypergraphs of large girth, J. Graph Theory, 93(1) (2020), 113-141] showed that |ForbL(n,r,ℓ)|= 2^O(n1+1/\lfloor ℓ/2\rfloor) based on the graph container method. It is natural to obtain |ForbL(n,r,ℓ)|\geqslant 2^c⋅ n1+1/ℓ for some constant c by probabilistic deletion method. Combined with the known results that |ForbL(n,r,3)|= 2^o (n2) and |ForbL(n,3,4)|= 2^Θ(n3/2), by analyzing the random greedy high linear girth linear r-uniform hypergraph process, we show |ForbL(n,r,ℓ)|\geqslant 2^n1+1/(ℓ-1)-O(loglog n/log n) for every pair of fixed integers r,ℓ\geqslant 4, or r= 3 and ℓ\geqslant 5.