Generalized Turán problems for even cycles

DOI10.1016/J.JCTB.2020.05.005zbMath1448.05107arXiv1712.07079OpenAlexW2988745151MaRDI QIDQ2200921

Abhishek Methuku, Dániel Gerbner, Máté Vizer, Ervin Gyoeri

Publication date: 24 September 2020

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

Abstract: Given a graph $H$ and a set of graphs $mathcalF$, let $ex(n,H,mathcalF)$ denote the maximum possible number of copies of $H$ in an $mathcalF$-free graph on $n$ vertices. We investigate the function $ex(n,H,mathcalF)$, when $H$ and members of $mathcalF$ are cycles. Let $C_k$ denote the cycle of length $k$ and let $mathscr{C}_k=C_3,C_4,ldots,C_k$. Some of our main results are the following. (i) We show that $ex(n,C_{2l},C_{2k})=Theta(n^l)$ for any $l,kge2$. Moreover, we determine it asymptotically in the following cases: We show that $ex(n,C_4,C_{2k})=(1+o(1))frac(k-1)(k-2)4n^2$ and that the maximum possible number of $C_6$'s in a $C_8$-free bipartite graph is $n^3+O(n^{5/2})$. (ii) Solymosi and Wong proved that if ErdH{o}s's Girth Conjecture holds, then for any $lge3$ we have $ex(n,C_{2l},mathscr{C}_{2l-1})=Theta(n^{2l/(l-1)})$. We prove that forbidding any other even cycle decreases the number of $C_{2l}$'s significantly: For any $k>l$, we have $ex(n,C_{2l},mathscr{C}_{2l-1}cup{C}_{2k})=Theta(n^2).$ More generally, we show that for any $k>l$ and $mge2$ such that $2keqml$, we have $ex(n,C_{ml},mathscr{C}_{2l-1}cup{C}_{2k})=Theta(n^m).$ (iii) We prove $ex(n,C_{2l+1},mathscr{C}_{2l})=Theta(n^{2+1/l}),$ provided a strong version of ErdH{o}s's Girth Conjecture holds (which is known to be true when $l=2,3,5$). Moreover, forbidding one more cycle decreases the number of $C_{2l+1}$'s significantly: More precisely, we have $ex(n,C_{2l+1},mathscr{C}_{2l}cup{C}_{2k})=O(n^{2-frac1l+1}),$ and $ex(n,C_{2l+1},mathscr{C}_{2l}cup{C}_{2k+1})=O(n^2)$ for $l>kge2$. (iv) We also study the maximum number of paths of given length in a $C_k$-free graph, and prove asymptotically sharp bounds in some cases.

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

zbMATH Keywords

cyclesTurán numbersextremal graph theoryErdős girth conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On regular hypergraphs of high girth
• 3-uniform hypergraphs avoiding a given odd cycle
• On 3-uniform hypergraphs without a cycle of a given length
• Cycles in graphs of fixed girth with large size
• On the maximum number of five-cycles in a triangle-free graph
• Pentagons vs. triangles
• Cycle lengths in sparse graphs
• The spectral radius of graphs without paths and cycles of specified length
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Polarities and \(2k\)-cycle-free graphs
• The Moore bound for irregular graphs
• Cycles of even length in graphs
• On the number of pentagons in triangle-free graphs
• Some sharp results on the generalized Turán numbers
• Generalized Turán problems for disjoint copies of graphs
• A spectral condition for odd cycles in graphs
• The Maximum Number of Triangles in C_2k+1-Free Graphs
• Hypergraphs with No Cycle of a Given Length
• Extremal problems for cycles in graphs
• Über ein Problem von K. Zarankiewicz
• On maximal paths and circuits of graphs
• On a Probabilistic Graph-Theoretical Method
• On the Number of Cycles in a Graph with Restricted Cycle Lengths
• A note on the maximum number of triangles in a C₅‐free graph
• The maximum number of $P_\ell$ copies in $P_k$-free graphs
• A generalized Turán problem and its applications
• Extremal Results for Berge Hypergraphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Minimal Regular Graphs of Girths Eight and Twelve
• On Graphs that do not Contain a Thomsen Graph
• Many \(T\) copies in \(H\)-free graphs

Related Items (38)

Tree densities in sparse graph classes ⋮ Some exact results for generalized Turán problems ⋮ Spectral radius, edge-disjoint cycles and cycles of the same length ⋮ Generalized rainbow Turán problems ⋮ Generalized Turán number for linear forests ⋮ The Generalized Rainbow Turán Problem for Cycles ⋮ On generalized Turán number of two disjoint cliques ⋮ Some extremal results on hypergraph Turán problems ⋮ The maximum number of paths of length four in a planar graph ⋮ Generalized planar Turán numbers ⋮ Generalized rainbow Turán numbers of odd cycles ⋮ Unnamed Item ⋮ The maximum number of triangles in \(F_k\)-free graphs ⋮ Triangles in C5‐free graphs and hypergraphs of girth six ⋮ On the maximum number of odd cycles in graphs without smaller odd cycles ⋮ The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number ⋮ The cycle of length four is strictly \(F\)-Turán-good ⋮ Rainbow Turán problem for even cycles ⋮ Generalized Turán problems for \(K_{2,t}\) ⋮ Some exact results of the generalized Turán numbers for paths ⋮ $t$-Wise Berge and $t$-Heavy Hypergraphs ⋮ The maximum number of copies of \(K_{r,s}\) in graphs without long cycles or paths ⋮ Some sharp results on the generalized Turán numbers ⋮ On Turán-good graphs ⋮ On extremal values of some degree-based topological indices with a forbidden or a prescribed subgraph ⋮ Many H-Copies in Graphs with a Forbidden Tree ⋮ Some results on \(k\)-Turán-good graphs ⋮ The constructor-blocker game ⋮ Many triangles in \(C_5\)-free graphs ⋮ Generalized Turán number of even linear forests ⋮ On the generalized Turán problem for odd cycles ⋮ On generalized Turán numbers of intersecting cliques ⋮ Maximizing five-cycles in \(K_r\)-free graphs ⋮ Generalized Turán problems for complete bipartite graphs ⋮ \(C_{2k}\)-saturated graphs with no short odd cycles ⋮ Generalized Turán densities in the hypercube ⋮ Further results on the generalized Turán number of spanning linear forests ⋮ The generalized Turán number of spanning linear forests

This page was built for publication: Generalized Turán problems for even cycles