The number of hypergraphs without linear cycles

DOI10.1016/J.JCTB.2018.07.003MaRDI QIDQ1633760zbMATH OpenOpenAlexWikidataFDO

Authors József Balogh, J. Skokan, Bhargav P. Narayanan

Publication date 20 December 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.01207, http://eprints.lse.ac.uk/88952/1/Skokan_Linear%20Cycles_Accepted.pdf

zbMATH Keywords

asymptotic enumerationbalanced supersaturation

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Hypergraphs (05C65)

Abstract: The $r$-uniform linear $k$-cycle $C_k^r$ is the $r$-uniform hypergraph on $k(r-1)$ vertices whose edges are sets of $r$ consecutive vertices in a cyclic ordering of the vertex set chosen in such a way that every pair of consecutive edges share exactly one vertex. Here, we prove a balanced supersaturation result for linear cycles which we then use in conjunction with the method of hypergraph containers to show that for any fixed pair of integers $r,kge3$, the number of $C_k^r$-free $r$-uniform hypergraphs on $n$ vertices is $2^{Theta(n^{r-1})}$, thereby settling a conjecture due to Mubayi and Wang.

Recommendations

• On the number of linear hypergraphs of large girth
• Hypergraph Turán numbers of linear cycles
• Supersaturation of even linear cycles in linear hypergraphs
• Some findings on \(r\)-uniform hypergraph of order \(n\) which contains no \(k\)-C-cycle
• On hypergraphs without loose cycles

Cites work

• Asymptotic enumeration, global structure, and constrained evolution
• scientific article; zbMATH DE number 5130822 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• Hypergraph containers
• Hypergraph Turán numbers of linear cycles
• Independent sets in hypergraphs
• On hypergraphs without loose cycles
• On the number of graphs without 4-cycles
• On the number of linear hypergraphs of large girth
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The number of \(C_{2\ell}\)-free graphs
• The number of \(K_{m,m}\)-free graphs
• The number of \(K_{s,t}\)-free graphs
• The number of triple systems without even cycles
• Turán problems and shadows. I: Paths and cycles

Cited in

(22)

• On hypergraphs without loose cycles
• A note on the linear cycle cover conjecture of Gyárfás and Sárközy
• The structure of hypergraphs without long Berge cycles
• Triangle-free subgraphs of hypergraphs
• Asymptotic Turán number for linear 5-cycle in 3-uniform linear hypergraphs
• Counting \(r\)-graphs without forbidden configurations
• Hypergraph Turán numbers of linear cycles
• Jumps in speeds of hereditary properties in finite relational languages
• Some findings on \(r\)-uniform hypergraph of order \(n\) which contains no \(k\)-C-cycle
• Supersaturation of even linear cycles in linear hypergraphs
• Large hypergraphs without tight cycles
• Hypergraphs with no tight cycles
• On the number of linear hypergraphs of large girth
• C-cycles in hypergraphs
• Balanced supersaturation for some degenerate hypergraphs
• Counting hypergraphs with large girth
• Turán theorems for even cycles in random hypergraph
• On the number of \(\mathcal{H}\)-free hypergraphs
• Counting independent sets in percolated graphs via the Ising model
• On the random Turán number of linear cycles
• Random Turán theorem for expansions of spanning subgraphs of tight trees
• Supersaturation of odd linear cycles

This page was built for publication: The number of hypergraphs without linear cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633760)