{"id":"5f366cca-16ae-4132-9c8f-54d19c9346f4","arxiv_id":"2505.03903","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For every k, the density of odd alternating paths P^A_{2k+1} in any edge-coloured graph is at most k^k(k+1)^{k+1}(2k+1)^{-2k-1}.","lead":"This paper proves a sharp upper bound on the number of odd-length red-blue alternating walks that any two-coloured graph can contain. The result solves a problem posed in a recent preprint and is obtained through an entropy-based construction.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central bound rests on lengthy case analysis in Lemmas 4.3–4.4; no independent or symbolic verification is provided.","rationale":"The reader's weakest assumption identifies precisely the same issue: the proof of Theorem 1.2 collapses if Lemmas 4.3 or 4.4 contain a missed case or an algebra error. I verified the surrounding framework: Lemma 3.15's entropy gluing is sound (the conditional independence claims follow from Lemma 3.12, and the entropy accounting for forests is correct), and the local counting in Lemma 2.1 leading to (2.3) is valid after tracking vertex counts and the n(n-1) versus n^2 cancellations. The construction of φ and the covering counts match the stated formulas in spot checks. Therefore the only load-bearing weakness is the unverified lengthy case analysis, which is a correctness risk due to human error rather than a discovered mathematical flaw. Since the reader already conditioned acceptance on clarification of this point, my stress test does not change the verdict; it underscores that an independent computational check of Lemmas 4.3 and 4.4 would settle the issue.","tokens_in":25655,"tokens_out":30275,"duration_ms":238077,"concrete_test":"Independently verify Lemmas 4.3 and 4.4 by computer: for each congruence class in Definition 4.1, generate x, y, z symbolically and evaluate all expressions c(v_j) and c(v_j, v_{j+1}) for 0 ≤ j ≤ k, asserting that each equals k(k+1)^2(2k+1). This can be done by a short script for k up to, say, 1000, and the algebraic identities for general k in each class can be checked with a computer algebra system (e.g., SymPy) by simplifying the expressions using the given piecewise definitions. If any evaluation deviates from the target value, Lemma 2.1 fails and Theorem 1.2 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.2 depends entirely on Lemma 2.1, which in turn requires an edge-coloured forest H_{2k+1} whose defining vectors x, y, z (Definition 4.1) satisfy the covering identities in Lemmas 4.3 and 4.4. These identities are verified in Appendix A by a case analysis over congruence classes of k, with explicit algebra for each sub-case. The proof gives no structural reason why the formulas hold, and the vectors were found by extrapolating LP solutions up to k=40, so a single missed index or a single algebraic slip would invalidate Lemma 2.1 and hence the main theorem. I spot-checked several representatives (k=1,2,3,5,7,8) and the expressions simplify correctly, but the full verification spans dozens of pages of routine algebra. The other potential weak point, the edge-accounting in the proof of (2.3), appears correct once the vertex-count cancellations are tracked (v(H')=v(H''') and n(n-1) terms are dominated by n^2); it is terse but not flawed. Thus the load-bearing concern is the reliability of the covering-identity case analysis, not a structural gap in the entropy argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every k >= 1 and every red/blue edge-coloured graph G, the homomorphism density of the odd alternating path P^A_{2k+1} satisfies t(P^A_{2k+1}, G) <= k^k (k+1)^{k+1} (2k+1)^{-2k-1}, and that this bound is asymptotically tight. This answers Problem 9.2 of Basit, Granet, Horsley, Kündgen and Staden. The proof constructs, for each k, an explicit auxiliary edge-coloured forest H_{2k+1} defined through three integer vectors x, y, z; proves a lower bound on t(P^A_{2k+1}, G)^{1/e(P)} in terms of t(H_{2k+1}, G)^{1/e(H)} using an entropy argument (Lemma 3.15); proves an upper bound on t(H_{2k+1}, G) in terms of t(P^A_{2k+1}, G) by elementary degree counting; and then combines the two inequalities. The vectors x, y, z are chosen so that H_{2k+1} admits a homomorphism to P^A_{2k+1} covering every vertex and edge the same number of times; the verification of the required identities is carried out by a lengthy case analysis in Appendix A.","tokens_in":25898,"tokens_out":21794,"duration_ms":203153,"significance":"If the proof is correct, this is a substantial result: it solves an open problem on semi-inducibility for odd alternating paths and provides the first entropy-method proof of the full family. The paper is self-contained: the entropy lemmas are proved in Section 3, the auxiliary forest is constructed from scratch, and the target constant emerges algebraically rather than being assumed. The authors are also transparent about the provenance of the vectors, which were discovered by solving a linear program for k up to about 40 and then extrapolating a pattern. The main correctness risk is the heavy reliance on the case analysis in Appendix A for Lemmas 4.3 and 4.4; I spot-checked several representative values of k and found the algebra correct, but the proof does not give a conceptual reason for the identities. This is a legitimate concern but not, in my reading, a demonstrated flaw.","major_comments":[],"minor_comments":[{"comment":"The accounting of edge-colour changes in the transition from H'_2k+1 to H'''_2k+1 is misleading. The text says that the number of blue edges lost is sum_j |Z^B_j| = k sum_j z_j, but deleting the Z-sets actually removes more blue edges: the Z^R_j-Z^RB_j matchings contribute (k+1)z_j blue edges and the Z^B_j-Z^BB_j matchings contribute k z_j blue edges, in addition to the k z_j blue edges from Z^B_j to v_j. The isolated blue edges added to form H'''_2k+1 then give a net loss of k sum_j z_j. The final ratio claim is true, but it should be stated as a net-change computation, not as a direct loss.","section":"§4, proof of Lemma 2.1, paragraph after Eq. (4.6)"},{"comment":"The sentence 'it is not hard to check that each vertex v_j is covered exactly c(v_j)+1 times and each edge v_jv_{j+1} is covered exactly c(v_j,v_{j+1})+1 times' is the bridge between the construction of H_{2k+1} and Lemmas 4.3 and 4.4. Since the whole proof depends on this point, I recommend adding a short explicit derivation for the vertex and edge cover counts, especially for the Z-sets, where the blue perfect matchings make the count less immediate.","section":"§4, proof of Lemma 2.1, construction of the covering homomorphism"},{"comment":"Lemma 2.1, and therefore Theorem 1.2, rests entirely on the identities in Lemmas 4.3 and 4.4, whose verification is a long case analysis over congruence classes of k. I checked several representative cases and found no error, but I recommend that the authors add an explicit statement that the listed subcases are exhaustive, and ideally provide a small symbolic verification script or computer algebra check as supplementary material. This is a robustness suggestion rather than a request based on a detected mistake.","section":"Appendix A"},{"comment":"In the derivation of the density inequality from the homomorphism inequality, the paper uses that v(H) = v(P^A_{2k+1}) e(H)/e(P^A_{2k+1}) because the covering homomorphism covers every vertex the same number of times. The analogous vertex-count cancellation in the proof of (4.6), namely v(H'_2k+1) = v(H'''_2k+1), is never stated; I recommend adding one sentence to make that step explicit.","section":"§3, proof of Lemma 3.15"},{"comment":"There are a few typographical errors: 'asympototically' in Section 1 and 'semi-inducubility' in Section 5. These should be corrected.","section":"§1 and §5"}],"recommendation":"minor_revision","confidential_remarks":"The paper is strong and the main theorem is significant. My recommendation of minor revision is based on the local but real issue with the edge-colour accounting in the proof of (2.3) and on the desire for a slightly more explicit verification of the covering counts. The lengthy case analysis in Appendix A is the main correctness risk, but I did not find an actual error. Given the importance of the result, it would be worth asking the authors to include a machine-checkable verification of Lemmas 4.3 and 4.4 as supplementary material."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read the paper twice, including the appendix. The result is genuine: it settles the odd-length case of Basit et al.'s semi-inducibility problem for alternating paths, with a sharp constant that matches the natural construction with p=(k+1)/(2k+1). The entropy framework is adapted cleanly from Behague et al. and Kopparty-Rossman, and Lemma 3.15 is a nice general criterion. The construction of H_{2k+1} is intricate and seems to work; I spot-checked several values of k and the covering identities hold. The LP origin of the vectors is disclosed honestly, which is good.\n\nThe main soft spot is exactly where the stress-test put it: the covering identities in Lemmas 4.3 and 4.4 are verified by dozens of pages of algebraic case analysis. That is load-bearing. If a single case is wrong, Lemma 2.1 collapses. The authors say the verification is 'straightforward but tedious' and put it in an appendix, but they do not provide any independent check, symbolic or otherwise. I'd want at least a self-contained derivation of the covering counts or a reference to machine verification. The other concern, the edge-colour accounting in the proof of (2.3), I believe is fine; the cancellation the stress-test mentions works. It is terse, but not flawed.\n\nOne thing I'd push back on in the reader's report: the claim that the covering counts are 'asserted as not hard to check' is slightly overstated. The paper explicitly proves them in an appendix; the issue is more that the appendix is routine algebra without structure. The paper also says the second candidate for H3 yields a 3-covering, which gives some cross-check.\n\nIs this paper for everyone? Only extremal combinatorics people. But for that community it's a serious contribution, not a paradigm shift. It extends the entropy-tree method to a new setting and demonstrates the LP-to-explicit-construction pipeline. I'd send it to a competent referee for a full proof check, especially of the appendix, and expect it to be accepted after minor revisions.\n\nRecommended: conditional accept, with a request that the authors either shorten the case analysis with a more conceptual derivation, or provide the code/script used to verify the identities symbolically.","headline":"A solid entropy-method proof of the odd alternating path bound, with the main risk being a lengthy computer-inspired case analysis that is only spot-checked.","tokens_in":26384,"tokens_out":1469,"would_cite":true,"duration_ms":14311,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C15","05C38","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a sharp, asymptotically tight bound on red-blue alternating walks of every odd length in any edge-coloured graph.","keywords":["semi-inducibility","alternating paths","edge-coloured graphs","homomorphism density","entropy method","extremal graph theory","forest construction","red-blue colourings"],"falsifier":"For k=2 and n=5, enumerate all $2^{{10}}$ red/blue colourings of K_5 and compute, for each, the number of homomorphisms from the six-vertex alternating path P^A_5 into the coloured graph; if any colouring yields more than 540 homomorphisms—equivalently t(P^A_5,G) > 108/3125—Theorem 1.2 is false. If no colouring exceeds 540, the k=2 case passes its smallest exact test.","tokens_in":25474,"feed_emoji":"🎲","tokens_out":10492,"duration_ms":99987,"temperature":0.7,"pith_summary":"The paper proves an exact extremal bound for colour-alternating walks of odd length in red-blue edge-coloured graphs. For every k≥1, in any n-vertex graph whose edges are red or blue, the number of walks of length 2k+1 with k+1 red edges and k blue edges is at most k^k(k+1)^{k+1}(2k+1)^{-2k-1}$n^{{2k+2}}$. This settles the odd-length case of a problem about the maximum homomorphism density of edge-coloured paths, the semi-inducibility problem. The proof introduces an auxiliary red-blue forest and compares the path count to the forest count using the entropy method; the bound is asymptotically tight, since graphs with red and blue degrees in the ratio (k+1):k come close to achieving it.","feed_headline":"Every odd alternating path has a sharp density cap","feed_subtitle":"In any red-blue graph, the density of odd alternating paths never exceeds an explicit constant; the bound is asymptotically tight.","key_machinery":"An auxiliary edge-coloured forest H_{2k+1}. Starting from P^A_{2k+1}, the construction attaches pendant red and blue edges, two-edge pendant paths, isolated edges, and isolated vertices in multiplicities encoded by three symmetric integer vectors x, y, z (Definition 4.1). A homomorphism from H_{2k+1} to the path covers every vertex and every edge exactly k(k+1)^2(2k+1)+1 times; because H_{2k+1} is a forest, this covering lets the entropy lemma (Lemma 3.15) produce a random homomorphism from H_{2k+1} to G whose entropy is exactly e(H_{2k+1})/e(P^A_{2k+1}) times the entropy of a uniform random homomorphism from the path to G. That gives the lower comparison t(P)^{1/e(P)} ≤ t(H)^{1/e(H)}. A separate degree-counting argument bounds t(H) from above by a constant power of t(P), and the two inequalities sandwich t(P) into the claimed constant.","core_discovery":"Theorem 1.2 is the paper's central discovery: for every k≥1 and every edge-coloured graph G, t(P^A_{2k+1},G) ≤ k^k(k+1)^{k+1}(2k+1)^{-2k-1}, where t is the homomorphism density—the probability that a uniformly random map of the path's vertices into G respects adjacency and edge colours. The constant is asymptotically tight: a graph where every vertex has red degree about (k+1)/(2k+1)n and blue degree about k/(2k+1)n realizes the bound in the limit. The theorem resolves the odd alternating path case of a problem stated in [2] and complements the known even-length result t(P^A_{2k},G) ≤ (1/2)^{2k}. The proof works with homomorphisms, which need not be injective, rather than copies; the paper notes the two formulations agree up to lower-order terms.","pith_inferences":["The paper's linear-programming search suggests a recipe for other targets: for any edge-coloured tree, one can set up a small linear program whose feasible integer solutions are exactly the auxiliary forests needed for an entropy proof; the same search could be run for alternating cycles of length 4k+2, where no covering forest is currently known.","Because the lower comparison (2.2) is tight for a much larger family than the extremal clique—any graph with prescribed red and blue degrees—the equality cases of the entropy argument may characterize 'locally balanced' graphs and could support a stability version of Theorem 1.2.","A direct corollary not drawn in the paper: the covering-forest strategy should yield exact density bounds for alternating paths with any fixed colour sequence, provided the target remains a tree and the corresponding linear program admits integer solutions."],"forward_implications":["The odd alternating path problem in the semi-inducibility framework is settled: the homomorphism density of P^A_{2k+1} is asymptotically at most the explicit constant, and this is best possible.","The same kind of construction with a simpler forest H_{2k} reproduces the even-length bound t(P^A_{2k},G) ≤ (1/2)^{2k}, giving a second proof of that result.","Near-extremal graphs must have a red/blue degree split close to the ratio (k+1):k, so the extremal examples are explicit and not exotic.","The entropy comparison of Section 3 applies to any edge-coloured forest that evenly covers a target path, so the method is a general tool for path and forest semi-inducibility rather than a one-off calculation.","For trees with r colours and one edge of each colour at each non-leaf, the same argument yields a multicolour bound of (1/r)^{e(T)}."],"supporting_citations":[{"why":"Poses the semi-inducibility problem, proves the even-length alternating-path bound, and lists the odd-length case (Problem 9.2) that Theorem 1.2 answers.","marker":"[2]"},{"why":"Develops Sidorenko-type homomorphism-density inequalities for pairs of trees via entropy; the comparison strategy in Section 3 adapts this to edge-coloured forests.","marker":"[3]"},{"why":"Introduces the entropy method for homomorphism-count domination, the basis of Lemma 3.15 and the distribution-gluing construction.","marker":"[15]"},{"why":"Stated as the source of the distribution-gluing lemma used to build the entropy-maximizing random homomorphism from H_{2k+1} to G.","marker":"[16]"}],"fun_headline_variants":["Entropy proves exact cap for odd alternating paths","Odd alternating paths: entropy settles density limit","Alternating walks: entropy method gives tightest bound","Max density of odd alternating paths is now exact","Entropy solves alternating path maximum problem"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof rests on an exact bookkeeping identity for every k — the integer vectors x, y, z define a forest whose natural homomorphism to the alternating path covers every vertex and edge an equal number of times — and this identity is verified only by a lengthy appendix case analysis, so a single missed case or algebraic slip would collapse Lemma 2.1 and hence Theorem 1.2.","fun_headline_variants_meta":{"raw":{"variants":["Entropy proves exact cap for odd alternating paths","Odd alternating paths: entropy settles density limit","Alternating walks: entropy method gives tightest bound","Max density of odd alternating paths is now exact","Entropy solves alternating path maximum problem"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000634,"raw_usage":{"total_tokens":2870,"prompt_tokens":832,"completion_tokens":2038,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":448,"completion_tokens_details":{"reasoning_tokens":1969}},"tokens_in":448,"tokens_out":2038,"duration_ms":15156,"temperature":1.0,"reasoning_tokens":1969,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:44:59.866053+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For k=2 and n=5, enumerate all $2^{{10}}$ red/blue colourings of K_5 and compute, for each, the number of homomorphisms from the six-vertex alternating path P^A_5 into the coloured graph; if any colouring yields more than 540 homomorphisms—equivalently t(P^A_5,G) > 108/3125—Theorem 1.2 is false. If no colouring exceeds 540, the k=2 case passes its smallest exact test.","supporting_citations":[{"cited_title":"Sidorenko-Type Inequalities for Pairs of Trees","cited_arxiv_id":"2305.16542","evidence_quote":"Develops Sidorenko-type homomorphism-density inequalities for pairs of trees via entropy; the comparison strategy in Section 3 adapts this to edge-coloured forests."},{"cited_title":"Kopparty and B","cited_arxiv_id":null,"evidence_quote":"Introduces the entropy method for homomorphism-count domination, the basis of Lemma 3.15 and the distribution-gluing construction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Stated as the source of the distribution-gluing lemma used to build the entropy-maximizing random homomorphism from H_{2k+1} to G."}],"review_version":1}