Source-linked AI summary
The maximum number of cliques in graphs without long cycles
Ruth Luo
TL;DR
The paper asks how many s-cliques can occur in graphs with circumference less than k or with no path on k vertices. It extends Kopylov’s result to clique counts, showing that the edge-extremal examples also maximize fixed-size clique counts, and gives a bound for the path-free case.
Problem
The paper addresses the extremal number of s-cliques in graphs with circumference less than k and in graphs with no path on k vertices.
Source: §1 · p. 3Method
It generalizes Kopylov’s result to clique counts and uses a Kopylov-style argument for the path-free bound.
Source: §1 · p. 3Results
For circumference less than k, the 2-connected bound is max{f_s(n, k, 2), f_s(n, k, t)}; for connected P_k-free graphs it is max{f_s(n, k − 1, 1), f_s(n, k − 1, t)}.
Source: §1 · p. 3Takeaways & Limitations
The edge-extremal examples for 2-connected graphs with circumference less than k also maximize the number of cliques of any fixed size.
Source: §1 · p. 3
Abstract
from arXiv · showhide
The Erd\H{o}s--Gallai Theorem states that for $k\geq 3$ every graph on $n$ vertices with more than $\frac{1}{2}(k-1)(n-1)$ edges contains a cycle of length at least $k$. Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples $H_{n,k,t}$ and $H_{n,k,2}$. In this note, we generalize the result of Kopylov to bound the number of $s$-cliques in a graph with circumference less than $k$. Furthermore, we show that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, we obtain the extremal number of $s$-cliques in a graph with no path on $k$-vertices.
1 Introduction
The paper extends extremal graph results from edge counts to counts of s-cliques in graphs with bounded circumference, and also treats graphs with no path on k vertices. For 2-connected graphs, the edge-extremal examples also maximize clique counts of every fixed size.
1 Introduction
- Generalized Turán results for graphs can support related hypergraph extremal bounds; the introduction cites cycle-free triangle bounds used for Berge-cycle questions.The cited example is due to Fürédi and Özkahya.Source: §1 · p. 3
- The paper also gives an s-clique bound for graphs with circumference less than k, extending the result beyond the 2-connected setting.Source: §1 · p. 3
- The same extremal examples that maximize edges among 2-connected graphs with circumference less than k also maximize cliques of every fixed size.Source: §1 · p. 3
- For 2-connected n-vertex graphs with circumference less than k, N_s(G) ≤ max{f_s(n, k, 2), f_s(n, k, t)}, where t = ⌊(k − 1)/2⌋.The bound is sharp for H_n,k,2 and H_n,k,t.Source: §1 · p. 3
- For connected n-vertex graphs with no path on k vertices, N_s(G) ≤ max{f_s(n, k − 1, 1), f_s(n, k − 1, t)}, where t = ⌊(k − 2)/2⌋.The stated sharpness examples are H_n,k−1,1 and H_n,k−1,t.Source: §1 · p. 3
- The disconnected path-free result follows by induction on components and uses the same extremal examples as the edge result for P_k-free graphs.Source: §1 · pp. 1, 3
2 Proof of Theorem 1.4
The proof builds a nonempty high-minimum-degree core by disintegration, then uses its structure and long paths to rule out a counterexample.
2 Proof of Theorem 1.4
- An edge-maximal counterexample is k-closed, so every nonadjacent vertex pair has a path of at least k −1 edges between them.The proof uses this property to select long paths between nonadjacent pairs in the core.Source: §2 · p. 4
- Repeatedly deleting vertices of degree at most α produces the unique (α + 1)-core, which is the proof's tool for finding a large core.The core is empty or has minimum degree at least α+1.Source: §2 · p. 4
- The (t + 1)-core is nonempty; otherwise, the disintegration process would bound the number of cliques removed and contradict the counterexample assumption.The supplied proof passages state that deletions remove at most a bounded number of copies of K_s, though the bound is incomplete in the text.Source: §2 · p. 4
- The core H(G, t) is complete, since a nonedge would yield a long path whose endpoint degrees force a cycle of length at least k.The path argument uses Kopylov's lemma, which bounds the cycle length below by the minimum of the path length plus one and the sum of endpoint degrees on the path.Source: §2 · pp. 4–5
- Writing r for the core's order gives t + 2 ≤ r ≤ k − 2; further disintegration then creates a nonedge whose long path forces a cycle of length at least k.The upper bound follows because a core clique of order at least k−1 could be extended to a cycle of length at least k.Source: §2 · p. 5
3 Proof of Corollary 1.5, Theorem 1.6, and Corollary 1.7
For graphs with circumference less than k, the proof bounds the number of s-cliques by g_s(n,k), using a 2-connected bound and induction over blocks. It also derives path-free bounds through a dominating vertex and disintegration, then handles disconnected graphs and k=3 separately.
Proof of Corollary 1.5
- g_s(n, k) ≥ max{f_s(n, k, t), f_s(n, k, 2)}.This comparison is stated as part of the proof of Corollary 1.5.Source: §3 · p. 5
Proof for circumference less than k
- N_s(G) ≤ g_s(n, k) for a 2-connected graph with circumference less than k, by Theorem 1.4 when n ≥ k.For a connected graph with n ≤ k − 1, the proof also establishes the bound directly.Source: §3 · p. 5
- The block-cut tree splits the graph at a cut vertex, giving N_s(G) = N_s(B1) + N_s(B2) ≤ g_s(|B1|, k) + g_s(n − |B1| + 1, k).The proof applies induction to the leaf block B1 and its complement B2.Source: §3 · p. 5
- For k = 4, if G is a forest or has circumference 3 (in which case each block is a triangle or an edge), then Ns(G) ≤ gs(n, k).Source: §3 · pp. 5–6
Theorem 1.6
- The path-free proof adds a dominating vertex and takes the (k + 1)-closure before applying disintegration to bound the s-cliques.The resulting graph H(G′, t + 1) must be complete; otherwise it yields a cycle of length at least 2(t + 2) ≥ k + 1.Source: §3 · p. 6
Corollary 1.7
- N_s(G) ≤ max{f_s(n, k −1, 1), f_s(n, k −1, t)} ≤ h_s(n, k) for path-free graphs with n ≥ k and k ≥ 4.For disconnected graphs, the component bounds combine to give N_s(G) ≤ h_s(n, k); when k = 3, the graph is a matching plus isolated vertices.Source: §3 · p. 6