{"id":"2bb4a792-9aa0-41b6-acac-03ce746b1d50","arxiv_id":"2608.01870","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An explicit family of 0/1-polytopes is constructed whose graphs have exponentially small edge expansion, disproving the Mihail-Vazirani conjecture.","lead":"A new family of high-dimensional 0/1-polytopes is constructed whose 1-skeleton edge expansion shrinks exponentially with dimension. This disproves the Mihail-Vazirani conjecture, a long-standing open problem in combinatorial optimization, and its polynomial weakening.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the construction and proof are internally sound.","rationale":"The paper's central claim is that the explicit 0/1-polytopes P_n have edge expansion at most 4nβ^n/(1−β^n), which is exponentially small. I checked each step of the proof in detail. The only steps that could plausibly fail are the cross-layer edge preservation of active-block sets and the boundary count in Lemma 13. Both are correct. The compatibility relation R contains exactly the five pairs achievable by a common linear functional, and each pair preserves the zero/nonzero pattern, so cross-layer edges cannot cross the cut S_n. The boundary count is also correct: a same-layer edge crossing S_n must change the profile from (r,r) to (r−1,r) or (r,r+1), and the multiplicities for the lower and upper layers are properly counted, yielding (3). The diagonal sum bound is valid, and the dimension conversion to exp(−c·dim) is straightforward. I find no internal inconsistency or hidden assumption. The reader's weakest-assumption identification (Lemma 11) is indeed the most delicate point, but it withstands scrutiny. Thus no change to the verdict is needed.","tokens_in":8879,"tokens_out":12076,"duration_ms":111368,"concrete_test":"Write a brute-force verifier for n=1 and n=2 (e.g., in Python): generate all vertices of P_n from C^n×D^n and D^n×C^n, enumerate all edges using the characterizations in Lemma 8 and Corollary 10 (or by testing all pairs of vertices for being an edge via linear programming), construct S_n = {u : |I(u)| < |J(u)|}, and compute |δ(S_n)| exactly. Confirm that for n=1,2 the boundary count equals Σ_{r=0}^n A_{r,r}(4(n−r)+5r/3) and that |S_n| matches 12^n − Σ A_{r,r}. This independently validates the two most delicate counting steps without relying on the paper's hand-proofs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After careful re-derivation, I find no load-bearing flaw in the paper's central argument. The most delicate steps are (i) the cross-layer edge characterization via the compatibility relation R (Lemma 9, Corollary 10), (ii) the active-block set invariance and connectivity of each V_{K,L} (Lemma 11), and (iii) the boundary count for the cut S_n (Lemma 13). All three check out. The compatibility pairs in R indeed preserve zero/nonzero status blockwise, so cross-layer edges cannot cross the cut S_n. The connectivity proof for V_{K,L} is terse but valid: every lower-layer vertex can be transformed to the canonical vertex by changing one active block at a time through a compatible upper-layer intermediate, and every upper-layer vertex has a compatible lower neighbor. The boundary count correctly identifies that a same-layer boundary edge must have exactly one endpoint with diagonal profile (r,r) and the other with profile (r−1,r) or (r,r+1); the per-vertex counts (2/3 for deactivating a C-block, 2 for activating a D-block, etc.) are accurate, giving the formula in (3). The Cauchy–Schwarz bound on the diagonal sum is a simple (Σx_r)^2 ≥ Σx_r^2 application and yields β = (1+√6)^2/12 < 1. Thus the exponential decay bound in Theorem 14 follows. The AI-generated statement is disclosed and does not affect the mathematics. I therefore agree with the reader's ACCEPT verdict.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper gives an explicit construction of full-dimensional 0/1-polytopes (P_n) in dimension 4n+1 whose 1-skeleta have exponentially small edge expansion. The polytope is P_n = conv(C^n × D^n × {0} ∪ D^n × C^n × {1}), where C={0,1}^2 and D={0,e1,e2}. The proof classifies all edges: same-layer edges are Cartesian-product edges (Lemma 8), and cross-layer edges are governed by a five-pair compatibility relation R (Lemma 9, Corollary 10). It then defines S_n = {u: |I(u)|<|J(u)|} using active-block sets, proves each V_{K,L} is a connected component of the cross-layer graph (Lemma 11), and shows that the edge boundary of S_n is counted exactly by the diagonal profiles (Lemma 13). Combined with the Cauchy-Schwarz bound on the diagonal binomial sum, this yields h(G(P_n)) ≤ 4n β^n/(1-β^n) with β=(1+√6)^2/12<1, hence h<1 and exponential decay in dim(P_n). Since dim(P_n)=4n+1, this disproves the Mihail-Vazirani conjecture in full generality.","tokens_in":9140,"tokens_out":16298,"duration_ms":178983,"significance":"This is a significant resolution of a longstanding open problem. The construction is simple and fully explicit; the proof is self-contained and has no fitted parameters. The derived bound is quantitative, including an explicit exponential decay constant. I independently checked the three delicate steps: the compatibility relation, the connectivity/invariance of V_{K,L}, and the boundary count in Lemma 13; all are valid. The result also rules out inverse-polynomial lower bounds for general 0/1-polytopes. The paper is well-written and the related-work discussion is accurate.","major_comments":[],"minor_comments":[{"comment":"The connectivity argument is terse but valid. I recommend expanding it by explicitly noting that in every unchanged block the chosen compatible partner is 00 for an inactive block and nonzero for an active block, so the intermediate upper-layer vertex indeed lies in the same V_{K,L}; and that first-group changes between 10 and 01 are realized in two steps via 11. This would remove a common source of reader hesitation.","section":"Section 3, Lemma 11"},{"comment":"The boundary count is correct, but the sentence 'Starting from this diagonal endpoint' may confuse because the diagonal endpoint is the outside endpoint of the boundary edge. A short clarification that the inside endpoint has profile (r-1,r) or (r,r+1) would improve readability.","section":"Section 4, Lemma 13"},{"comment":"The disclosure that the construction was generated with GPT-5.6 Sol is transparent and the author states that the proof was independently verified. This does not affect mathematical correctness, but the editor should ensure it complies with the journal's AI-use policy.","section":"Introduction, Statement of AI use"}],"recommendation":"accept","confidential_remarks":"The paper is technically sound and, in my view, publishable. The only editorial matter is the AI-use statement at the end of the Introduction; the author should be asked to confirm that the manuscript's authorship and disclosure meet the journal's policy. The construction's simplicity might invite scrutiny, but I found no gap."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things: the construction is genuinely simple—a Cayley sum of products of squares and triangles—and the proof is airtight as far as I can tell. The paper answers a long-standing open question by showing 0/1-polytopes can have exponentially small edge expansion.\n\nThe novelty is real. Previous negative evidence was half-integral (Cardinal–Pournin) or only about vertex expansion (Kwok–Lau–Tung). Here the main theorem gives explicit full-dimensional 0/1-polytopes P_n with h(G(P_n)) ≤ 4n β^n/(1−β^n), β=(1+√6)^2/12<1. I re-derived the key steps: the one-block compatibility relation R (Lemma 9), the cross-layer edge characterization (Corollary 10), the invariant that cross-layer edges preserve active-block sets (Lemma 11), and the boundary count (Lemma 13). All check out. The boundary count correctly identifies that boundary edges are exactly those with one diagonal endpoint and one off-diagonal endpoint, and the per-vertex counts are right. The Cauchy–Schwarz step on the diagonal sum is straightforward and yields the exponential decay.\n\nSoft spots are minor. Lemma 11's connectivity argument is terse but valid: you can move any lower-layer vertex to the canonical one by changing one active block through a compatible upper-layer partner, and every upper vertex has a lower neighbor. Lemma 8 is stated only for same-layer edges, which is fine because cross-layer edges are handled separately. The AI-generation statement is disclosed and the author says the proof was independently verified; my own check agrees. The paper only presents the m=2 case, though the remark about general m suggests a sharper constant is possible; that doesn't affect the disproof. The related-work section looks accurate.\n\nThis paper is for anyone working on 0/1-polytopes, edge expansion, or Markov-chain sampling. It is also a nice example of a minimal counterexample construction. I would bring it to a reading group and would cite it.\n\nMy recommendation: send it to peer review. It deserves a serious referee, and I expect acceptance after minor clarifications of the terse parts.","headline":"Clean, self-contained counterexample to the Mihail–Vazirani conjecture; core lemmas hold under inspection.","tokens_in":9627,"tokens_out":1312,"would_cite":true,"duration_ms":15139,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52B11","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new family of 0/1-polytopes has edge expansion decaying exponentially in dimension, disproving the Mihail–Vazirani conjecture.","keywords":["edge expansion","Cheeger constant","0/1-polytope","Mihail–Vazirani conjecture","Cayley sum","active-block invariant","polytope graph"],"falsifier":"Exhaustively test Lemma 9: for each of the 12 pairs (c,d)∈C×D, decide whether some w∈R^2 uniquely maximizes over C at c and over D at d. The paper claims exactly the five pairs in R; a single counterexample outside R would break the active-block invariant and hence the boundary estimate. Independently, for n beyond the threshold (4n+1)β^n<1, evaluating |δ(S_n)|/|S_n| from the explicit formulas should confirm the exponential bound.","tokens_in":8739,"feed_emoji":"📉","tokens_out":6557,"duration_ms":64682,"temperature":0.7,"pith_summary":"The paper constructs a family of full-dimensional 0/1-polytopes P_n whose graph edge expansion h(G(P_n)) is at most 4n β^n/(1−β^n), where β=(1+√6)^2/12<1. Since dim(P_n)=4n+1, this decays exponentially in the dimension, so h<1 for all large n. That contradicts the Mihail–Vazirani conjecture, which asserted that every 0/1-polytope has edge expansion at least 1. The construction is a Cayley sum of two Boolean layers, X_n=C^n×D^n and Y_n=D^n×C^n with C={0,1}² and D={0,e1,e2}; the cut S_n={|I(u)|<|J(u)|} has a boundary consisting only of same-layer edges because cross-layer edges preserve the active-block sets. The entire estimate reduces to bounding a diagonal binomial sum by (1+√6)^{2n}.","feed_headline":"0/1-polytopes break the Mihail–Vazirani expansion conjecture","feed_subtitle":"Explicit Cayley-sum polytopes give edge expansion ≤ 4n β^n, exponentially small in dimension, so the conjecture fails.","key_machinery":"Key machinery: the Cayley sum P_n = X_n ∗ Y_n, i.e., conv((X_n×{0}) ∪ (Y_n×{1})) with X_n=C^n×D^n and Y_n=D^n×C^n, together with the one-block compatibility relation R={(00,00),(10,10),(01,01),(11,10),(11,01)}⊆C×D that exactly characterizes which cross-layer segments are edges. The active-block sets I(u), J(u) record which blocks are nonzero; Lemma 11 shows they are invariant along every cross-layer edge, so the cut S_n={|I|<|J|} has no cross-layer boundary. The boundary computation converts the expansion ratio into the diagonal binomial sum Σ_r binom(n,r)^2 6^r, bounded by 12^n β^n, which gives the exponential decay.","core_discovery":"The central claim is Theorem 1: there exist c>0 and an infinite sequence of full-dimensional 0/1-polytopes with dim(P_n)→∞ such that h(G(P_n))≤exp(−c dim(P_n)). The proof gives the explicit bound h(G_n)≤4n β^n/(1−β^n) with β=(1+√6)^2/12, which is below 1 once (4n+1)β^n<1. The polytope is P_n = conv((C^n×D^n)×{0} ∪ (D^n×C^n)×{1}), with C={0,1}² and D={0,e1,e2}. The graph-theoretic heart is a cut S_n containing all vertices whose second-group active-block count exceeds their first-group count; cross-layer edges never leave S_n because every compatible block pair in the relation R matches zero with zero and nonzero with nonzero. Counting same-layer boundary edges gives a diagonal binomial sum t","pith_inferences":["Following the paper's remark, the same layered construction with C={0,1}^m and D={0,e1,...,em} likely yields a sharper decay rate; computing the analogue of the diagonal sum would make this explicit.","The active-block invariant suggests a general recipe: any Cayley sum whose cross-layer adjacency relation preserves a monotone statistic will have a cut with only same-layer boundary, potentially yielding other small-expansion polytopes.","The contrast with the random-polytope results cited in the paper points to a sharp worst-case versus typical-case separation: expansion is not guaranteed by the class of 0/1-polytopes, only typical in random models."],"forward_implications":["The Mihail–Vazirani conjecture is false: no constant lower bound holds for all 0/1-polytopes.","The weaker inverse-polynomial version is also false, since the expansion can be exponentially small in the dimension.","Random-walk and Markov-chain sampling algorithms that require expansion at least one cannot be justified unconditionally for all 0/1-polytopes.","The bound is explicit: h(G_n)≤4n β^n/(1−β^n) with β=(1+√6)^2/12, so the failure is quantitative, not just qualitative.","Full-dimensionality shows the counterexample is not an artifact of degenerate low-dimensional embedding."],"fun_headline_variants":["Counterexample to Mihail-Vazirani: 0/1-polytopes with tiny edge expansion","Edge expansion of 0/1-polytopes shrinks exponentially, disproving conjecture","Explicit 0/1-polytopes disprove Mihail-Vazirani edge expansion bound","Mihail-Vazirani fails: 0/1-polytope family has exponentially small expansion"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The construction's validity hinges on Lemma 11, which claims that cross-layer edges preserve the active-block sets—i.e., a block is nonzero in one layer exactly when the matching block is nonzero in the other; if any compatible pair violated this zero/nonzero matching, the cut's boundary would gain cross-layer edges and the exponential bound would break.","fun_headline_variants_meta":{"raw":{"variants":["Counterexample to Mihail-Vazirani: 0/1-polytopes with tiny edge expansion","Edge expansion of 0/1-polytopes shrinks exponentially, disproving conjecture","Explicit 0/1-polytopes disprove Mihail-Vazirani edge expansion bound","Mihail-Vazirani fails: 0/1-polytope family has exponentially small expansion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001083,"raw_usage":{"total_tokens":4309,"prompt_tokens":631,"completion_tokens":3678,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":375,"completion_tokens_details":{"reasoning_tokens":3579}},"tokens_in":375,"tokens_out":3678,"duration_ms":28837,"temperature":1.0,"reasoning_tokens":3579,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T19:14:46.653322+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively test Lemma 9: for each of the 12 pairs (c,d)∈C×D, decide whether some w∈R^2 uniquely maximizes over C at c and over D at d. The paper claims exactly the five pairs in R; a single counterexample outside R would break the active-block invariant and hence the boundary estimate. Independently, for n beyond the threshold (4n+1)β^n<1, evaluating |δ(S_n)|/|S_n| from the explicit formulas should confirm the exponential bound.","supporting_citations":[],"review_version":1}