REVIEW 4 major objections 4 minor 1 references
Some results on concatenating bipartite graphs
T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For each of the thresholds 3/4, 2/5, and 3/5, the paper locates the precise regions of the (x,y)-unit square where the graph functions $\phi$ and $\psi$ force a vertex in $C$ to reach that fraction of $A$ in two steps.
desk verdict A genuine extension of the phi/psi threshold program to three new levels, but the main classifications lean on unproved results from an unpublished companion paper and a few formulas look mistyped. 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 central objects are the extremal functions $\phi(x,y)$ and $\psi(x,y)$, defined as the largest $z$ such that every $(x,y)$-constrained, respectively $(x,y)$-biconstrained, tripartition $(A,B,C)$ of a finite graph has a vertex $v \in C$ with $|N_A^2(v)| \ge z|A|$. The argument is carried by the rotating equivalence 2.7, which equates the three statements $\phi(x,y) \le 1-z$, $\phi(z,x) \le 1-y$, and $\phi(y,z) \le 1-x$, and by the weighted-vertex transfer lemmas 2.9 through 2.11, which build new constrained graphs from old ones so that lower bounds at one scale become upper bounds at the next. Lemma 2.1 supplies the main lower-bound engine: under the biconstrained hypothesis, a subset of $B$ of controlled size forces a controlled number of neighbours in $A$, and iterating this with $k=2$ or more yields the constants $3/4$, $2/5$, and $3/5$.
What would settle it
Compute, by exhaustive search over weighted tripartitions of graphs with small block sizes, the exact value of $\psi(1/2,1/6)$; the first bullet of theorem 5.4 asserts it is below $3/5$, so finding any graph with $\psi \ge 3/5$ there would disprove the claimed upper-bound region.
Extended reading notes
Core claim
For $z \in \{3/4,2/5,3/5\}$, the paper determines, on the square $(0,1]^2$, exactly where $\psi(x,y) \ge z$ and where $\phi(x,y) \ge z$: the boundary curves are given by inequalities such as $16x^2y \ge (3-4x)^2$ for $\phi \ge 3/4$, $12x^2y \ge 5(1-x-y)^2$ for $\phi \ge 2/5$, and $40x^2y \ge (3-5x)^2$ for $\phi \ge 3/5$, complemented by straight-line upper-bound regions obtained from the transfer lemmas and from explicit weighted graph constructions. The paper proves lower-bound theorems and upper-bound theorems that together partition the square as drawn in Figures 1 through 3. In the process it develops general transfer mechanisms: lemma 2.1 controls how large the set of $A$-neighbours of a block $B_k$ must be, and lemmas 2.9 through 2.11 convert a counterexample at a smaller level into one at a larger level by adding three weighted vertices.
Load-bearing premise
The paper relies, without proof, on the block of companion results quoted as 1.1 through 1.6 and 2.2 through 2.8, in particular the rotating equivalence 2.7; if any of those statements is false or needs extra hypotheses, the region classifications here do not follow.
Editorial extensions
If this is right
- The regions where $\phi$ and $\psi$ exceed each of $3/4$, $2/5$, and $3/5$ are completely classified, extending the earlier map at $1/2$, $2/3$, and $1/3$ to three further levels.
- When $\phi(x,y) \ge z$ is claimed, the proof gives explicit algebraic sufficient conditions such as $16x^2y \ge (3-4x)^2$, $12x^2y \ge 5(1-x-y)^2$, and $40x^2y \ge (3-5x)^2$; these can be checked directly for any rational $(x,y)$.
- When $\psi(x,y) < z$ is claimed, the proof supplies explicit biconstrained graphs showing sharpness of the upper-bound regions.
- The rotating equivalence means that proving one of the three equivalent inequalities $\phi(x,y) \le 1-z$, $\phi(z,x) \le 1-y$, $\phi(y,z) \le 1-x$ automatically transfers the result to the other two points, which is how several upper-bound theorems are obtained.
Reading between the lines
- The same transfer-and-bound scheme may work for every rational threshold $a/b$ with $a/b \le 1/2$, with boundary curves described by finitely many polynomial inequalities and line segments; a natural test is to run the machine at $4/7$ or $5/7$.
- The gadget constructions, which add three vertices with carefully chosen weights, suggest that $\phi$ and $\psi$ are piecewise algebraic and possibly computable by a finite optimization over weighted tripartitions, so exact values on the boundary could be checked by symbolic computation.
- Because theorem 2.12 uses explicit cyclic concatenation graphs, the upper-bound regions may have a purely combinatorial characterization independent of the analytic lemmas, which could yield a cleaner proof of the same figures.
- A brute-force search over small weighted tripartitions at a boundary point predicted to have $\psi < z$ would be a direct check of the sharpness of the upper-bound inequalities.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies two graph parameters φ and ψ introduced by Chudnovsky et al. [1]. For x,y in (0,1], φ(x,y) is the best guaranteed fraction of A that some vertex of C reaches by two-edge paths in (x,y)-constrained tripartitions, and ψ is the analogous parameter for biconstrained partitions. The paper proves new general lemmas (2.1, 2.9–2.12) and then determines, for z in {3/4, 2/5, 3/5}, regions of the unit square in which φ(x,y) ≥ z and ψ(x,y) ≥ z, as drawn in Figures 1–3. The lower-bound theorems are proved by case analysis on auxiliary graphs H on C; the upper-bound theorems are largely obtained by applying transformation lemmas to results quoted from [1].
Significance. If the results are correct, the paper gives a substantial extension of the threshold analysis begun in [1], and the new lemmas 2.9–2.12 are potentially useful for future levels. The proofs are detailed and the paper is transparent about which results come from [1]. The main limitations are that the new threshold classifications are conditional on a large block of unproved companion results and that several displayed inequalities in Sections 4.2 and 3.3 appear to contain internal inconsistencies that currently prevent verification.
major comments (4)
- [§2, §3–§5] The central classifications in Figures 1–3 are conditional on Theorems 1.1–1.6 and 2.2–2.8, which are quoted without proof from the unpublished companion paper [1]. This dependence is load-bearing: 3.7 and 5.3 use 2.2; 3.9 uses 2.10, 2.11, and 2.3; 4.3 uses 2.7 and 2.2; 4.4 uses 2.7 and 2.8; 4.6 uses 2.6 and 2.4; and 5.5 uses 2.5 and 2.9. In addition, 3.9 asserts the value φ(3/5,1/5)=3/5 without proof or a numbered reference. Since an extra hypothesis or a wrong inequality in any of these quoted statements would shift the region boundaries, the paper needs to make this block verifiable, for example by including proofs or by providing a version of [1] that is available and refereed.
- [§4.2] The proof of the ψ≥2/5 theorem splits into cases according to whether x+y/(10(1−2y)) ≥ 3/4, but the theorem's first alternative is x+y/(10(1−2y)) ≥ 2/5. As written, the use of 3/4 is not implied by the hypotheses, and the later deduction 'and thus y≥1/4' depends on that stronger threshold. The proof should use 2/5 in place of 3/4 in the case split and in the final estimate |N^2_A(v)| > ... ≥ 3|A|/4; otherwise the argument does not establish the claimed ψ≥2/5 region.
- [§3.3] The condition (3x−1)/(12−12y−4)+x≥1/2, repeated in the proof, has a denominator that simplifies to 8−12y. It is not clear that this is the intended expression: the proof needs to combine the resulting bound with x+1/4 to reach 3/4, and it uses x/(4−4y) in an earlier case. The formula and the surrounding arithmetic need to be corrected.
- [§4.6] The proof 'Apply 2.6 to 2.4' does not follow from the statements as given. Statement 2.6 requires the equality z/(1−z)=φ(x/(1−x),y/(1−y)); applying 2.4 to X=x/(1−x), Y=y/(1−y) yields only φ(X,Y)<2/3 = (2/5)/(1−2/5), not equality. Without an additional monotonicity or continuity statement that upgrades this to equality, the inference φ(x,y)<2/5 is unsupported.
minor comments (4)
- [§3.8] In the proof, 'Choose X3 ⊂ N(V3)' should read 'N(v3)'.
- [§3.2] The phrase 'all points of the upper bound curve' is undefined; the proof should either describe the curve explicitly or refer to the figure by coordinates.
- [§2.10–§2.11] The sentence 'The strict inequality formulation immediately follows, since for some ε>0 we have ψ(x,y) ≤ z−ε < z' is terse; it would help to spell out how the constructed graph gives the strict inequality.
- [§3.9] The first bullet quotes the value φ(3/5,1/5)=3/5; if this is a result from [1], it should be cited to a numbered statement, and if it is new, it should be proved.
Circularity Check
No circularity: the new threshold classifications are derived from graph constructions and prior companion results cited as external lemmas, not from the conclusions they purport to establish.
full rationale
The paper is a continuation of [1] and delegates many lemmas (1.1-1.6, 2.2-2.8) to that companion paper, with statements like 'Here is a basic result from [1], which we state without proof' and 'The following collection of results comes from [1].' This creates a genuine verification gap: theorems 3.7, 3.9, 3.10, 4.3, 4.4, 4.6, 5.3, and 5.5 are short applications of those unproved self-cited results, so their correctness is conditional on [1]. However, that is reliance on prior work, not circularity in the sense used here. The target thresholds (3/4, 2/5, 3/5) are not assumed as inputs; [1] analyzed different levels (1/2, 2/3, 1/3). The paper also contains independent new proofs (2.9-2.12, 3.1-3.6, 3.8, 4.1-4.2, 4.5, 5.1-5.2, 5.4) that construct counterexamples or derive lower bounds from the graph-theoretic definitions. No fitted parameter is renamed as a prediction, and no theorem in [1] is shown to be identical by construction to the new classification. The rigorous circularity tests are therefore not met.
Assumptions & free parameters
assumptions (3)
- domain assumption Theorems 1.1-1.6 and 2.2-2.8 from [1] are correct and apply under the stated hypotheses.
- standard math All graphs are finite with no loops or multiple edges.
- domain assumption Rationality and integrality assumptions can be achieved by blowing up vertices or perturbing x and y.
Cite this review
Pith. "Pith review of Some results on concatenating bipartite graphs." pith.science (2026). https://pith.science/paper/LCCPNUNY
@misc{pith2026190807453,
author = {Pith},
title = {Pith review of: Some results on concatenating bipartite graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/LCCPNUNY}},
note = {Machine review of arXiv:1908.07453}
}
abstract
We consider two functions $\phi$ and $\psi$, defined as follows. Let $x,y \in (0,1]$ and let $A,B,C$ be disjoint nonempty subsets of a graph $G$, where every vertex in $A$ has at least $x|B|$ neighbors in $B$, and every vertex in $B$ has at least $y|C|$ neighbors in $C$. We denote by $\phi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $v \in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. If in addition we require that every vertex in $B$ has at least $x|A|$ neighbors in $A$, and every vertex in $C$ has at least $y|B|$ neighbors in $C$, we denote by $\psi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $v \in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. In their recent paper, M. Chudnovsky, P. Hompe, A. Scott, P. Seymour, and S. Spirkl introduced these functions, proved some general results about them, and analyzed when they are greater than or equal to $1/2, 2/3,$ and $1/3$. Here, we extend their results by analyzing when they are greater than or equal to $3/4, 2/5,$ and $3/5$.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
M. Chudnovsky, P. Hompe, A. Scott, P. Seymour, and S. Spirkl, ``Concatenating bipartite graphs'', submitted for publication, https://web.math.princeton.edu/ pds/papers/chain/paper.pdf
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.