{"id":"2361b6d4-4e38-4c84-87ba-8b6268cc4603","arxiv_id":"2506.23989","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Boolean matrices with bounded γ2-norm or normalized trace norm contain linear-sized homogeneous submatrices, and graphs with near-minimal MaxCut contain a large clique.","lead":"This paper proves that Boolean matrices with bounded factorization norm must contain a large all-ones or all-zeros submatrix, confirming a conjecture from communication complexity. It also shows that graphs whose maximum cut is barely above a random cut must contain a large clique, giving an inverse theorem for MaxCut.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7.1's proof contains a false step: e(G1) ≥ d0|A1|/2 fails on a star-like bipartite graph, leaving Theorem 1.5 and its corollaries unsupported; Theorems 1.1 and 1.7 are not affected.","rationale":"The reader's weakest_assumption focused on Lemma 9.4 and Lemma 7.4. I find that Lemma 9.4's proof has a harmless factor-of-2 typo that preserves the Ω(E) conclusion, and Lemma 7.4 is an unpublished black box affecting only Theorem 1.6. The truly load-bearing issue I identified is a different one: the proof of Lemma 7.1 contains a concrete false inequality (e(G1) ≥ d0|A1|/2), which fails on a simple star-like bipartite graph. This gap affects Theorem 1.5 and its corollaries (Theorems 1.6 and 2.4), but not the central HHH conjecture (Theorem 1.1) or the MaxCut inverse theorem (Theorem 1.7), which are the paper's headline results. Since the central theorems appear sound and the secondary results have a fixable proof gap, the CONDITIONAL verdict is unchanged; the concern reinforces the need for revision but does not move the verdict. My disagreement with the reader is because the specific weakest assumption differs: the reader did not flag the Lemma 7.1 proof gap.","tokens_in":25852,"tokens_out":64782,"duration_ms":549859,"concrete_test":"Verify Lemma 7.1 on the explicit star-like construction: let N be large, define a bipartite graph with parts A = {a_1,...,a_N,c} and B = {b_1,...,b_N}, with edges exactly c-a_i and c-b_j for all i,j. Compute the maximum average degree d0 of any induced subgraph (it is ≈2 for the whole graph). Then check whether the proof's claim e(G1) ≥ d0|A1|/2 holds: with C = {c}, A1 = {a_1,...,a_N}, the induced subgraph on A1 ∪ B has no edges, so the claim fails. Then check whether Lemma 7.1's statement still holds by searching for a submatrix with average degree at least d0/3 and one side with degree at most six times its average degree (the 1×1 submatrix {c}×{b_1} should work). A correct proof of Lemma 7.1 or a counterexample to the lemma will settle whether Theorem 1.5 can be repaired.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 7, the proof of Lemma 7.1 claims that after removing high-degree vertices C from the larger part A0, the induced subgraph G1 on A1 ∪ B0 satisfies e(G1) ≥ d0|A1|/2, where d0 is the average degree of the maximum-average-degree subgraph G0. This bound is unjustified and is in fact false: take a bipartite graph with parts A1 = {a_1,...,a_N}, C = {c}, B0 = {b_1,...,b_N}, and edges from c to every vertex in A1 ∪ B0, with no other edges. For this graph, G0 = the whole graph has average degree d0 = 4N/(2N+1) ≈ 2, and C = {c} is the only vertex with degree > 2d0, so A1 has size N. But G1 = G0[A1 ∪ B0] has no edges, so e(G1) = 0, while d0|A1|/2 ≈ N > 0. Thus the stated lower bound fails. The lemma itself may still be true (a single edge (c,b_1) satisfies its conclusion), but the proof as written does not establish it. Since Lemma 7.1 is the first step in the proof of Theorem 1.5, which is then used to prove Theorem 1.6 and Theorem 2.4, this is a load-bearing gap for those results. It does not affect the main conjecture Theorem 1.1 or the MaxCut inverse theorem Theorem 1.7, whose proofs do not rely on Lemma 7.1. The Factor-2 slip in Lemma 9.4 (where ∑_{edges} ⟨x_a,x_b⟩ is written as ⟨A,M'⟩ instead of ⟨A,M'⟩/2) weakens the constant from E/(2π) to E/(4π) but does not change the Ω(E) conclusion, so it is not load-bearing.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops structural results for Boolean matrices with bounded gamma_2-norm. Theorem 1.1 asserts that an m x n Boolean matrix with gamma_2(M) <= gamma contains a delta_1 m x delta_2 n all-zero or all-one submatrix with delta_1, delta_2 >= 2^{-O(gamma^3)}, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. Corollary 1.2 extends this to bounded normalized trace norm, Corollary 1.3 handles integer matrices, and Theorem 1.4 gives a matching construction. The paper also proves that four-cycle-free Boolean matrices satisfy gamma_2(M) = Theta(sqrt(d)) where d is the degeneracy (Theorem 1.5), derives a Zarankiewicz-type consequence (Theorem 1.6), and proves an inverse theorem for MaxCut: if a graph with m edges has surplus at most alpha sqrt(m), then it contains a clique of size 2^{-O(alpha^9)} sqrt(m) (Theorem 1.7). The proofs combine matrix factorization, discrepancy sparsification, spectral arguments, and a semidefinite-programming-based energy bound for MaxCut.","tokens_in":26279,"tokens_out":27118,"duration_ms":271247,"significance":"If the central claims hold, the paper resolves a conjecture of Hambardzumyan, Hatami, and Hatami and gives the first inverse theorem for MaxCut in the near-minimal regime, a substantial result in extremal graph theory. The main derivations in Sections 5 and 9 are coherent and proceed from first principles, with explicit quantitative bounds and no fitted parameters. The paper also gives a tight construction and connects the results to communication complexity, operator theory, discrepancy theory, and spectral graph theory. However, the proof of Theorem 1.5 currently rests on a false step in Lemma 7.1, and Theorem 1.6 depends on an unpublished lemma from overlapping authors; these issues affect the supporting structural claims but not the main Theorem 1.1 or the MaxCut inverse theorem.","major_comments":[{"comment":"The proof of Lemma 7.1 contains a false step. After deleting the high-degree set C from the larger part A0, the paper claims that the induced subgraph G1 on A1 union B0 satisfies e(G1) >= d0 |A1|/2. This is unjustified and is false in general. For example, take A1 = {a_1,...,a_N}, C = {c}, B0 = {b_1,...,b_N}, with edges from c to every vertex in A1 union B0 and no other edges. Then G0 is the whole graph, with average degree d0 = 4N/(2N+1), and C is the only vertex of degree larger than 2d0, so A1 has size N. But G1 = G0[A1 union B0] has no edges, while d0|A1|/2 is about N. Thus e(G1) >= d0|A1|/2 fails. Since Lemma 7.1 is the first step in the proof of Lemma 7.2, which establishes the lower bound in Theorem 1.5, the proof of Theorem 1.5 is incomplete as written. Consequently Theorems 1.6, 2.2, and 2.4, which rely on Theorem 1.5 or 1.6, are also unsupported until this lemma is repaired. The lemma itself may be true, but the current argument does not prove it.","section":"7, Lemma 7.1"},{"comment":"Theorem 1.6 depends on Lemma 7.4, which is cited to an unpublished manuscript 'in preparation' by Hunter, Milojevic, Sudakov, and Tomon. The lemma is used as a black box and is load-bearing: without it, the proof of Theorem 1.6 does not go through. Since one of the authors of the current paper is also an author of the cited unpublished work, the manuscript should either include a proof of Lemma 7.4, cite a public version with a verifiable statement, or explicitly mark Theorem 1.6 (and Theorem 2.4, which uses it) as conditional on an external result. This is not a concern for Theorem 1.1 or Theorem 1.7, whose proofs do not use Lemma 7.4.","section":"7, Lemma 7.4 and Theorem 1.6"}],"minor_comments":[{"comment":"In the induction step, the displayed inequality 'gamma_2(M_{i+1}) < gamma_2(M_{i+1}) - c/gamma_2(M_{i+1})' is self-referential; it should read 'gamma_2(M_{i+1}) < gamma_2(M_i) - c/gamma_2(M_i)'. The subsequent 'gamma(M_i)' should also be 'gamma_2(M_i)'.","section":"5, Proof of Theorem 5.2"},{"comment":"In the proof of Corollary 1.2, the phrase 'for some t/m, u/m >= 2^{-O(gamma^3)}' should read 't/m, u/n >= 2^{-O(gamma^3)}'.","section":"5, Proof of Corollary 1.2"},{"comment":"In the computation of the expected cut size, sum over edges of <x_a,x_b> equals <A,M'>/2, not <A,M'>, because each edge contributes once but the Frobenius inner product sums over ordered pairs. The displayed expression is therefore missing a factor of 1/2. This changes the constant from E(G)/(2pi) to E(G)/(4pi) in the lower bound sp(G) >= E(G)/(2pi) - O(n), but the conclusion sp(G) = Omega(E(G)) is unaffected because Lemma 9.3 supplies the additional term sp(G) = Omega(n).","section":"9, Lemma 9.4"},{"comment":"In the final part of Case (c), the sentence 'then V_J has at least n_J/(4 gamma^2) columns' should refer to the submatrix V' of V_I, not to V_J. The notation is confusing as written.","section":"5, Lemma 5.3, Case (c)"},{"comment":"When Lemma 4.4 is applied to J - B, the resulting submatrix B' should be explicitly described as the corresponding submatrix of B, not of J - B, to avoid ambiguity in the sentence 'we can find such a submatrix B''.","section":"9, Proof of Theorem 9.1"}],"recommendation":"major_revision","confidential_remarks":"The main theorems, Theorem 1.1 and Theorem 1.7, appear sound based on the coherent arguments in Sections 5 and 9. The false step in Lemma 7.1 is serious for the supporting structural results, but it is localized and may be repairable; the reliance on the unpublished Lemma 7.4 is also a concern that the editor may wish to have addressed. I do not see grounds for rejection, but the paper should not be accepted with these gaps in the stated Theorems 1.5 and 1.6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is my read of Balla–Hambardzumyan–Tomon. The headline: the main conjecture (Theorem 1.1) and the MaxCut inverse theorem (Theorem 1.7) look right, modulo small typos, and are significant. But there is a real gap in the proof of Lemma 7.1 that the authors seem to have missed. As written, that lemma's proof fails, and Theorem 1.5, 1.6, and 2.4 are not established by the arguments given.\n\nWhat is good: Theorem 1.1 answers a conjecture of [HHH23] with exponential-type bounds, and the corollary for normalized trace norm (Corollary 1.2) is a nice bonus. Theorem 1.7 is a striking inverse theorem for MaxCut; the proof via trace norm plus the sparsification machinery (Lemmas 4.1–4.4 and 5.3) seems coherent. The four-cycle-free estimate (Theorem 1.5) would be a genuine advance if the proof goes through. The paper is generally well-written and the main derivations in Sections 5 and 9 are legible.\n\nThe problem: in Lemma 7.1, the proof asserts that after removing high-degree vertices C from the larger part A0, the induced subgraph on A1 ∪ B0 has e(G1) ≥ d0|A1|/2. That is false; a star centered in C has no edges between A1 and B0. The lemma may be salvageable—the conclusion holds for the star by taking a single edge—but the current argument does not establish it. Since Lemma 7.1 is the first step in Lemma 7.2 and hence Theorem 1.5, that part of the paper is currently unsupported. The stress-test note is correct on this.\n\nOther soft spots: Theorem 1.6 depends on Lemma 7.4, an unpublished result from [HMST]. That is a black box and should be either proved or cited to a public version. There are also minor typos: the self-referential inequality in the proof of Theorem 5.2 (should be γ2(M_{i+1}) ≤ γ2(M_i) − c/γ2(M_i)), and the factor of 2 in Lemma 9.4's expectation calculation, which weakens E(G)/(2π) to E(G)/(4π) but does not affect the Ω(E) conclusion.\n\nVerdict: conditional. The main theorems (1.1 and 1.7) are likely correct and significant. Theorem 1.5 and its corollaries need a repaired proof of Lemma 7.1, plus a resolution of the unpublished dependency. This paper deserves a serious referee—the stakes are high and the core ideas are strong. I would send it to review, with instructions to ask for a corrected treatment of Section 7.","headline":"Strong main results (Theorem 1.1 and the MaxCut inverse theorem) but a genuine gap in Lemma 7.1's proof currently leaves Theorem 1.5 and its corollaries unsupported.","tokens_in":26779,"tokens_out":17540,"would_cite":true,"duration_ms":160931,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C50","15A23","15A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that every Boolean matrix with bounded $\\gamma_2$-norm contains a linear-sized all-zeros or all-ones submatrix, and derives an inverse theorem for MaxCut: graphs with near-minimal maximum cut must contain a clique of size…","keywords":["$\\gamma_2$-norm","factorization norm","MaxCut","inverse theorem","Boolean matrices","trace norm","monochromatic submatrix","graph energy"],"falsifier":"Calculate the surplus-to-energy ratio $\\mathrm{sp}(G)/E(G)$ for a growing family of graphs with no isolated vertices, for instance random regular graphs of increasing degree; Lemma 9.4 predicts this ratio is bounded below by a universal constant, so any sequence with the ratio tending to zero would falsify the inverse MaxCut theorem.","tokens_in":25677,"feed_emoji":"✂️","tokens_out":13026,"duration_ms":117018,"temperature":0.7,"pith_summary":"The paper proves that any Boolean matrix with $\\gamma_2$-factorization norm at most $\\gamma$ contains an all-zeros or all-ones submatrix whose dimensions are a constant fraction of the original, with the fraction at least $2^{-O(\\gamma^3)}$. This verifies a conjecture of [HHH23], and the same conclusion is shown to hold under the weaker hypothesis of bounded normalized trace norm. As a key application, the paper establishes an inverse theorem for MaxCut: if a graph with $m$ edges has maximum cut at most $m/2 + \\alpha\\sqrt{m}$, then it contains a clique of size $2^{-O(\\alpha^9)}\\sqrt{m}$. This is the first inverse theorem in the near-minimal regime, and it is tight up to the constant in the exponent.","feed_headline":"MaxCut near m/2 forces a clique of size √m","feed_subtitle":"If a graph's best cut beats random by only O(√m), it must still contain a clique of size Ω(√m).","key_machinery":"The key object is the $\\gamma_2$ factorization norm, defined as $\\gamma_2(M) = \\min_{M=UV} \\|U\\|_{\\mathrm{row}}\\|V\\|_{\\mathrm{col}}$, which measures how much a matrix action is distorted when factored through $\\ell_2$ and serves as a smooth surrogate for rank. The proof of the main structural result runs through an iterative sparsification lemma (Lemma 5.3): starting from a matrix of density at most $1/2$, it repeatedly finds a large submatrix whose $\\gamma_2$-norm drops by $\\Omega(1/\\gamma)$ per step, using \"brilliant\" rows and columns and orthogonal projection, until the submatrix is all-zero after $O(\\gamma^2)$ steps. For the MaxCut theorem, the load-bearing mechanism is the energy-surplus bound $\\mathrm{sp}(G) = \\Omega(E(G))$, proved by a hyperplane-rounding argument applied to a positive-semidefinite factorization of the adjacency matrix, together with the classical bound $\\mathrm{sp}(G) \\ge n/6$ that absorbs the linear error term; this converts a near-minimal MaxCut into a bound on the trace norm, enabling Corollary 1.2 to locate a large complete bipartite subgraph, from which Tur\\'an's theorem produces the clique.","core_discovery":"The central discovery is that the $\\gamma_2$ factorization norm is a structural parameter for Boolean matrices: a bounded $\\gamma_2$-norm forces a linear-sized monochromatic submatrix, with quantitative bound $\\delta_1,\\delta_2 \\ge 2^{-O(\\gamma^3)}$ in Theorem 1.1. The same structural conclusion follows from a bounded normalized trace norm (Corollary 1.2), and a construction shows the dependence cannot be improved below $2^{-O(\\gamma)}$ (Theorem 1.4). For four-cycle-free matrices, the paper proves $\\gamma_2(M) = \\Theta(\\sqrt{d})$ where $d$ is the degeneracy (Theorem 1.5), yielding a Zarankiewicz-type theorem (Theorem 1.6). On the MaxCut side, the proof shows that the surplus $\\mathrm{sp}(G) = \\mathrm{MaxCut}(G) - e(G)/2$ of any graph with no isolated vertices is at least a constant times the energy $E(G)$ (the trace norm of the adjacency matrix), improving a previous bound with a logarithmic loss (Lemma 9.4). Combining this energy-surplus inequality with the trace-norm corollary produces a complete bipartite subgraph of size $2^{-O(\\alpha^9)}\\sqrt{m}$, from which Tur\\'an's theorem yields the large clique (Theorem 1.7).","pith_inferences":["A natural extension beyond the paper is to ask whether the energy-surplus inequality $\\mathrm{sp}(G) = \\Omega(E(G))$ generalizes to hypergraph cuts, where an analogous trace norm of a tensor could play the role of energy.","The gap between the upper bound $2^{-O(\\gamma^3)}$ in Theorem 1.1 and the lower bound $2^{-O(\\gamma)}$ in Theorem 1.4 suggests that the true exponent may be closer to linear; tightening this gap would directly improve bounds for the approximate-$\\gamma_2$ version relevant to randomized communication complexity.","The MaxCut proof method, which routes through the trace norm of the adjacency matrix, may adapt to other cut-like optimization problems (for instance Max $k$-Cut or bisection) once a version of the energy-surplus bound is established for those objectives.","Theorem 1.6 and its corollaries such as Theorem 2.4 currently rely on the unpublished Lemma 7.4 used as a black box; a public proof of that lemma would remove the only conditional component from these consequences."],"forward_implications":["Any Boolean matrix with constant $\\gamma_2$-norm contains a linear-sized all-zeros or all-ones submatrix, removing the main structural barrier toward the randomized communication complexity conjecture of [CLV19, HHH23].","The same conclusion holds under the weaker hypothesis of constant normalized trace norm, so the result applies directly to adjacency matrices of graphs with small energy, including those arising in spectral graph theory.","Graphs with $m$ edges and MaxCut at most $m/2 + O(\\sqrt{m})$ contain a clique of size $\\Omega(\\sqrt{m})$, settling the clique case of the Alon\\,--\\,Krivelevich\\,--\\,Sudakov conjecture at the extreme end of the spectrum.","Four-cycle-free matrices have $\\gamma_2$-norm comparable to the square root of their degeneracy, giving sharp bounds for the hereditary discrepancy of geometric set systems such as point-line incidence matrices.","Graphs with smallest eigenvalue at least $-\\lambda$ contain cliques of size $\\Omega_\\lambda(d)$ where $d$ is the average degree, a strengthening that follows from the Zarankiewicz-type theorem."],"supporting_citations":[{"why":"Posed the conjecture that Boolean matrices with bounded $\\gamma_2$-norm contain a linear-sized all-zeros or all-ones submatrix, which Theorem 1.1 resolves.","marker":"[HHH23]"},{"why":"Introduced the $\\gamma_2$-norm into communication complexity and supplied the duality between cut-norm and $\\gamma_2^*$ via Grothendieck's inequality used in Lemma 4.1.","marker":"[LS09b]"},{"why":"Provided Claim 2.2, used as Lemma 4.2, which gives the halving sparsification step underlying Lemma 4.4.","marker":"[ST24]"},{"why":"Established the bound $\\mathrm{sp}(G) \\ge n/6$ for graphs with no isolated vertices, which absorbs the linear error term in Lemma 9.4.","marker":"[EGK97]"},{"why":"Supplied the hyperplane-rounding scheme that converts a positive-semidefinite factorization into a cut distribution, the core of the energy-surplus argument in Lemma 9.4.","marker":"[GW95]"},{"why":"Proved a weaker energy-surplus bound with a logarithmic factor and introduced the semidefinite-programming approach that Lemma 9.4 improves.","marker":"[RT25]"},{"why":"Lemma 7.4, used as a black box, is the graph-theoretic link between four-cycle-free $\\gamma_2$ bounds and dense subgraphs required for Theorem 1.6.","marker":"[HMST]"},{"why":"Tur\\'an's theorem converts the sparse complement of a dense bipartite subgraph into a large clique, the final step of the inverse MaxCut proof.","marker":"[Tur41]"}],"fun_headline_variants":["Small MaxCut surplus forces a large clique","MaxCut near m/2 implies clique of size √m","Inverse theorem: MaxCut surplus O(√m) forces clique Ω(√m)","Near-random MaxCut implies large clique"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The inverse MaxCut theorem rests on the new inequality that a graph's cut surplus is at least a constant fraction of its energy (the trace norm of the adjacency matrix); if that inequality fails for some family of graphs, the clique conclusion collapses.","fun_headline_variants_meta":{"raw":{"variants":["Small MaxCut surplus forces a large clique","MaxCut near m/2 implies clique of size √m","Inverse theorem: MaxCut surplus O(√m) forces clique Ω(√m)","Near-random MaxCut implies large clique"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000691,"raw_usage":{"total_tokens":3160,"prompt_tokens":1010,"completion_tokens":2150,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":2082}},"tokens_in":626,"tokens_out":2150,"duration_ms":15689,"temperature":1.0,"reasoning_tokens":2082,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:31:27.793354+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Calculate the surplus-to-energy ratio $\\mathrm{sp}(G)/E(G)$ for a growing family of graphs with no isolated vertices, for instance random regular graphs of increasing degree; Lemma 9.4 predicts this ratio is bounded below by a universal constant, so any sequence with the ratio tending to zero would falsify the inverse MaxCut theorem.","supporting_citations":[],"review_version":1}