Tur\'{a}n number of four vertex-disjoint cliques

Alexandr Kostochka; Dadong Peng; Liang Zhang

arxiv: 2511.05401 · v2 · submitted 2025-11-07 · math.CO

Tur\'{a}n number of four vertex-disjoint cliques

Alexandr Kostochka , Dadong Peng , Liang Zhang This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-05-17 23:50 UTCgrok-4.3open to challenge →

classification math.CO MSC 05C35

keywords Turán numberextremal graph theorydisjoint cliquesHajnal-Szemerédi theoremdischarging methodforbidden subgraphcomplete graph

0 comments

The pith

The exact maximum number of edges in any n-vertex graph without four vertex-disjoint copies of K_p is determined for every n and every p at least 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper finds the precise Turán number ex(n, 4K_p), the largest possible edges in an n-vertex graph containing no four vertex-disjoint complete subgraphs K_p. The authors reach this by adapting the equitable-coloring approach from the proof of the Hajnal-Szemerédi theorem and combining it with a discharging argument to verify the bound in every case. A reader would care because the result gives the sharp threshold at which any additional edge forces the appearance of four separate dense cliques, completing the extremal picture for this forbidden subgraph. The determination holds uniformly for all n and all p greater than or equal to three, supplying an exact formula rather than an asymptotic estimate.

Core claim

Utilizing the idea of the proof of the Hajnal-Szemerédi Theorem and discharging, we determine the value ex(n,4K_p) for all n and p≥3. The argument shows that the extremal graphs are specific constructions that avoid four disjoint K_p while maximizing edges, and the discharging method confirms that no larger edge count is possible without creating the forbidden configuration.

What carries the argument

The Hajnal-Szemerédi theorem proof idea combined with a discharging argument to establish the exact extremal edge count for the forbidden graph 4K_p.

If this is right

Any graph on n vertices with one more edge than the determined value must contain four vertex-disjoint copies of K_p.
The extremal graphs achieving the bound are explicitly characterized by the proof.
The same technique settles the precise edge maximum for the forbidden configuration 4K_p in every order n.
The result supplies the exact threshold separating graphs that avoid four disjoint cliques from those that do not.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same combination of equitable-coloring ideas and discharging may extend to determine ex(n, kK_p) for k larger than four.
The explicit extremal number could be used to derive new bounds on the maximum number of edge-disjoint cliques in dense graphs.
Verification for small fixed p and moderate n by computer search would provide an independent check on the formula.

Load-bearing premise

The discharging argument and the Hajnal-Szemerédi proof idea together cover every possible case without gaps for small n or special values of p.

What would settle it

A single n-vertex graph with no four vertex-disjoint K_p subgraphs yet containing strictly more edges than the extremal number given by the theorem would disprove the result.

read the original abstract

Given a graph $H$, the Tur\'{a}n number ${\rm ex}(n,H)$ of $H$ is the maximum number of edges of an $n$-vertex simple graph containing no $H$ as a subgraph. Let $kK_p$ denote the disjoint union of $k$ copies of the complete graph $K_p$. In this paper, utilizing the idea of the proof of the Hajnal-Szemer\'{e}di Theorem and discharging, we determine the value ${\rm ex}(n,4K_p)$ for all $n$ and $p\ge 3$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Kostochka, Peng, and Zhang give the exact ex(n, 4K_p) for p≥3 by adapting the Hajnal-Szemerédi equitable coloring argument with a discharging procedure on maximal forbidden graphs.

read the letter

The paper settles the exact value of the Turán number ex(n, 4K_p) for every n and every p at least 3. They start from the inductive structure in the proof of Hajnal-Szemerédi, which produces an equitable coloring with Δ+1 colors, and then apply discharging to a maximal 4K_p-free graph to force the edge count down to a specific construction. This yields a closed-form expression rather than an asymptotic bound, which is the main advance over earlier work that handled smaller numbers of cliques or different forbidden graphs. The combination is straightforward once the idea is in place, and the authors appear to reduce most cases to the known theorem or to explicit extremal examples. That is solid, reproducible work in the usual style of exact extremal results. The soft spot is the handling of small n, roughly when n is only a little larger than 4p, or when p=3 and the graph has a few low-degree vertices mixed with triangles. The minimum-degree condition needed to invoke the Hajnal-Szemerédi step can be close to the boundary in those regimes, and the discharging rules need to be checked carefully so that no charge remains negative. The abstract does not spell out the base-case verification, so a referee would want to see explicit checks or a separate small-n argument to be sure the formula does not slip there. Readers who care about packing problems or exact Turán numbers for disjoint unions will get direct use from the result. It is the sort of paper that belongs in a combinatorics journal and should go to peer review; the core argument is standard and the claim is precise enough to be worth referee time even if some boundary details need tightening.

Referee Report

1 major / 1 minor

Summary. The manuscript determines the exact value of the Turán number ex(n, 4K_p) for all n and every p ≥ 3. It does so by adapting the equitable-coloring argument from the proof of the Hajnal–Szemerédi theorem together with a discharging procedure performed on a maximal 4K_p-free graph on n vertices.

Significance. If the central claim holds, the paper supplies a precise extremal function for the forbidden subgraph consisting of four vertex-disjoint copies of K_p. This extends the classical Hajnal–Szemerédi theorem and known results for smaller numbers of disjoint cliques. The combination of a standard theorem with discharging is a conventional and potentially effective approach; the manuscript would be strengthened by explicit verification that the method controls all regimes.

major comments (1)

[Main theorem and discharging section] The global claim that ex(n, 4K_p) is determined for every n and p ≥ 3 requires that every minimal counterexample reduces under the discharging rules and that the Hajnal–Szemerédi step can always be invoked. When n is only slightly larger than 4p, or when the graph has low minimum degree, the minimum-degree hypothesis needed for the equitable-coloring step may fail and the charge function may not become non-negative. The manuscript must contain an explicit base-case verification (for example, a separate lemma or subsection treating n ≤ 5p) to confirm that no exceptions arise in these regimes.

minor comments (1)

[Abstract] The abstract states that the value is determined but does not display the explicit formula obtained for ex(n, 4K_p). Including the closed-form expression would immediately clarify the result for readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the constructive suggestion regarding base-case verification. We agree that making the small-n regimes fully explicit will strengthen the presentation of the proof. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Main theorem and discharging section] The global claim that ex(n, 4K_p) is determined for every n and p ≥ 3 requires that every minimal counterexample reduces under the discharging rules and that the Hajnal–Szemerédi step can always be invoked. When n is only slightly larger than 4p, or when the graph has low minimum degree, the minimum-degree hypothesis needed for the equitable-coloring step may fail and the charge function may not become non-negative. The manuscript must contain an explicit base-case verification (for example, a separate lemma or subsection treating n ≤ 5p) to confirm that no exceptions arise in these regimes.

Authors: We appreciate the referee’s point that the global statement requires explicit confirmation that the discharging rules and the invocation of the Hajnal–Szemerédi theorem remain valid when n is close to 4p or when the minimum degree is modest. In the original proof the maximality of the 4K_p-free graph already forces a sufficiently high minimum degree for the equitable-coloring argument to apply once the discharging phase terminates; nevertheless, to eliminate any doubt we will add a dedicated subsection (new Section 3.1) that treats all n ≤ 5p separately. In this subsection we verify the claimed extremal number by a direct counting argument for n < 4p (where the forbidden subgraph is impossible) and, for 4p ≤ n ≤ 5p, by showing that any maximal 4K_p-free graph on these orders satisfies the edge bound either by exhaustive structural analysis or by confirming that the charge function stays non-negative even under the weaker degree conditions that may occur. This addition will make the coverage of all regimes completely transparent. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation adapts external Hajnal-Szemerédi theorem via independent discharging

full rationale

The paper's central result determines ex(n,4K_p) by adapting the proof structure of the Hajnal-Szemerédi theorem (an independent 1970 result on equitable coloring) together with a discharging argument on maximal 4K_p-free graphs. No step reduces by construction to a self-definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. The Hajnal-Szemerédi invocation is external and not authored by the present team; discharging rules are derived from the extremal setting rather than presupposing the final formula. Base cases and small-n regimes are handled within the same framework without circular reduction to the claimed closed-form expression.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Hajnal-Szemerédi theorem as a background result and standard graph-theoretic definitions; no free parameters or new entities are introduced in the abstract.

axioms (1)

standard math Hajnal-Szemerédi Theorem
The proof idea is taken directly from this theorem on equitable coloring of graphs with given clique number.

pith-pipeline@v0.9.0 · 5395 in / 1106 out tokens · 30560 ms · 2026-05-17T23:50:34.140272+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

utilizing the idea of the proof of the Hajnal-Szemerédi Theorem and discharging, we determine the value ex(n,4K_p) for all n and p≥3

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

Bielak and S

[1]H. Bielak and S. Kieliszek, The Tur´ an number of the graph 3P4, Ann. Univ. Mariae Curie-Sklodowska Sect. A, 68 (2014), 21-29. [2]H. Bielak and S. Kieliszek, The Tur´ an number of the graph 2P 5, Discuss. Math. Graph Theory, 36 (2016), 683-694. [3]R.A. Brualdi and S. Mellendorf, Two extremal problems in graph theory, The Electron. J. Combin., 1 (1994),...

work page 2014
[2]

Bushaw and N

[5]N. Bushaw and N. Kettle, Tur´ an numbers of multiple paths and equibipartite forests, Combin. Probab. Comput., 20 (2011), 837-853. [6]V. Campos and R. Lopes, A proof for a conjecture of Gorgol, Discrete Appl. Math., 245 (2018), 202-207. [7]B. Chen, K.-W. Lih and P. Wu, Equitable coloring and the maximum degree, European J. Combin., 15 (1994), 443-447. ...

work page 2011
[3]

Erd˝ os, ¨ uber ein Extremal problem in der Graphentheorie, Arch

[9]P. Erd˝ os, ¨ uber ein Extremal problem in der Graphentheorie, Arch. Math. (Basel), 13 (1962), 122-127. [10]P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar, 10(3) (1959), 337-356. [11]R.J. Faudree and R.H. Schelp, Path Ramsey numbers in multicolourings, J. Combin. Theory B, 19 (1975), 150-160. [12]Z. F¨ u...

work page doi:10.21136/cmj.2024.0461-23 1962

[1] [1]

Bielak and S

[1]H. Bielak and S. Kieliszek, The Tur´ an number of the graph 3P4, Ann. Univ. Mariae Curie-Sklodowska Sect. A, 68 (2014), 21-29. [2]H. Bielak and S. Kieliszek, The Tur´ an number of the graph 2P 5, Discuss. Math. Graph Theory, 36 (2016), 683-694. [3]R.A. Brualdi and S. Mellendorf, Two extremal problems in graph theory, The Electron. J. Combin., 1 (1994),...

work page 2014

[2] [2]

Bushaw and N

[5]N. Bushaw and N. Kettle, Tur´ an numbers of multiple paths and equibipartite forests, Combin. Probab. Comput., 20 (2011), 837-853. [6]V. Campos and R. Lopes, A proof for a conjecture of Gorgol, Discrete Appl. Math., 245 (2018), 202-207. [7]B. Chen, K.-W. Lih and P. Wu, Equitable coloring and the maximum degree, European J. Combin., 15 (1994), 443-447. ...

work page 2011

[3] [3]

Erd˝ os, ¨ uber ein Extremal problem in der Graphentheorie, Arch

[9]P. Erd˝ os, ¨ uber ein Extremal problem in der Graphentheorie, Arch. Math. (Basel), 13 (1962), 122-127. [10]P. Erd˝ os and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar, 10(3) (1959), 337-356. [11]R.J. Faudree and R.H. Schelp, Path Ramsey numbers in multicolourings, J. Combin. Theory B, 19 (1975), 150-160. [12]Z. F¨ u...

work page doi:10.21136/cmj.2024.0461-23 1962