REVIEW 2 major objections 5 minor 11 references
Maximum flow and self-avoiding walk on bunkbed graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read On bunkbed graphs with mirror-symmetric edge capacities, the maximum flow from x0 to y0 is always at least the flow from x0 to y1; for self-avoiding walks on large complete bunkbeds, the inequality reverses.
desk verdict Strong max-flow bunkbed inequality with a real but repairable gap in the large-n SAW asymptotic. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The main load-bearing object is the linear-programming duality MF(x,y)=min_{f(x)=1,f(y)=0} ∑_{e=uv} c(e)|f(u)-f(v)|, which turns max flow into a minimum over cut-like potentials. To compare MF(x0,y0) with MF(x0,y1), the paper maps any admissible potential f to h defined by h(u0)=max(f(u0),f(u1)) and h(u1)=min(f(u0),f(u1)); a convexity lemma (Lemma 2.3) shows this rearrangement does not increase the horizontal cost while preserving vertical differences, so the cut-minimum for the same-bunk problem is at least that for the cross-bunk problem. For the self-avoiding-walk part, the machinery is a partition of S(u0,v0) and S(u0,v1) into five classes, four of which are paired by explicit bijections (Lemma 3.1); the whole inequality then reduces to comparing the fifth classes, counted exactly for Kn×K2 in Lemma 3.4 and asymptotically in Lemma 3.5.
What would settle it
Evaluate the explicit formulas of Lemma 3.4 for A_n and B_n for n=6 through, say, n=30; if any such n has A_n ≥ B_n, or if the ratios diverge from the claimed asymptotics, then Theorem 1.7's large-n assertion is false.
Extended reading notes
Core claim
The central claims are Theorem 1.4 and Theorem 1.7. Theorem 1.4 says that in G×K2 with reflection-symmetric nonnegative capacities (c(e0)=c(e1) for every edge e of G, with arbitrary vertical capacities), MF(x0,y0) ≥ MF(x0,y1) for every pair x,y. Theorem 1.7 concerns self-avoiding walks: for Kn×K2, |S(u0,v0)| < |S(u0,v1)| when n=3,4,5 and when n is sufficiently large, while n=2 gives equality. The paper also proves Proposition 1.6: on ladder graphs Pn×K2, equality holds for n=2,3, but for n≥4 and adjacent interior vertices u,v the inequality reverses, so the general SAW question has a negative answer. These positive and negative results are unified by a decomposition of the walk sets that reduces everything to a comparison of one exceptional class.
Load-bearing premise
The load-bearing premise is that the stated estimates of how the walk-count sums grow with n are correct, since those estimates are asserted without their details and the entire 'sufficiently large n' conclusion depends on them.
Editorial extensions
If this is right
- The max-flow inequality holds for every finite base graph and every choice of nonnegative reflection-symmetric capacities, including arbitrary vertical edges; this is a deterministic complement to the false bunkbed conjecture for percolation.
- The same convex-rearrangement argument proves Rp(x0,y1) ≥ Rp(x0,y0) for every p>1, extending the known effective-resistance inequality for bunkbed graphs.
- For complete base graphs, the exact counts A4=4,B4=18 and A5=144,B5=387 show the SAW inequality is already strict at n=4 and n=5, not just asymptotically.
- On ladder graphs Pn×K2 with n≥4 and adjacent interior u,v, |S(u0,v0)|>|S(u0,v1)|, giving explicit small counterexamples to the general SAW question.
- When {u,v} is a cut-edge whose endpoints have degree at least 2, the same-layer walk count is strictly larger than the cross-layer count; when one endpoint is a leaf, the counts are equal.
Reading between the lines
- The rearrangement argument is driven only by convexity and reflection symmetry, so a natural testable extension is to nonlinear flow costs φ(|f(u)-f(v)|) with convex φ; the same inequality should hold for p-flow variants with p≥1.
- The exact formulas in Lemma 3.4 make Conjecture 1.8 checkable numerically for every intermediate n; computing A_n and B_n for 6≤n≤30 would likely reveal where the large-n asymptotics kick in.
- Question 3.3 suggests cut-edges are the only obstruction; a search for counterexamples among non-cut-edge graphs such as cycles, grids, or complete bipartite graphs would either sharpen or refute that guess.
- The large-n statement would be placed on a fully explicit footing if the asymptotic estimates (7)-(12) were derived in detail rather than summarized, since those estimates carry the entire 'sufficiently large n' conclusion.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies two models on bunkbed graphs G×K2. In the first part, it proves that for any reflection-symmetric nonnegative capacities on G×K2, the maximum flow from (x,0) to (y,0) is at least that from (x,0) to (y,1), by extending the effective-resistance inequality of Bollobás and Brightwell to p-resistance and then applying a linear programming formulation of max flow. In the second part, it investigates whether |S(u0,v0)| < |S(u0,v1)| for self-avoiding walks. It proves this for Kn×K2 for n=3,4,5 and for all sufficiently large n, gives ladder-graph examples where the inequality fails, and poses a question about the role of cut-edges.
Significance. The max-flow statement is a natural deterministic analogue of the (false) bunkbed percolation conjecture and appears to be a genuine new result; the proof via p-resistance is elegant and, modulo the technical gaps noted below, convincing. For the SAW model, the explicit formulas for An and Bn and the small-case checks are concrete and reproducible, and the bijections reducing the comparison to S5 are a useful device. The paper is self-contained and does not rely on fitted parameters. Its main weakness is the unproved asymptotic estimates that underpin the 'sufficiently large n' claim of Theorem 1.7.
major comments (2)
- [Section 3.2, Lemma 3.5] The proof of Lemma 3.5 establishes the q-case estimates (7), (9), and (10) in detail, but the analogous p-case estimates (8), (11), and (12) are asserted with 'we omit the details.' These estimates are load-bearing: they are exactly what yields the asymptotic An ~ (1+o(1)) e^2 * (n-3) * [(n-2)!]^2 * sum_m 1/((m!)^2(m+1)) and hence the comparison An < Bn for all sufficiently large n, which is the entire content of the 'sufficiently large n' part of Theorem 1.7. The authors should supply these derivations, or an alternative rigorous argument, before the large-n claim can be considered proven.
- [Section 2.2, Lemma 2.4] The proof of the max-flow dual identity is carried out for integer capacities, extended to rational capacities by scaling, and then real capacities are dismissed with 'the general case with real-valued capacities can be proved by a continuity argument, which we omit here.' Since Theorem 1.4 is stated for arbitrary nonnegative real capacities, the proof needs an explicit continuity argument (or a reference) to justify the theorem as stated.
minor comments (5)
- [Section 3, definition of S2(u0, v1)] In item 2, S2(u0,v1) is defined as 'the subset of walks in S(u0,v0)'; this should read S(u0,v1).
- [Section 3, Lemma 3.1] The bijections for S3 and S4 are described verbally and left to the reader; a short verification or figure would improve the paper, since these bijections are used to reduce the problem to S5.
- [Section 3.1, Proposition 1.6] The cases n=2,3 are asserted without proof; given that the proposition is a stated main result for ladder graphs, the omitted verification should be included.
- [Section 2.1, proof of Theorem 2.2] The assertion that f may be truncated to [0,1] should be justified in one sentence, since clipping is a contraction and this step is used in the construction of h.
- [Abstract and throughout] There are several typos, e.g., 'the statement does not holds' in the abstract and 'throug h' in the introduction; a careful proofreading is needed.
Circularity Check
No circularity: the max-flow and SAW derivations use external standard lemmas and explicit combinatorial counts; the omitted details in Lemma 3.5 are soundness gaps, not circular reasoning.
full rationale
The paper has no load-bearing self-citations and no fitted parameter passed off as a prediction. Theorem 1.4 derives the max-flow inequality from the max-flow/min-cut LP dual (Lemma 2.4) and the p-resistance duality of Alamgir-Luxburg (Lemma 2.1), both external; Theorem 2.2's proof is a direct convexity argument (Lemma 2.3) and does not presuppose the desired inequality. The SAW results are obtained from an explicit decomposition of S(u0,v0) and S(u0,v1) into five disjoint classes (Lemma 3.1), explicit counts for K_n (Lemma 3.4), and asymptotic estimates (Lemma 3.5). The large-n comparison An<Bn is not hard-wired by definitions; it depends on nontrivial estimates, some of which are asserted with 'we omit the details' (estimates (8),(11),(12)). Omitting those details is an unproved-assertion/soundness weakness, not circularity: the estimates are checkable inequalities about explicit sums and do not assume the theorem they support. There are no self-citations, no uniqueness theorems imported from the same authors, no ansatz smuggled in via citation, and no known result renamed as a new prediction. Therefore circularity score is 0.
Assumptions & free parameters
assumptions (3)
- standard math p-resistance duality R_p(x,y) = (C_p(x,y))^(-1/(p-1)) (Lemma 2.1, cited from Alamgir-Luxburg [2]).
- standard math LP dual form of max flow: MF(x,y) = min over f with f(x)=1, f(y)=0 of sum_e c(e)|f(u)-f(v)| (Lemma 2.4, plus max-flow min-cut and Menger's theorem).
- ad hoc to paper Asymptotic estimates (8), (11), (12) in Lemma 3.5: sums of a_{t,k} and b_{t,k} are asymptotic to e times their last terms, and p_{k+1}/p_k and q_{k+1}/q_k satisfy the stated decay bounds and asymptotics.
Cite this review
Pith. "Pith review of Maximum flow and self-avoiding walk on bunkbed graphs." pith.science (2026). https://pith.science/paper/H6ZLTU2W
@misc{pith2026250206237,
author = {Pith},
title = {Pith review of: Maximum flow and self-avoiding walk on bunkbed graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/H6ZLTU2W}},
note = {Machine review of arXiv:2502.06237}
}
abstract
We consider two combinatorial models on bunkbed graphs: maximum flow and self-avoiding walks. A bunkbed graph is defined as the Cartesian product $G\times K_2$, where $G$ is a finite graph and $K_2$ is the complete graph on two vertices, labelled $0$ and $1$. For the maximum flow problem, we show that if the bunkbed graph $G\times K_2$ has non-negative, reflection-symmetric edge capacities, then for any $u, v\in V(G)$, the maximum flow strength from $(u,0)$ to $(v,0)$ in $G\times K_2$ is at least as large as that from $(u,0)$ to $(v,1)$. For the self-avoiding walk model on a bunkbed graph $G\times K_2$, we investigate whether there are more self-avoiding walks from $(u,0)$ to $(v,1)$ than from $(u,0)$ to $(v,0)$. We prove that this holds when $G=K_n$ is a complete graph and $n$ is sufficiently large. Additionally, we provide examples where the statement does not holds and pose the question of whether it remains true when $\{u,v\}$ is not a cut-edge of $G$.
Figures
Reference graph
Works this paper leans on
-
[1]
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin . Maximum flow problem. In Christodoulos A. Floudas and Panos M. Pardalos, editors, Encyclopedia of Optimization, pages 2009–2020. Springer, New York, 2009
work page 2009
-
[2]
Phase transition in the family of p-resistances
Morteza Alamgir and Ulrike Luxburg. Phase transition in the family of p-resistances. Advances in neural information processing systems , 24, 2011
2011
-
[3]
Lectures on self-avoiding walks
Roland Bauerschmidt, Hugo Duminil-Copin, Jesse Goodma n, and Gordon Slade. Lectures on self-avoiding walks. In Probability and statistical physics in two and more dimensi ons, volume 15 of Clay Math. Proc. , pages 395–467. Amer. Math. Soc., Providence, RI, 2012
work page 2012
-
[4]
Random walks and electrical resistances in products of graphs
B´ ela Bollob´ as and Graham Brightwell. Random walks and electrical resistances in products of graphs. Discrete Appl. Math. , 73(1):69–79, 1997
work page 1997
-
[5]
The bunkb ed conjecture is false
Nikita Gladkov, Igor Pak, and Aleksandr Zimin. The bunkb ed conjecture is false. arXiv preprint arXiv:2410.02545, 2024
arXiv 2024
-
[6]
On a conjecture of Bollob´ as and Brigh twell concerning random walks on product graphs
Olle H¨ aggstr¨ om. On a conjecture of Bollob´ as and Brigh twell concerning random walks on product graphs. Combin. Probab. Comput. , 7(4):397–401, 1998
work page 1998
-
[7]
Olle H¨ aggstr¨ om. Probability on bunkbed graphs. In Proceedings of FPSAC, volume 3, 2003
work page 2003
-
[8]
The bunkbed conjecture is not robust to generalisation
Lawrence Hollom. The bunkbed conjecture is not robust to generalisation. arXiv preprint arXiv:2406.01790, 2024
arXiv 2024
Show all 11 references
-
[9]
The self-avoiding walk
Neal Madras and Gordon Slade. The self-avoiding walk . Probability and its Applications. Birkh¨ auser Boston, Inc., Boston, MA, 1993
1993
-
[10]
Paolo M. Soardi. Potential theory on infinite networks , volume 1590 of Lect. Notes Math. Berlin: Springer-Verlag, 1994
1994
-
[11]
van den Berg and J
J. van den Berg and J. Kahn. A correlation inequality for connection events in percolation. Ann. Probab., 29(1):123–126, 2001. 15
2001
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.