Supersaturation of even linear cycles in linear hypergraphs

DOI10.1017/S0963548320000206MaRDI QIDQ4987256zbMATH OpenFDO

Authors Tao Jiang, L. Yepremyan

Publication date 30 April 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.03091

zbMATH Keywords

bicliquesupersaturation problemsTurán problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: A classic result of ErdH{o}s and, independently, of Bondy and Simonovits says that the maximum number of edges in an $n$-vertex graph not containing $C_{2k}$, the cycle of length $2k$, is $O(n^{1+1/k})$. Simonovits established a corresponding supersaturation result for $C_{2k}$'s, showing that there exist positive constants $C,c$ depending only on $k$ such that every $n$-vertex graph $G$ with $e(G)geqC{n}^{1+1/k}$ contains at least $cleft(frace(G)v(G)ight{)}^{2k}$ many copies of $C_{2k}$, this number of copies tightly achieved by the random graph (up to a multiplicative constant). In this paper, we extend Simonovits' result to a supersaturation result of $r$-uniform linear cycles of even length in $r$-uniform linear hypergraphs. Our proof is self-contained and includes the $r=2$ case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest.

Recommendations

• The number of hypergraphs without linear cycles
• Balanced supersaturation for some degenerate hypergraphs
• Hypergraph Turán numbers of linear cycles
• Supersaturated graphs and hypergraphs
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3885945 (Why is no real title available?)
• scientific article; zbMATH DE number 3900799 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3333193 (Why is no real title available?)
• A correlation inequality for bipartite graphs
• A note on the Turán function of even cycles
• An existence theory for pairwise balanced designs. I: Composition theorems and morphisms
• An existence theory for pairwise balanced designs. II: Structure of PBD- closed sets and the existence conjectures
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
• Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
• Cycles of even length in graphs
• Erratum For ‘A Bound on the Number of Edges in Graphs Without an Even Cycle’
• Hypergraph Turán numbers of linear cycles
• Inequalities for functionals generated by bipartite graphs
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• On a class of degenerate extremal graph problems
• On a packing and covering problem
• On arithmetic progressions of cycle lengths in graphs
• On the existence of triangulated spheres in 3-graphs, and related problems
• On the structure of linear graphs
• Supersaturated graphs and hypergraphs
• The history of degenerate (bipartite) extremal graph problems
• The number of \(C_{2\ell}\)-free graphs
• The number of hypergraphs without linear cycles
• Turán problems and shadows. I: Paths and cycles

Cited in

(9)

• On the number of linear hypergraphs of large girth
• On Turán exponents of bipartite graphs
• Turán numbers of bipartite subdivisions
• Linearity of saturation for Berge hypergraphs
• The number of hypergraphs without linear cycles
• On the Turán number of the hypercube
• Balanced supersaturation for some degenerate hypergraphs
• Hypergraphs with no tight cycles
• Turán theorems for even cycles in random hypergraph

This page was built for publication: Supersaturation of even linear cycles in linear hypergraphs

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