Pith. sign in

REVIEW 5 minor 27 references

Kohayakawa's conjecture and clique coverings of complements of paths and cycles

T0 review · 0 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves an induced-path count grows like $4^s/s^{5/2}$, so the exponential base is 4, and derives clique-cover bounds $\mathrm{cc}(\overline{P_n}),\mathrm{cc}(\overline{C_n})=\log_2n+\Theta(\log_2\log_2n)$.

desk verdict Settles two long-standing conjectures with a sound, intricate construction and a clean independent proof; minor reliance on a cited recurrence is not a real weakness. read the letter →

arxiv 2608.11132 v1 pith:TBGEDCMZ submitted 2026-08-11 math.CO

Bo Ning This is my paper · ORCID
classification math.CO MSC 05C7005C3805C4505D40
keywords cliquecoveringnumberbipartiteKnesergraphinducedpathJohnsonlocallemmacomplementofacycleodd
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

For each integer $s$, take the $s$-subsets and the $(s-1)$-subsets of a $2s$-element set, and connect two subsets by an edge when they are disjoint. The paper proves that the longest induced path using only vertices from the $s$-subset side has at least $4^s/(2048\,s^{5/2})$ vertices for every $s\ge 6$, so the exponential growth rate is exactly $4$. That lower bound feeds into a recursion from an earlier paper [21], producing induced paths of length $\Omega(4^r/r^{5/2})$ in the Kneser graph $KG(2r+1,r)$, and those paths in turn give intersection representations that yield clique coverings of complements of paths and cycles. The conclusion is that both $\mathrm{cc}(\overline{P_n})$ and $\mathrm{cc}(\overline{C_n})$ equal $\log_2 n + \Theta(\log_2\log_2 n)$, settling the 1985 conjecture that they are asymptotic to $\log_2 n$. A second proof of the order estimates, independent of the recursion, proceeds through a stable-set covering lemma proved by the local lemma.

What carries the argument

The construction for the growth bound starts from a Hamilton path $B_1,\dots,B_N$ in the Johnson graph $J(U,k)$, which is the graph on $k$-subsets where two sets are adjacent when their symmetric difference has size two. For each edge $e_i=B_iB_{i+1}$, the union $C_i=B_i\cup B_{i+1}$ is a $(k+1)$-set, and an auxiliary graph $F$ records which edges of the Johnson path touch other $k$-subsets contained in $C_i$. Lemma 3.3 shows $F$ is $(4k-4)$-degenerate, hence has a proper coloring with $4k-3$ colors; each color is encoded by a binary string, and transitions between edge colors are routed through the hypercube $Q_h$, with the last coordinate reserved so that internal vertices of the routing paths are never valid color strings. Lifting the Johnson path through the map $B_i \mapsto B_i\cup T(z)$ gives a sequence of $t$-subsets with $t=k+\lceil\log_2(4k-3)\rceil+1$ that satisfies Lemma 3.2's criterion for an induced path, producing $w(t)\ge \binom{2k}{k}$. The second proof's key mechanism is a stable-set covering lemma: for a path $P$ and a graph $H$ sharing no edge with $P$ and with maximum degree $d$, there are $O(\ln d)$ subsets of $V(P)$, each stable in $P$, such that every edge of $H$ lies in one of them; the lemma is proved by the local lemma and applied to the non-consecutive disjointness edges among consecutive vertices of a Hamilton cycle in an odd Kneser graph.

What would settle it

Take the quoted recursion (7) with $r=2$; it predicts $p(2r+1,r)\ge 6w(r-2)-1$ for all $r$, so for a concrete value such as $r=10$, an exact search for the longest induced path in $KG(21,10)$, compared against $6w(8)-1$ using the constructed lower bound for $w(8)$, would expose the recursion if it overcounts. A more direct check is to run the construction behind Lemma 3.2 for small $k$: the produced sequence must contain at least $\binom{2k}{k}$ distinct $t$-subsets and satisfy the containment condition (5), and any failure there would invalidate the main theorem.

Watch

Extended reading notes

Core claim

The paper's central result is Theorem 3.1: for every $k\ge 2$, one has $w(k+\lceil\log_2(4k-3)\rceil+1)\ge \binom{2k}{k}$, and therefore $w(s)\ge 4^s/(2048\,s^{5/2})$ for all $s\ge 6$, which forces $\sup_{s\ge1} w(s)^{1/s}=4$. Via the quoted recursion (7), this yields $p(2r+1,r)\ge c\,4^r/r^{5/2}$ for the maximum order of an induced path in the odd Kneser graph. An induced path of order $m$ in $KG(2r+1,r)$ is the same data as an intersection representation of the complement of $P_m$ on $2r+1$ elements, so the clique covering upper bound $\mathrm{cc}(\overline{P_n})\le \log_2 n+\frac52\log_2\log_2 n+O(1)$ follows by choosing $r$ just above $\frac12\log_2 n+\frac54\log_2\log_2 n$. Together with earlier lower bounds $\mathrm{cc}(\overline{P_{n+1}})>\log_2 n+\frac12\log_2\log_2 n$, the paper obtains the exact order $\Theta(\log_2\log_2 n)$ for the gap, and the cycle bound follows from $\mathrm{cc}(\overline{C_n})\le \mathrm{cc}(\overline{P_{n-1}})+2$. The second proof reaches the same order by starting from a Hamilton cycle in $KG(2k+1,k)$, using the bounded disjointness degree of its vertices, and applying the stable-set covering lemma to add only $O(\ln k)$ new elements to the universe.

Load-bearing premise

The load-bearing premise is an unproved recursion from the earlier paper [21]: it says that a long induced path in one Kneser graph can be grown, using a pattern counted by $w(s)$, into a long induced path in a larger Kneser graph, losing only a factor of $w(s)$ and a subtractive constant; if that recursion failed, the new lower bound would not yield the clique-covering theorem.

Editorial extensions

If this is right

  • Every $s\ge 6$ admits an induced path in $G_s$ with at least $4^s/(2048\,s^{5/2})$ vertices from the $s$-subset side, so the exponential base in $w(s)$ is exactly $4$.
  • The odd Kneser graph $KG(2r+1,r)$ contains induced paths of length $\Omega(4^r/r^{5/2})$ for large $r$.
  • Both $\mathrm{cc}(\overline{P_n})$ and $\mathrm{cc}(\overline{C_n})$ are $\log_2 n+\Theta(\log_2\log_2 n)$, hence asymptotic to $\log_2 n$, confirming the 1985 conjecture.
  • An independent route proves the same order estimates using only Hamiltonicity of odd graphs and a covering lemma for stable sets, so the conclusion does not depend on the recursion's full strength.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The stable-set covering lemma should extend to other sparse host graphs: replacing the path by a forest or a bounded-degree graph would likely yield clique-covering bounds for complements of such graphs, with the $O(\ln d)$ term becoming the log-log correction.
  • The explicit, deterministic nature of the Johnson-path construction suggests that the induced paths in $G_s$ and in the odd Kneser graphs can be generated algorithmically, potentially giving constructive clique coverings rather than mere existence.
  • Because the proof only uses a Hamilton cycle in $KG(2k+1,k)$, any sparse Hamiltonian Kneser graph with smaller vertex degree would reduce the additive $O(\ln k)$ term in the independent proof and might sharpen the coefficient of $\log_2\log_2 n$ toward the lower bound's $\frac12$.
  • The paper does not determine whether the quotients $(\mathrm{cc}(\overline{P_n})-\log_2 n)/\log_2\log_2 n$ converge; if they do, their limits lie between $\frac12$ and $\frac52$, and the true value may be pinned by strengthening Theorem 3.1 to remove a power of $s$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies the induced-path parameter w(s) of the bipartite Kneser graph G_s whose vertices are the s-subsets and (s-1)-subsets of [2s], with disjointness as adjacency. The main theorem, Theorem 3.1, proves w(s) >= 4^s/(2048 s^{5/2}) for all s >= 6, which implies sup_{s>=1} w(s)^{1/s} = 4 and thereby confirms Kohayakawa's conjecture. The paper then derives upper bounds cc(P_n), cc(C_n) <= log_2 n + (5/2) log_2 log_2 n + O(1), and combines them with known lower bounds to conclude cc(P_n) = log_2 n + Theta(log_2 log_2 n) and cc(C_n) = log_2 n + Theta(log_2 log_2 n), settling the 1985 conjecture of de Caen, Gregory, and Pullman. A second, independent proof of these order estimates is given through a stable-set covering lemma proved with the Lovász local lemma together with Hamiltonicity of odd graphs.

Significance. The paper resolves two long-standing conjectures and gives a clean, explicit construction at the heart of the argument. The main construction is fully self-contained: Lemma 3.2 provides a verifiable induced-path criterion, Lemma 3.3 gives a rigorous degeneracy count, and the algebra in Theorem 3.1 is straightforward. The second proof in Section 5 is genuinely independent of Kohayakawa's recurrence (7), so the central claims do not rest on an unproved internal step. The paper also correctly isolates the logarithmic-order correction term for both clique covering numbers. These are substantial contributions to extremal graph theory and the theory of Kneser graphs.

minor comments (5)
  1. [Section 3, proof of Theorem 3.1] In the verification of condition (5) for the first type of consecutive pair, the sentence beginning 'Since no internal vertex of a chosen path in Q_h belongs to tau([q])...' is misstated and obscures the argument: the reason an edge f of (6) incident with B_j exists is that every occurrence of a W-part tau(c) in the sequence arises at a transition across an edge f with gamma(f)=c, not the absence of internal vertices. Please rephrase this step so that the role of the proper coloring of F is explicit.
  2. [Section 4, Eq. (7)] The first proof of Theorem 1.4 relies on Kohayakawa's recurrence (7), which is quoted from [21, Lemma 2] without proof or even a sketch. Since Section 5 gives an independent proof that does not use (7), this is not load-bearing for the main result, but a brief statement of the recurrence's proof or an expanded reference would improve self-containedness.
  3. [Section 4, first proof of Theorem 1.4] In the displayed estimate after the definition of r, the expression '2 L+ 5/2 log2 L+C = 2CnL5/2' is missing braces and is hard to parse; it should read 2^{L + (5/2) log_2 L + C} = 2^C n L^{5/2}.
  4. [Section 5.1, Lemma 5.1] The phrase 'Alon's two stage random-clique construction' does not match the one-stage random process used in the proof; consider writing 'Alon's random-clique construction' instead.
  5. [Section 1] The text 'his MS.C. Thesis' contains a small typo; it should be 'his M.Sc. thesis'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central construction is explicit and the only load-bearing external facts are cited from independent prior work.

full rationale

The paper's main content is an explicit construction proving w(s) ≥ 4^s/(2048 s^{5/2}). The proof of Theorem 3.1 builds an induced path in G_s directly from a Hamilton path in the Johnson graph (Alspach [4]), a proper coloring of an auxiliary graph F, and a hypercube encoding; nothing in that construction presupposes the target lower bound or sup w(s)^{1/s} = 4. The upper bound w(s) ≤ binom(2s,s) < 4^s is immediate counting, so the limit is derived, not assumed. The bridge from w(s) to induced paths in KG(2r+1,r) uses Kohayakawa's recurrence (7) and the base value p(5,2)=5, both from [21], an external source by a different author; the paper's second proof avoids even that recurrence by using the independent Hamiltonicity theorem [24] and the Lovász local lemma. The lower bounds for cc(P_n) and cc(C_n) come from [13], also external, and are not fitted to the paper's data. No self-citations appear among the load-bearing steps, no parameter is calibrated to the quantity being predicted, and no target theorem is used as an input. The derivation chain is therefore self-contained relative to its stated external benchmarks, with no circular step identifiable.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

All external assumptions are standard published theorems. The paper introduces no new entities and has no fitted parameters. The main construction is explicit, so the only burdens are the correctness of the cited theorems and the detailed verification of the sequence in Theorem 3.1.

assumptions (6)
  • standard math Erdős-Goodman-Pósa set representation theorem: cc(G) ≤ r iff there are sets A_v ⊆ [r] with uv∈E(G) iff A_u∩A_v≠∅.
    Stated as Proposition 2.1; it converts induced paths in Kneser graphs into intersection representations of a path, which is the core mechanism connecting w(s) to clique coverings.
  • standard math Alspach's theorem: every Johnson graph J(U,k) is Hamilton-connected, hence has a Hamilton path.
    Used in Section 3 to fix the Hamilton path (6) of the Johnson graph, the spine of the construction.
  • standard math Kohayakawa's recurrence (7): p(2(r+s)+1,r+s) ≥ w(s)(p(2r+1,r)+1)-1 or w(s)p(2r+1,r)-1 according to parity.
    Quoted from [21, Lemma 2]; it is the bridge from w(s) to long induced paths in Kneser graphs KG(2r+1,r).
  • standard math Mütze-Nummenpalo-Walczak theorem: for every k≥3, the odd graph KG(2k+1,k) has a Hamilton cycle.
    Used in Proposition 5.3 to obtain n consecutive vertices of the Kneser graph with bounded disjointness degree, enabling the local-lemma proof.
  • standard math Symmetric Lovász local lemma: if events have probability ≤p and dependency degree ≤D with ep(D+1)≤1, then with positive probability none occur.
    Used in Lemma 5.1 to show a good collection of stable sets exists.
  • standard math Standard binomial bound binom(2k,k) ≥ 4^k/(2√k).
    In Theorem 3.1's finishing estimate, converts the binom lower bound into the stated 4^s/(2048 s^{5/2}) form.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Kohayakawa's conjecture and clique coverings of complements of paths and cycles." pith.science (2026). https://pith.science/paper/TBGEDCMZ

@misc{pith2026260811132,
  author       = {Pith},
  title        = {Pith review of: Kohayakawa's conjecture and clique coverings of complements of paths and cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TBGEDCMZ}},
  note         = {Machine review of arXiv:2608.11132}
}
abstract

For $s\ge1$, let $G_s$ be the bipartite graph between the $s$-subsets and the $(s-1)$-subsets of $[2s]$, where adjacency means disjointness, and let $w(s)$ be the maximum number of $s$-subsets on an induced path in $G_s$. We prove $w(s)\ge \frac{4^s}{2048s^{5/2}}$ for all $s\geq 6$. This implies $\sup_{s\ge1}w(s)^{1/s}=4$, as conjectured by Kohayakawa (1991). His recursive construction then gives induced paths of order $\Omega(4^r/r^{5/2})$ in the Kneser graph $KG(2r+1,r)$ and yields \[ \max\{\cc(\overline{P_n}),\ \cc(\overline{C_n})\} \le \log_2 n+\frac52\log_2\log_2 n+O(1). \] Together with the known lower bounds, this settles a conjecture of de Caen, Gregory, and Pullman (1985) and gives \[ \cc(\overline{P_n})=\log_2 n+\Theta(\log_2\log_2 n), \qquad \cc(\overline{C_n})=\log_2 n+\Theta(\log_2\log_2 n). \] We also give an independent proof of the latter order estimates. It uses a Hamiltonicity result of Kneser graphs and a key lemma proved by the Lov\'{a}sz local lemma.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Alles and S

    P. Alles and S. Poljak, Long induced paths and cycles in Kneser graphs,Graphs Combin.5(1989), no. 1, 303–306

    work page 1989

  2. [2]

    Alon, Covering graphs by the minimum number of equivalence relations,Combina- torica6(1986), no

    N. Alon, Covering graphs by the minimum number of equivalence relations,Combina- torica6(1986), no. 3, 201–206

    work page 1986

  3. [3]

    Alon and J

    N. Alon and J. H. Spencer,The Probabilistic Method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Hoboken, NJ, 2016

    work page 2016

  4. [4]

    Alspach, Johnson graphs are Hamilton-connected,Ars Math

    B. Alspach, Johnson graphs are Hamilton-connected,Ars Math. Contemp.6(2013), no. 1, 21–23

    work page 2013

  5. [5]

    R. F. Bailey, A. C. Burgess, M. S. Cavers, and K. Meagher, Generalized covering designs and clique coverings,J. Combin. Des.19(2011), no. 5, 378–406

    work page 2011

  6. [6]

    Bárány, A short proof of Kneser’s conjecture,J

    I. Bárány, A short proof of Kneser’s conjecture,J. Combin. Theory Ser. A25(1978), no. 3, 325–326

    work page 1978

  7. [7]

    M. S. Cavers,Clique Partitions and Coverings of Graphs, M.Math. essay, University of Waterloo, 2005

    work page 2005

  8. [8]

    M. S. Cavers and J. Verstraëte, Clique partitions of complements of forests and bounded degree graphs,Discrete Math.308(2008), no. 10, 2011–2017

    work page 2008

Show all 27 references
  1. [9]

    Charbit, G

    P. Charbit, G. Hahn, M. Kamiński, M. Lafond, N. Lichiardopol, R. Naserasr, B. Seamone, and R. Sherkati, Edge clique covers in graphs with independence number two,J. Graph Theory97(2021), no. 2, 324–339

    2021

  2. [10]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov, Short proofs of some extremal results,Combin. Probab. Comput.23(2014), no. 1, 8–28

    2014

  3. [11]

    Davoodi, R

    A. Davoodi, R. Javadi, and B. Omoomi, Edge clique covering sum of graphs,Acta Math. Hungar.149(2016), no. 1, 82–91

    2016

  4. [12]

    Davoodi, D

    A. Davoodi, D. Gerbner, A. Methuku, and M. Vizer, On clique coverings of complete multipartite graphs,Discrete Appl. Math.276(2020), 19–23

    2020

  5. [13]

    de Caen, D

    D. de Caen, D. A. Gregory, and N. J. Pullman, Clique coverings of complements of paths and cycles,Ann. Discrete Math.27(1985), 257–267

    1985

  6. [14]

    Erdős, A

    P. Erdős, A. W. Goodman, and L. Pósa, The representation of a graph by set intersections,Canad. J. Math.18(1966), 106–112

    1966

  7. [15]

    Erdős and L

    P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, inInfinite and Finite Sets, Colloq. Math. Soc. János Bolyai, vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627

    1975

  8. [16]

    Godsil and K

    C. Godsil and K. Meagher,Erdős–Ko–Rado Theorems: Algebraic Approaches, Cam- bridge Studies in Advanced Mathematics, vol. 149, Cambridge University Press, Cambridge, 2016

    2016

  9. [17]

    J. E. Greene, A new short proof of Kneser’s conjecture,Amer. Math. Monthly109 (2002), no. 10, 918–920

    2002

  10. [18]

    D. A. Gregory and N. J. Pullman, On a clique covering problem of Orlin,Discrete Math.41(1982), no. 1, 97–99

    1982

  11. [19]

    Gyárfás, A simple lower bound on edge coverings by cliques,Discrete Math.85 (1990), no

    A. Gyárfás, A simple lower bound on edge coverings by cliques,Discrete Math.85 (1990), no. 1, 103–104

    1990

  12. [20]

    Javadi, Z

    R. Javadi, Z. Maleki, and B. Omoomi, Local clique covering of claw-free graphs,J. Graph Theory81(2016), no. 1, 92–104

    2016

  13. [21]

    Kohayakawa, A note on induced cycles in Kneser graphs,Combinatorica11(1991), no

    Y. Kohayakawa, A note on induced cycles in Kneser graphs,Combinatorica11(1991), no. 3, 245–251

    1991

  14. [22]

    Lovász, Kneser’s conjecture, chromatic number, and homotopy,J

    L. Lovász, Kneser’s conjecture, chromatic number, and homotopy,J. Combin. Theory Ser. A25(1978), no. 3, 319–324

    1978

  15. [23]

    B. I. McGrew,From Multi-Prime to Subset Labelings of Graphs, Ph.D. dissertation, Western Michigan University, 2021

    2021

  16. [24]

    Mütze, J

    T. Mütze, J. Nummenpalo, and B. Walczak, Sparse Kneser graphs are Hamiltonian, J. Lond. Math. Soc.(2)103(2021), no. 4, 1253–1275. 16 BO NING

    2021

  17. [25]

    Orlin, Contentment in graph theory: covering graphs with cliques,Indag

    J. Orlin, Contentment in graph theory: covering graphs with cliques,Indag. Math.39 (1977), 406–424

    1977

  18. [26]

    Rödl and M

    V. Rödl and M. Sales, Some results and problems on clique coverings of hypergraphs, J. Graph Theory107(2024), no. 2, 442–457

    2024

  19. [27]

    Schwartz, An overview of graph covering and partitioning,Discrete Math.345 (2022), no

    S. Schwartz, An overview of graph covering and partitioning,Discrete Math.345 (2022), no. 8, Paper No. 112884, 17 pp. College of Computer Science, Nankai University, Tianjin 300350, China. Email: bo.ning@nankai.edu.cn

    2022

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.