{"id":"cc37d40d-652a-4750-a289-57c1af62d7cb","arxiv_id":"2608.11132","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A constructive lower bound w(s) ≥ 4^s/(2048 s^{5/2}) proves sup_s w(s)^{1/s} = 4 and yields cc(\\bar{P_n}) = cc(\\bar{C_n}) = log_2 n + Θ(log_2 log_2 n).","lead":"The paper proves a 1991 conjecture of Kohayakawa about induced paths in a family of bipartite Kneser-type graphs, giving w(s) ≥ 4^s/(2048 s^{5/2}) for all s ≥ 6. It then uses this to settle a 1985 conjecture on clique coverings of complements of paths and cycles, with cc(\\bar{P_n}) and cc(\\bar{C_n}) equal to log_2 n + Θ(log_2 log_2 n).","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's identified weak point, the unproved recurrence (7), is real but not load-bearing because Section 5 gives a second proof of Theorem 1.4 that avoids it entirely. The main theorem's correctness rests on the self-contained Section 3 construction and the cited Hamiltonicity result, both of which appear correct. I checked the key steps in detail: the distinctness of the constructed sets, the verification of condition (5) for both types of consecutive pairs, the degeneracy bound on the auxiliary graph, the monotonicity lemma, and the local lemma's dependency graph. No internal inconsistency or unsupported step surfaced. The paper is honest about AI assistance and states limitations in Section 6. Therefore the reader's ACCEPT verdict should remain unchanged.","tokens_in":11145,"tokens_out":32170,"duration_ms":218769,"concrete_test":"Verify the transcription of Kohayakawa's recurrence (7) by reproducing its proof or by testing small cases (r=2,3; s=2,3) with an explicit induced-path construction in KG(2(r+s)+1,r+s); if (7) fails for a small case, only Corollary 4.1 is affected, not Theorem 1.4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I reviewed the main construction (Section 3), the recurrence bridge (Section 4), and the independent local-lemma proof (Section 5). The construction of the induced path in G_s is sound: Lemma 3.2's condition (5) is verified for both transition types, the auxiliary graph F is (4k-4)-degenerate as counted, and the algebra in the completion of Theorem 3.1 gives w(s) >= 4^s/(2048 s^{5/2}) correctly. The second proof of Theorem 1.4 via Lemma 5.1, Corollary 5.2, and Proposition 5.3 is also correct; the Lovasz local lemma is applied with a valid dependency graph and probability bound. The sole quoted external fact without proof is Kohayakawa's recurrence (7), but the independent proof does not use it, so the central claim is not hostage to it. No load-bearing concern identified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11319,"tokens_out":30796,"duration_ms":250482,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 3, proof of Theorem 3.1"},{"comment":"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.","section":"Section 4, Eq. (7)"},{"comment":"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}.","section":"Section 4, first proof of Theorem 1.4"},{"comment":"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.","section":"Section 5.1, Lemma 5.1"},{"comment":"The text 'his MS.C. Thesis' contains a small typo; it should be 'his M.Sc. thesis'.","section":"Section 1"}],"recommendation":"accept","confidential_remarks":"The paper is well within the scope of math.CO. The AI-use declaration is transparent and does not affect my assessment. The only external dependency I would flag is the quoted recurrence (7), but the independent proof in Section 5 fully mitigates that concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kohayakawa's conjecture and the 1985 de Caen–Gregory–Pullman conjecture are both settled here, and the quantitative forms are genuinely new. The lower bound w(s) ≥ 4^s/(2048 s^{5/2}) is the first proof that sup w(s)^{1/s}=4, and the bridge to clique coverings gives cc(P_n) = log_2 n + Θ(log_2 log_2 n), matching the known lower bounds up to constants.\n\nThe main construction is the auxiliary graph F and the hypercube encoding. I checked the key steps: Lemma 3.2's induced-path criterion is correct, Lemma 3.3's degeneracy count is sound, and the verification of condition (5) for both transition types in Theorem 3.1 holds. The algebra at the completion of the theorem is also right. The independent proof in Section 5 via the Lovász local lemma and the Hamiltonicity theorem for odd graphs is a nice plus; it avoids the one cited external recurrence (7) and gives the same order estimates.\n\nSoft spots are minor. The recurrence (7) is quoted without proof from Kohayakawa, but it is a standard cited lemma and the second proof does not rely on it, so the paper's central claim is not hostage to it. The constant 2048 is not optimized, and the author openly notes the gap between the coefficients 1/2 and 5/2 in the second-order term. The construction is intricate—a reader must work through the details, but the details are all there and internally consistent.\n\nThis paper should be refereed. It resolves two long-standing conjectures with a serious combinatorial construction, and the exposition is honest about what remains open. I would bring it to a reading group and would cite it.","headline":"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.","tokens_in":11814,"tokens_out":2403,"would_cite":true,"duration_ms":20437,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C38","05C45","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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)$.","keywords":["clique covering number","bipartite Kneser graph","induced path","Johnson graph","local lemma","complement of a path","complement of a cycle","odd graph"],"falsifier":"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.","tokens_in":10981,"feed_emoji":"🧩","tokens_out":15122,"duration_ms":119289,"temperature":0.7,"pith_summary":"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.","feed_headline":"Complements of paths and cycles need log n + Θ(log log n) cliques","feed_subtitle":"A 1991 growth conjecture is settled, and the clique-cover count for path and cycle complements is log n + Θ(log log n).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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$."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the recursion from w(s) to induced paths in odd Kneser graphs, the base value p(5,2)=5, and the growth exponent conjecture that the paper proves.","marker":"[21]"},{"why":"Supplies the lower bounds on clique covering numbers and the cycle-to-path reduction that turn the new upper bound into a sharp order result.","marker":"[13]"},{"why":"Supplies the set-representation theorem equating the clique covering number with the minimum universe size in an intersection representation, the bridge from induced paths to clique coverings.","marker":"[14]"},{"why":"Supplies the Hamilton-connectedness of Johnson graphs, giving the Hamilton path in J(U,k) on which the main construction of Theorem 3.1 is built.","marker":"[4]"},{"why":"Supplies the Hamiltonicity of odd Kneser graphs KG(2k+1,k), the starting point of the independent proof.","marker":"[24]"},{"why":"Supplies the local lemma used to prove the stable-set covering lemma in the independent proof.","marker":"[15]"},{"why":"Supplies the two-stage random construction idea adapted in Lemma 5.1 to cover edges of a bounded-degree graph by stable sets in a path.","marker":"[2]"}],"fun_headline_variants":["Kohayakawa conjecture proved: clique cover gap is Θ(log log n)","Exact order for cliques covering complements of paths and cycles","Settling 1985 and 1991 conjectures on clique covers","Path/cycle complement cliques: log n + Θ(log log n) order"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Kohayakawa conjecture proved: clique cover gap is Θ(log log n)","Exact order for cliques covering complements of paths and cycles","Settling 1985 and 1991 conjectures on clique covers","Path/cycle complement cliques: log n + Θ(log log n) order"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000544,"raw_usage":{"total_tokens":2759,"prompt_tokens":1254,"completion_tokens":1505,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":870,"completion_tokens_details":{"reasoning_tokens":1423}},"tokens_in":870,"tokens_out":1505,"duration_ms":11846,"temperature":1.0,"reasoning_tokens":1423,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:35:12.640416+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Kohayakawa, A note on induced cycles in Kneser graphs,Combinatorica11(1991), no","cited_arxiv_id":null,"evidence_quote":"Supplies the recursion from w(s) to induced paths in odd Kneser graphs, the base value p(5,2)=5, and the growth exponent conjecture that the paper proves."},{"cited_title":"de Caen, D","cited_arxiv_id":null,"evidence_quote":"Supplies the lower bounds on clique covering numbers and the cycle-to-path reduction that turn the new upper bound into a sharp order result."},{"cited_title":"Erdős, A","cited_arxiv_id":null,"evidence_quote":"Supplies the set-representation theorem equating the clique covering number with the minimum universe size in an intersection representation, the bridge from induced paths to clique coverings."},{"cited_title":"Alspach, Johnson graphs are Hamilton-connected,Ars Math","cited_arxiv_id":null,"evidence_quote":"Supplies the Hamilton-connectedness of Johnson graphs, giving the Hamilton path in J(U,k) on which the main construction of Theorem 3.1 is built."},{"cited_title":"Mütze, J","cited_arxiv_id":null,"evidence_quote":"Supplies the Hamiltonicity of odd Kneser graphs KG(2k+1,k), the starting point of the independent proof."},{"cited_title":"Erdős and L","cited_arxiv_id":null,"evidence_quote":"Supplies the local lemma used to prove the stable-set covering lemma in the independent proof."},{"cited_title":"Alon, Covering graphs by the minimum number of equivalence relations,Combina- torica6(1986), no","cited_arxiv_id":null,"evidence_quote":"Supplies the two-stage random construction idea adapted in Lemma 5.1 to cover edges of a bounded-degree graph by stable sets in a path."}],"review_version":1}