On the number of linear hypergraphs of large girth
On the number of linear hypergraphs of large girth
复制标题
DOI：
10.1002/jgt.22477
复制
发表时间：
2017-09
影响因子：
0.9
通讯作者：
J. Balogh;Lina Li
中科院分区：
文献类型：
--
作者：
J. Balogh;Lina Li
长度为ℓ的r-一致线性圈，记为Cℓr，是一个边为e 1，…的r-图，eℓ使得对于每个i∈[ℓ−1]，|e i∩e i+1|=1，|eℓ∩e 1|=1，并且对于所有其他对{i，j}，e i∩e j=∅，i≠j。对于任意的r≥3和ℓ≥4，我们证明了存在一个依赖于r和ℓ的常数C，使得围长ℓ的线性r图的个数至多为2Cn1+1/⌊ℓ/2⌋.进一步推广了ℓ=4的结果，证明了存在依赖于r的常数C，使得不含C4r的线性r-图的个数至多为2Cn3/2。证明的思想是将超图计数问题归结为一些图计数问题，然后应用图容器方法的变体，这可能是独立感兴趣的。推广了Kleitman和Winston关于无C4图的个数的一个突破性结果，证明了对于足够大的n，至多包含n2/32log6nC4‘S的图的个数至多为211n3/2，进一步证明了对于任意的r≥3和ℓ≥2，每个边都只包含在长度不超过2ℓ的O(1)圈中的图的个数渐近有界于2 3(ℓ+1)n1+1/ℓ.
An r ‐uniform linear cycle of length ℓ , denoted by C ℓ r , is an r ‐graph with edges e 1 , … , e ℓ such that for every i ∈ [ ℓ − 1 ] , ∣ e i ∩ e i + 1 ∣ = 1 , ∣ e ℓ ∩ e 1 ∣ = 1 , and e i ∩ e j = ∅ 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 ℓ such that the number of linear r ‐graphs of girth ℓ is at most 2 C n 1 + 1 ∕ ⌊ ℓ ∕ 2 ⌋ . Furthermore, we extend the result for ℓ = 4 , proving that there exists a constant C depending on r such that the number of linear r ‐graphs without C 4 r is at most 2 C n 3 ∕ 2 . 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 C 4 ‐free graphs, proving that the number of graphs containing at most n 2 ∕ 32 log 6 n C 4 's is at most 2 11 n 3 ∕ 2 , 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 2 ℓ , is bounded by 2 3 ( ℓ + 1 ) n 1 + 1 ∕ ℓ asymptotically.