Supersaturation of even linear cycles in linear hypergraphs

DOI10.1017/S0963548320000206zbMATH Open1462.05265arXiv1707.03091MaRDI QIDQ4987256FDOQ4987256

Authors: Tao Jiang, L. Yepremyan 

Publication date: 30 April 2021

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

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.

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

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

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)

Cites Work

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

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)