{"id":"78cdb890-36dc-4e89-8016-27c2c97a8c89","arxiv_id":"1908.07453","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper identifies new regions of the (x,y) square where the graph functions ψ(x,y) and φ(x,y) are guaranteed to be at least 3/4, 2/5, and 3/5, plus complementary regions where they are not.","lead":"This paper maps out new regions of the unit square where two graph functions, phi and psi, are guaranteed to exceed specified thresholds. It extends a prior paper by the same authors that handled three smaller thresholds, adding three new levels with a mix of new lemmas and earlier tools.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central classifications are conditional on unproved companion results from [1]; a wrong or extra hypothesis there shifts the region boundaries.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing point: the new results are built on unproved theorems from the companion paper. This is the right concern because it is global rather than local. Even if every new proof in Sections 3–5 were correct, the region boundaries in the figures would be wrong if any quoted theorem from [1] is false or has hidden hypotheses. I also considered the proof of Lemma 2.9, where the newly added vertex c has second-neighbor set exactly A′ in the displayed construction, so the claimed strict inequality |N^2_A(c)| < z is not established; however, a small perturbation of the weights on A and A′ appears to repair this gap, so I do not treat it as the primary concern. The paper contains no machine-checked proof and no independent verification of [1], so a conditional verdict is appropriate rather than acceptance or rejection.","tokens_in":22231,"tokens_out":37064,"duration_ms":349979,"concrete_test":"Obtain [1] and independently re-derive Theorem 2.7 (the rotating equivalence) and Theorem 2.2 from the definitions of φ and ψ; then check every invocation in this paper, especially the uses of 2.7 in 4.3 and 4.4 and of 2.8 in 4.4, against the exact hypotheses of those theorems. If any quoted theorem is false or requires an extra condition, the corresponding region classification in Sections 3–5 must be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's threshold classifications in Figures 1–3 depend on a large block of results imported without proof from the companion paper [1]: Theorems 1.1–1.6 and 2.2–2.8, including the rotating equivalence 2.7. These are not marginal; they are used directly in the new arguments, e.g. 2.9–2.12, and then again in the Section 3–5 theorems such as 3.7, 3.9, 3.10, 4.3, 4.6, and 5.3. The introduction itself states that most of it is taken word-for-word from [1], and [1] is only listed as submitted. No independent proof or verification of 2.2, 2.7, or 2.8 is supplied here. If any of these quoted statements has a missing hypothesis or a wrong inequality, the claimed regions for ψ and φ at the levels 3/4, 2/5, and 3/5 would not follow as drawn. Thus the central claim is only as secure as an external manuscript whose exact hypotheses are not re-examined in this paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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].","tokens_in":22417,"tokens_out":13162,"duration_ms":111317,"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":[{"comment":"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.","section":"§2, §3–§5"},{"comment":"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.","section":"§4.2"},{"comment":"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.","section":"§3.3"},{"comment":"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.","section":"§4.6"}],"minor_comments":[{"comment":"In the proof, 'Choose X3 ⊂ N(V3)' should read 'N(v3)'.","section":"§3.8"},{"comment":"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.","section":"§3.2"},{"comment":"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.","section":"§2.10–§2.11"},{"comment":"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.","section":"§3.9"}],"recommendation":"major_revision","confidential_remarks":"Given the heavy dependence on the unpublished companion paper, I recommend that the revision be evaluated together with [1], or that proofs of the imported results be appended so that the referee can verify the conditional claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Patrick, if you work on this concatenation problem, this paper is worth a look. It takes the program from Chudnovsky–Hompe–Scott–Seymour–Spirkl and adds threshold analyses for 3/4, 2/5, and 3/5, with figures showing where psi and phi sit above or below those levels. The new content is real: Lemma 2.1 and the transformation lemmas 2.9–2.12 are original tools that let the author transfer bounds from known points to new regions, and the lower-bound constructions in Sections 3–5 are detailed and mostly convincing. The paper is also transparent about what is borrowed. It says plainly that most of the introduction is taken word-for-word from [1] and lists the unproved results it uses.\n\nThe main soft spot is the reliance on [1], which is only submitted. Theorems 2.2–2.8 and 1.1–1.6 are quoted without proof, and they are not marginal: the rotating equivalence 2.7 and the bounds from 2.2 are used directly in the new theorems. If any of those has a missing hypothesis, the region boundaries in Figures 1–3 shift. That is not a defect in the author's arguments, but it makes the paper's central claims conditional on an external manuscript. A referee should have access to [1], and the final version should either include the needed proofs or wait until [1] is accepted.\n\nThere are also a few formulas that look mistyped. In 3.3, the expression '(3x−1)/(12−12y−4)' appears twice, and the denominator is strange for y > 1/2; it may be a typo for something like 12(1−y). In 4.2, the theorem says 'x + y/(10(1−2y)) ≥ 2/5' but the proof uses 3/4 instead. These are small fixes, but they matter because the surrounding inequalities are tight.\n\nI did not find a load-bearing flaw in the new mathematics. The casework in 3.2, 3.3, and 3.4 is heavy, but the strategy is coherent and the derivations are plausible. The paper is honest, serious work.\n\nWho is it for? Specialists in extremal graph theory who care about these two functions. A general reader can skip it, but for someone working on concatenation it advances a specific program.\n\nRecommendation: send it to a referee. It deserves serious engagement, conditional on access to the companion and cleanup of the typos. If [1] is not available, I'd ask the author to include the quoted results as an appendix or wait.","headline":"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.","tokens_in":22945,"tokens_out":3717,"would_cite":false,"duration_ms":32026,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["bipartite graph concatenation","phi and psi functions","extremal graph theory","tripartitions","two-edge paths","threshold regions","rotating equivalence","weighted gadgets"],"falsifier":"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.","tokens_in":22007,"feed_emoji":"📐","tokens_out":7361,"duration_ms":62032,"temperature":0.7,"pith_summary":"The paper studies two numbers $\\phi(x,y)$ and $\\psi(x,y)$ attached to tripartitions of graphs: the guaranteed proportion of one part, $A$, that some vertex in an opposite part, $C$, can reach by two-edge paths, given that vertices in earlier parts have specified minimum degrees. Earlier work established which $(x,y)$ make these guarantees at least $1/2$, $2/3$, or $1/3$. This paper pushes the same question to the thresholds $3/4$, $2/5$, and $3/5$, and claims that in each case the unit square splits into regions, shown in Figures 1 through 3, where the guarantee holds and where it fails. The regions are cut out by explicit polynomial inequalities and straight boundary segments, with the upper-bound side witnessed by explicit biconstrained graphs. If the companion results quoted without proof are correct, the new theorems give the complete picture at these three levels.","feed_headline":"Proved: three new threshold regions for phi and psi","feed_subtitle":"The paper pinpoints where a C-vertex must reach 75%, 40%, or 60% of A in two steps.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the definitions of $\\phi$ and $\\psi$, the foundational results 1.1 through 1.6 and 2.2 through 2.8 including the rotating equivalence 2.7, and the earlier threshold analysis for $1/2$, $2/3$, and $1/3$ which this paper extends.","marker":"[1]"}],"fun_headline_variants":["New thresholds: when bipartite concatenation forces 75%, 40%, 60% reach","Exact regions for phi and psi at 3/4, 2/5, 3/5 thresholds","Bipartite graph concatenation: precise bounds for three new values","Where phi and psi hit 3/4, 2/5, 3/5: full characterization","Solving phi and psi thresholds: 3/4, 2/5, 3/5 on the unit square"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["New thresholds: when bipartite concatenation forces 75%, 40%, 60% reach","Exact regions for phi and psi at 3/4, 2/5, 3/5 thresholds","Bipartite graph concatenation: precise bounds for three new values","Where phi and psi hit 3/4, 2/5, 3/5: full characterization","Solving phi and psi thresholds: 3/4, 2/5, 3/5 on the unit square"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000775,"raw_usage":{"total_tokens":3510,"prompt_tokens":1111,"completion_tokens":2399,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":727,"completion_tokens_details":{"reasoning_tokens":2272}},"tokens_in":727,"tokens_out":2399,"duration_ms":14985,"temperature":1.0,"reasoning_tokens":2272,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:40:38.499679+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Chudnovsky, P","cited_arxiv_id":null,"evidence_quote":"Supplies the definitions of $\\phi$ and $\\psi$, the foundational results 1.1 through 1.6 and 2.2 through 2.8 including the rotating equivalence 2.7, and the earlier threshold analysis for $1/2$, $2/3$, and $1/3$ which this paper extends."}],"review_version":1}