Maximizing Alternating Paths via Entropy

Felix Christian Clemen; Hao Chen; Jonathan A. Noel

Maximizing Alternating Paths via Entropy

T0 review · 0 major / 5 minor · reviewed 2026-08-15 · 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 a sharp, asymptotically tight bound on red-blue alternating walks of every odd length in any edge-coloured graph.

desk verdict 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. read the letter →

arxiv 2505.03903 v1 pith:YI5DSXGK submitted 2025-05-06 math.CO

Hao Chen , Felix Christian Clemen , Jonathan A. Noel This is my paper · ORCID

classification math.CO MSC 05C3505C1505C3805D40

keywords semi-inducibilityalternatingpathsedge-colouredgraphshomomorphismdensityentropymethodextremalgraphtheoryforestconstructionred-bluecolourings

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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)}.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

The 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.

One 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.

Is 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.

Recommended: 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.

Referee Report

0 major / 5 minor

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.

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.

minor comments (5)

[§4, proof of Lemma 2.1, paragraph after Eq. (4.6)] 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.
[§4, proof of Lemma 2.1, construction of the covering homomorphism] 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.
[Appendix A] 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.
[§3, proof of Lemma 3.15] 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.
[§1 and §5] There are a few typographical errors: 'asympototically' in Section 1 and 'semi-inducubility' in Section 5. These should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the entropy framework and the explicit forest construction are proved in-paper, and the LP-based discovery of the vectors is a search heuristic rather than a fitted input.

full rationale

The main claim is derived from Lemma 2.1, which is proved entirely in the paper. Inequality (2.2) follows from Lemma 3.15, whose proof using entropy, the chain rule, the deconditioning lemma, and the distribution gluing lemma is self-contained in Section 3 and does not depend on any external or self-cited result for its validity. Inequality (2.3) is proved by explicit homomorphism counting: the proof deletes pendant sets, applies the elementary bound dR(u)+dB(u) <= n-1 with exponents k and k+1, and then accounts for isolated edges; the target constant emerges from these local inequalities. The forest H_{2k+1} is constructed explicitly in Definition 4.1, and Lemmas 4.3 and 4.4 verify the covering identities by direct algebra in Appendix A. Although the appendix is lengthy and would benefit from independent symbolic checking, that is a verification concern, not circularity: the identities are proved in-paper, not imported. The disclosure that the vectors x, y, z were found by solving a linear program for k up to about 40 and then extrapolating a pattern is a search heuristic; the formulas are subsequently verified for all k, and no value from the target inequality is used as an input. Self-citations such as [3] and [15] appear only for context or for standard entropy tools, and the lemmas actually needed (3.12 and 3.15) are proved in the paper with complete proofs. No step in the derivation reduces by construction to its own input, so there is no circularity.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The only hand-chosen objects are the vectors defining H_{2k+1}. They are auxiliary proof devices, not fitted physical parameters; listing them here is the conservative choice. All other background is standard mathematics.

free parameters (1)

vectors x,y,z defining H_{2k+1} = explicit formulas in Definition 4.1 (e.g., k=1: x=(0,4,4,0), y=(2,2,2), z=(0,0,0,0))
These integer vectors are chosen ad hoc to make the auxiliary forest H_{2k+1} satisfy Lemma 2.1; they were discovered by solving a linear program for k up to 40 and then extrapolated. They are not empirical fits, but they are hand-selected construction parameters rather than derived naturally.

assumptions (4)

standard math Standard entropy facts: uniform distribution maximizes entropy; chain rule; deconditioning lemma.
Used in Section 3; proofs are standard or included in the paper.
standard math Markov property for uniformly random homomorphisms from a tree: the image of a child is conditionally independent of all earlier images except the parent.
Invoked in Proposition 3.10 and in Lemma 3.15; standard in entropy proofs for tree homomorphisms, though not proved in detail here.
standard math A calculus inequality: for x+y <= m, x^a y^b <= m^{a+b} (a/(a+b))^a (b/(a+b))^b.
Footnoted in Section 2 and used repeatedly in Section 4 for the local degree bounds.
domain assumption The semi-inducibility problem can be studied through homomorphism densities rather than labeled copies.
The paper states the two formulations are 'roughly equivalent' and proves the homomorphism version. This is a standard modeling choice in extremal combinatorics.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Maximizing Alternating Paths via Entropy." pith.science (2026). https://pith.science/paper/YI5DSXGK

@misc{pith2026250503903,
  author       = {Pith},
  title        = {Pith review of: Maximizing Alternating Paths via Entropy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YI5DSXGK}},
  note         = {Machine review of arXiv:2505.03903}
}

abstract

We prove that if $G$ is an $n$-vertex graph whose edges are coloured with red and blue, then the number of colour-alternating 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 solves a problem that was recently posed by Basit, Granet, Horsley, K\"undgen and Staden. Our proof involves an application of the entropy method.

Figures

Figures reproduced from arXiv: 2505.03903 by the authors.

**Figure 2.** A representation of a possible choice of the edge-coloure [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** The edge-colored graph H2k. 3 Homomorphism Counting Inequalities Via Entropy Our focus in this section is on proving a lemma which will allow us to establish the inequality (2.2) in Lemma 2.1. To keep the calculations simple and focused, we will only deal with the case of odd alternating paths; however, by incorporating more of the ideas from [3] (which are built upon ideas from [15]), one can extend this approach t… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: A tree with edges of three colours. Acknowledgements. We learned about the semi-inducibility problem through remotely attending a talk given by Bertille Granet as part of the Connections Workshop: Extremal Combinatorics held at SL Math in February, 2025. We thank SL Ma…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Semi-inducibility of 4-vertex graphs
math.CO 2025-10 conditional novelty 7.0 of 10

The paper determines the semi-inducibility constants for all 4-vertex non-complete graphs except the blue-blue-red path, using flag algebra certificates and stability arguments.
On Alternating 6-Cycles in Edge-Coloured Graphs
math.CO 2025-05 conditional novelty 6.0 of 10

The density of colour-alternating 6-cycles in any red/blue edge-coloured graph is at most (1/2)^6, matching the random colouring.

Reference graph

Works this paper leans on

19 extracted references · 15 canonical work pages · cited by 2 Pith papers

[1]

Alon and J

N. Alon and J. H. Spencer. The probabilistic method . Wiley Series in Discrete Mathe- matics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourt h edition, 2016

2016
[2]

Basit, B

A. Basit, B. Granet, D. Horsley, A. K¨ undgen, and K. Staden. T he semi-inducibility problem. E-print arXiv:2501.09842v1, 2025

arXiv 2025
[3]

Sidorenko-Type Inequalities for Pairs of Trees

N. Behague, G. Crudele, J. A. Noel, and L. Simbaqueba. Sidorenk o-type inequalities for pairs of trees. E-print arXiv:2305.16542v2, 2025. 21

work page Pith review arXiv 2025
[4]

Behague, N

N. Behague, N. Morrison, and J. A. Noel. Common pairs of graphs . E-print arXiv:2208.02045v3, Accepted to Combin. Probab. Comput. , 2023

work page arXiv 2023
[5]

Behague, N

N. Behague, N. Morrison, and J. A. Noel. Oﬀ-diagonal commonalit y of graphs via entropy. SIAM J. Discrete Math. , 38(3):2335–2360, 2024

work page 2024
[6]

Blekherman and A

G. Blekherman and A. Raymond. A path forward: tropicalization in extremal combi- natorics. Adv. Math. , 407:Paper No. 108561, 68, 2022

work page 2022
[7]

Blekherman and A

G. Blekherman and A. Raymond. A new proof of the Erd˝ os-Simon ovits conjecture on walks. Graphs Combin. , 39(3):Paper No. 53, 8, 2023

work page 2023
[8]

Chao and H.-H

T.-W. Chao and H.-H. H. Yu. When entropy meets Tur´ an: new pro ofs and hypergraph Tur´ an results. E-print arXiv:2412.08075v2, 2024

arXiv 2024

Show all 19 references

[9]

Conlon, J

D. Conlon, J. H. Kim, C. Lee, and J. Lee. Some advances on Sidore nko’s conjecture. J. Lond. Math. Soc. (2) , 98(3):593–608, 2018

2018
[10]

Conlon and J

D. Conlon and J. Lee. Finite reﬂection groups and graph norms. Adv. Math., 315:130– 165, 2017

2017
[11]

Conlon and J

D. Conlon and J. Lee. Domination inequalities and dominating graph s. Math. Proc. Cambridge Philos. Soc. , 177(1):167–184, 2024

2024
[12]

Grzesik, J

A. Grzesik, J. Lee, B. Lidick´ y, and J. Volec. On tripartite comm on graphs. Combin. Probab. Comput., 31(5):907–923, 2022

2022
[13]

H. Hatami. Graph norms and Sidorenko’s conjecture. Israel J. Math. , 175:125–150, 2010

2010
[14]

J. S. Kim and J. Lee. Extended commonality of paths and cycles v ia Schur convexity. J. Combin. Theory Ser. B , 166:109–122, 2024

2024
[15]

Kopparty and B

S. Kopparty and B. Rossman. The homomorphism domination exp onent. European J. Combin., 32(7):1097–1114, 2011

2011
[16]

J. Lee. On some graph densities in locally dense graphs. Random Structures Algorithms, 58(2):322–344, 2021

2021
[17]

Lov´ asz

L. Lov´ asz. Subgraph densities in signed graphons and the loca l Simonovits-Sidorenko conjecture. Electron. J. Combin. , 18(1):Paper 127, 21, 2011

2011
[18]

A. F. Sidorenko. A correlation inequality for bipartite graphs. Graphs Combin. , 9(2):201–204, 1993

1993
[19]

B. Szegedy. An information theoretic approach to Sidorenko’s conjecture. E-print arXiv:1406.6738v3, 2015. 22 A Veriﬁcation of the Covering Conditions The purpose of this appendix is to carry out the calculations require d to prove Lemmas 4.3 and 4.4; we start with the former. ...

2015 arXiv

Pith tools

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

[1] [1]

Alon and J

N. Alon and J. H. Spencer. The probabilistic method . Wiley Series in Discrete Mathe- matics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourt h edition, 2016

2016

[2] [2]

Basit, B

A. Basit, B. Granet, D. Horsley, A. K¨ undgen, and K. Staden. T he semi-inducibility problem. E-print arXiv:2501.09842v1, 2025

arXiv 2025

[3] [3]

Sidorenko-Type Inequalities for Pairs of Trees

N. Behague, G. Crudele, J. A. Noel, and L. Simbaqueba. Sidorenk o-type inequalities for pairs of trees. E-print arXiv:2305.16542v2, 2025. 21

work page Pith review arXiv 2025

[4] [4]

Behague, N

N. Behague, N. Morrison, and J. A. Noel. Common pairs of graphs . E-print arXiv:2208.02045v3, Accepted to Combin. Probab. Comput. , 2023

work page arXiv 2023

[5] [5]

Behague, N

N. Behague, N. Morrison, and J. A. Noel. Oﬀ-diagonal commonalit y of graphs via entropy. SIAM J. Discrete Math. , 38(3):2335–2360, 2024

work page 2024

[6] [6]

Blekherman and A

G. Blekherman and A. Raymond. A path forward: tropicalization in extremal combi- natorics. Adv. Math. , 407:Paper No. 108561, 68, 2022

work page 2022

[7] [7]

Blekherman and A

G. Blekherman and A. Raymond. A new proof of the Erd˝ os-Simon ovits conjecture on walks. Graphs Combin. , 39(3):Paper No. 53, 8, 2023

work page 2023

[8] [8]

Chao and H.-H

T.-W. Chao and H.-H. H. Yu. When entropy meets Tur´ an: new pro ofs and hypergraph Tur´ an results. E-print arXiv:2412.08075v2, 2024

arXiv 2024