{"id":"4c9f8539-e4d0-4ff7-b5d1-2b2197c208c4","arxiv_id":"2411.11627","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An explicit infinite family of biregular graphs is shown to have (3/5 - epsilon)-two-sided unique-neighbor expansion, the first to beat the spectral 0.5d barrier.","lead":"This paper constructs the first explicit bipartite graphs where every small set of vertices on both sides has about 0.6 times the degree distinct neighbors, beating the long-standing 0.5 barrier imposed by spectral methods. The construction combines the tripartite line product framework with Ramanujan clique complexes and new triangle-density estimates.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Omitted verification of the truncated base graph's special-set structure is load-bearing: Lemma 5.3 requires a fixed balanced partition of the gadget's right side, but Lemmas 3.10 and 3.18 never prove the common-neighborhood sets have this form.","rationale":"The paper's central idea is serious: instantiating the tripartite line product with vertex-face incidence of the Ramanujan clique complex is a natural way to improve the previous constant, and the triangle-density computations in Section 4 appear carefully derived and internally consistent. The spectral barrier claim would indeed follow if all structural hypotheses were met. The vulnerability is exactly where the reader located it: the special-set structure of the truncated base graph is asserted, not proved. In the full (untruncated) incidence graph, the special sets for a pair of parts are the fibers A_s parameterized by s in S_{b-a}, and these are disjoint and balanced. But Lemma 3.18 constructs the truncated graph by deleting entire equivalence classes, and no proof is given that the fibers A_s ∩ F remain nonempty, disjoint, and Θ(D/s)-sized. These properties are needed to apply Lemma 5.3, whose proof is tailored to a fixed balanced partition. Losing this step would break the multiplicity control in Lemma 2.16 and hence the unique-neighbor lower bound. I do not see a separate contradiction: the parameter asymptotics for k = 5 (DL = Θ(q^10), τ = O(q^6.5), λ = O(q^3), dL = Θ(q^3.25)) are compatible, and the omitted verification is plausibly a routine but substantial combinatorial check. The citation error noted by the reader ([HL22] where [LH22] is meant) is real but cosmetic. Since the reader's conditional verdict already reflects this gap, my stress-test does not move the verdict.","tokens_in":29099,"tokens_out":25503,"duration_ms":260400,"concrete_test":"For k = 5 and a large prime power q, take the full face-generator set F(S), fix b - a = 2, and define A_s = {σ in F(S) : id, s in σ} for s in S_2. Now form F by choosing D/j equivalence classes of size j as in Lemma 3.18, with D just below |F(S)|/k and divisible by j. Verify analytically or by exhaustive enumeration for a small q: (i) the nonempty sets A_s ∩ F are pairwise disjoint; (ii) each nonempty A_s ∩ F has size between D/(2s) and 2D/s, where s is the number of nonempty sets; (iii) at least q^4 nonempty sets exist. If (i)-(iii) hold, supply the omitted Lemma 3.10/3.18 verification; if any fails, Lemma 5.3 cannot be instantiated on the special sets and the e(C) bound in Lemma 2.16 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The middle-to-right analysis in Lemma 2.16 depends on Definition 2.8(1) being applied to the special sets from Definition 2.3(4): for u in M_a, the collision multiplicity toward M_b is charged to the blue/red edges landing in the sR(a,b) special sets. The only proof that random gadgets satisfy Definition 2.8(1) is Lemma 5.3, which is proved for a fixed balanced partition B = B1 ∪ ... ∪ Br of [D_R] with |Bi| between n2/(2r) and 2n2/r. The key distributional step, that sum_{i in W} |N(S) ∩ Bi| has the same law as |N(S) ∩ T| for a uniform T of size sum |Bi|, requires the Bi to be disjoint blocks; balancing is also needed for the stated tail bound. The paper never establishes either fact for the special sets of the truncated incidence graph. Lemma 3.10 is asserted with 'we omit the details,' and Lemma 3.18 says the structured-graph verification is 'straightforward verification that we omit.' In particular, no argument shows that after choosing F as a union of arbitrary equivalence classes, the nonempty common-neighborhood sets A_s ∩ F are pairwise disjoint, have sizes Θ(D/s), and number at least q^{k-1}. Thus Lemma 2.7's lower bound s ∈ [q^{k-1}, O(q^{floor(k^2/4)})] is unsupported. If these sets overlap or are badly unbalanced, Eq. (1) and the saturated-vertex argument in Lemma 2.16 lose the gadget pseudorandomness bound, and the claimed 3/5 unique-neighbor expansion does not follow from the written proof. This is a gap, not a demonstrated contradiction; the central construction may well be repairable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs explicit two-sided vertex expanders that break the 0.5d spectral barrier. Using the tripartite line product framework of Hsieh–McKenzie–Mohanty–Paredes, the authors instantiate the base graph with a truncated vertex-face incidence graph of the 4-dimensional Ramanujan clique complex, and prove new bounds on the triangle density of small sets in that complex. The main theorem states that for any target aspect ratio, there exist explicit families of (5dL,5dR)-biregular graphs with (3/5 − ε)-two-sided unique-neighbor expansion for large degrees. The proof combines a left-to-middle analysis using small-set triangle expansion with a middle-to-right collision analysis using skeleton expansion and a pseudorandom gadget.","tokens_in":29377,"tokens_out":11412,"duration_ms":102159,"significance":"If the proof is completed, this is a substantial breakthrough: it is the first explicit construction to exceed the 1/2 spectral barrier for two-sided vertex expansion, resolving a question implicit in Kahale's work. The construction is explicit and polynomial-time, and the triangle-density analysis of small sets in the Ramanujan clique complex (Section 4, especially Lemma 4.8 and Corollary 4.9) is a technically interesting contribution in its own right, potentially useful for other HDX-based constructions. The proof is mostly self-contained and the parameter choices for k=5 are carefully checked (dL,dR = Θ(q^3.25) lies between λ/δ and δD/τ). The main caveat is the unverified structured base-graph property, which the authors explicitly acknowledge as omitted; this omission is load-bearing for the main claim.","major_comments":[{"comment":"The paper asserts, but does not prove, that the (truncated) vertex–face incidence graph of the Ramanujan clique complex is a structured bipartite graph satisfying Definition 2.3. Lemma 3.10 says 'we omit the details' and Lemma 3.18 says the verification is 'straightforward verification that we omit.' This omission is load-bearing for the main theorem. Definition 2.8(1) requires the pseudorandom gadget to control the total number of neighborhood vertices landing in any union of the special sets A_i ⊆ [DR] from Definition 2.3(4). The only provided proof that a random gadget satisfies this bound (Lemma 5.3) is for an arbitrary fixed balanced partition B = B1 ∪ ... ∪ Br of [DR]; its key distributional step, that Σ_{i∈W} |N(S)∩Bi| has the same law as |N(S)∩T| for a uniform T of size Σ|Bi|, uses the disjointness of the Bi. Definition 2.3(4) does not assert that the special sets are pairwise disjoint, nor that they cover [D], nor that after truncation by F in Lemma 3.18 they remain disjoint and balanced with sizes Θ(D/s). Lemma 3.18 does not establish any of these facts. Consequently, Lemma 2.10 (existence of a good gadget) and the application of Eq. (1) in the proof of Lemma 2.16 are not justified for the special sets arising from the construction. The authors must supply the missing verification or replace Definition 2.8(1) with a condition that can be proved for the actual special sets.","section":"Section 3.2–3.3 (Lemmas 3.10 and 3.18), Definition 2.3(4), Definition 2.8(1), Lemma 5.3"}],"minor_comments":[{"comment":"The parameter r is not defined in Definition 2.8; it appears in the bound 'max{1/r · dL|S|, log D}'. The proof of Lemma 5.3 uses r for the number of blocks in a partition, but Definition 2.8 is stated before any partition is introduced. The intended identification r = sR(a,b) should be stated explicitly.","section":"Definition 2.8(1)"},{"comment":"The sentence 'We claim that there if a face f that contains m' contains a typo ('there if' should be 'that if').","section":"Lemma 3.18, proof"},{"comment":"The notation d_{ij} = [k/(j-i)k]_q is confusing; the subscript k appears misplaced. The intended Gaussian binomial coefficient should be written as [ k / ((j-i) mod k) ]_q, with the modular reduction made explicit.","section":"Section 4, notation"},{"comment":"Observation 2.13 would benefit from stating explicitly that the special sets are those for the pair (a,b) and that the multiplicity bound holds for every v ∈ M_b; as written the observation is too informal for a formal proof.","section":"Observation 2.13"}],"recommendation":"major_revision","confidential_remarks":"The omitted verification in Lemmas 3.10 and 3.18 is the single obstacle to accepting the main theorem as proven. If the special sets of the Ramanujan complex indeed form balanced disjoint partitions as required by Lemma 5.3, the paper is likely correct; the authors should be asked to provide a full proof. The paper's own admission of omitted 'straightforward verification' makes this a high-priority issue rather than a routine presentation fix. The result is significant and within the scope of math.CO."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the first explicit construction to break the 0.5d spectral barrier for two-sided vertex expanders, and it achieves (3/5 - epsilon) unique-neighbor expansion. That is a real milestone, and the paper is worth a serious look. The main new ingredient, the triangle-density bound for small sets in the Ramanujan clique complex (Lemma 4.8), is genuinely new and carefully argued. The parameter choices for k=5 are internally consistent.\n\nThe paper is built on the HMMP24 tripartite line product, but the base graph is the face-vertex incidence of the 4D Ramanujan complex, and the analysis exploits the special common-neighborhood structure of that complex. The left-to-middle analysis via triangle expansion and the middle-to-right analysis via skeleton expansion form a coherent strategy. I found no error in the main parameter inequalities.\n\nThe soft spot is exactly where the stress-test points. Lemmas 3.10 and 3.18 assert that the truncated incidence graph is structured in the sense of Definition 2.3, with 'omitted' verification. That is load-bearing: Lemma 5.3, which supplies the gadget pseudorandomness, is proved for a fixed balanced partition B = B1 union ... union Br of [D_R], and its key distributional step uses the Bi as disjoint blocks. Definition 2.3(4) only states that special sets have sizes in [D/(2s), 2D/s]; it never says they are pairwise disjoint or that they form a partition. If they do not, the union over W of |N(S) intersect Ai| is not the same as |N(S) intersect T| for a uniform T of size sum |Ai|, and the tail bound in Lemma 5.3 does not follow. The same issue affects the lower bound s in [q^{k-1}, O(q^{floor(k^2/4)})] in Lemma 2.7. This is a gap, not a demonstrated contradiction; the construction may well be repairable, and the authors may have a straightforward verification in mind. But as written, the proof does not close the loop.\n\nMinor point: Section 1.1 cites [HL22] for quantum LDPC codes; that should be [LH22].\n\nWho this is for: researchers in explicit expanders, high-dimensional expanders, and quantum LDPC codes will want to read it. It deserves a serious referee. I would send it to review with a request that the authors provide the omitted proofs and either strengthen Definition 2.3 to require a balanced partition or explain how the existing definition suffices. My own verdict is conditional: I think the main idea works, but I cannot certify the proof as it stands.","headline":"First explicit construction to break the 0.5d spectral barrier for two-sided vertex expanders, with a real but fixable gap in the structured base graph verification.","tokens_in":30053,"tokens_out":5016,"would_cite":true,"duration_ms":45304,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C48","05E45"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives the first explicit graphs in which every small set of vertices on either side has roughly 0.6d unique neighbors, breaking the spectral barrier of 0.5d.","keywords":["explicit vertex expanders","unique-neighbor expansion","two-sided expansion","spectral barrier","Ramanujan clique complex","tripartite line product","triangle density","high-dimensional expanders"],"falsifier":"Take the smallest nontrivial q and k=5 instance of the construction, enumerate for a fixed vertex u∈M and all v∈M_b with a common neighbor in R their common neighborhoods, and check that each equals Nbr_u(A_i) for one of the special sets A_i and that the A_i partition the neighbors of u into balanced groups; any deviation from Definition 2.3 disproves Lemma 3.18 and undermines the middle-to-right argument.","tokens_in":28768,"feed_emoji":"🔀","tokens_out":10879,"duration_ms":104253,"temperature":0.7,"pith_summary":"This paper constructs the first explicit two-sided vertex expanders that break the 0.5d spectral barrier. For any small error ε and any fixed aspect ratio, and all sufficiently large dL and dR, it gives an explicit infinite family of (5dL,5dR)-biregular bipartite graphs in which every sufficiently small subset on either side has at least roughly 0.6·(degree)·|S| unique neighbors, not merely 0.5d distinct neighbors. The construction uses a tripartite line product whose base graphs are vertex–face incidence graphs of the 4-dimensional Ramanujan clique complex, together with a constant-sized pseudorandom gadget, and a new bound on triangle density in small vertex sets of the Ramanujan complex is the key analytical ingredient. The result is the first explicit construction whose two-sided unique-neighbor expansion exceeds 1/2, the threshold that makes expander-based classical error-correcting codes work, and a step toward the 5/6 threshold needed for quantum LDPC codes.","feed_headline":"First explicit expanders beat the 0.5d spectral barrier","feed_subtitle":"Two-sided unique-neighbor expansion reaches about 0.6d, the first explicit construction past the old spectral limit.","key_machinery":"The load-bearing object is the structured bipartite base graph (Definition 2.3): a (k,D)-biregular graph G=(V,M,E) whose M-side is partitioned into k parts M_a, with each v∈V adjacent to exactly one vertex in each part, and whose common neighborhoods are constrained so that for u∈M_a and v∈M_b, N(u)∩N(v) is empty or exactly one of s 'special sets' of neighbors of u, each of size between D/(2s) and 2D/s. The construction instantiates G as the truncated vertex–face incidence graph of the Ramanujan clique complex of [LSV05a, LSV05b]. The tripartite line product places a copy of a constant-sized pseudorandom (dL,dR)-biregular gadget H between the DL left-neighbors and DR right-neighbors of each middle vertex, producing the final (kdL,kdR)-biregular graph on L∪R. The collision analysis rests on two derived properties of the base graphs: small-set triangle expansion (few vertices of V have three or more neighbors into a small U⊆M) and small-set skeleton expansion (the largest eigenvalue of the simple graph of length-2 walks through V on a small U⊆M is at most λ). For k=5 the new triangle-density bound gives DL,DR=Θ($q^{{10}}$), τ=O($q^{{6.5}}$), λ=O($q^{3}$), and sL,sR∈[$q^{4}$,O($q^{6}$)]; choosing gadget degrees dL,dR=Θ($q^{{3.25}}$) makes the analysis work, yielding the factor (k−2)/k=3/5.","core_discovery":"The paper's central claim, Theorem 2.1, is that for every ε>0 and β∈(0,1] there is a d0 such that for all dL,dR≥d0 with dR/dL∈[β,β+ε], there is an explicit infinite family of (5dL,5dR)-biregular bipartite graphs that are (3/5−ε)-two-sided unique-neighbor expanders, and there is a poly(n)-time algorithm that outputs a member of the family with Θ(n) vertices. This is the first explicit construction to bypass the spectral barrier: previously Ramanujan graphs guaranteed only that every small set has at least 0.5d distinct neighbors, and examples show this factor can be tight, with some explicit Ramanujan graphs containing small sets that have zero unique neighbors. The construction proves the stronger unique-neighbor statement: every small set on the left has at least (3/5−ε)·5dL·|S| unique neighbors, and similarly on the right. The proof goes through a tripartite line product with a structured base graph supplied by the 4-dimensional Ramanujan clique complex and a constant-sized pseudorandom gadget; the key new analysis is a bound on the number of size-5 faces with at least three vertices in any small vertex set of the Ramanujan complex.","pith_inferences":["A natural next test is to run the omitted verification of Lemma 3.18 computationally for small q and k=5; if the special-set structure fails, the middle-to-right collision bound would need a different mechanism, while if it passes, the construction is fully explicit and ready to instantiate.","The key quantitative gain over the earlier line-product construction is that the square of the right-side base graph splits into many nearly Ramanujan components, so the relevant collision degree is roughly sqrt(DR/ℓ) rather than sqrt(DR); this suggests that any base family whose two-step graph is a union of many independent expanders would yield a similar gain, making the exact face-density bound","Because the gadget graph is found by brute force over constant-size graphs, the explicitness of the construction does not depend on random search; a useful extension would be to tabulate the smallest gadget degrees for which the pseudorandom-gadget properties hold, which would determine the practical constants in the theorem.","If improved triangle-density or tetrahedron-density bounds become available, plugging them into this construction is the most direct route to two-sided unique-neighbor expansion above 3/5 and toward the 5/6 threshold for quantum LDPC codes."],"forward_implications":["For any fixed aspect ratio β and any small δ>0, once dL and dR are large enough, there is an explicit family of (5dL,5dR)-biregular two-sided unique-neighbor expanders with expansion 3/5−δ, constructible in polynomial time in the number of vertices.","Because the graphs have unique-neighbor expansion above 1/2 and carry the algebraic group-action property noted in Remark 1.1, they satisfy the main structural requirements for expander-based classical codes and some of the requirements for quantum LDPC constructions.","The new small-set triangle-density bound for the 4-dimensional Ramanujan clique complex is a standalone high-dimensional-expander fact: any vertex set of size at most δn contains at most O(q^{13/2}|U|) size-5 faces with at least three vertices.","If the same construction could be run with larger k, the unique-neighbor factor would become (k−2)/k; the paper identifies the missing ingredient as better density bounds for triangles or larger faces in the complex and for incidence graphs of subspace posets."],"supporting_citations":[{"why":"Supplies the tripartite line product construction and the collision-analysis lemmas (orientation by eigenvalue, two-sided degree bound) on which the proof builds.","marker":"[HMMP24]"},{"why":"Gives the explicit Ramanujan clique complex construction whose vertex–face incidence graph serves as the base graph.","marker":"[LSV05b]"},{"why":"Provides the companion Ramanujan-complex construction and spectral properties used throughout, including the simultaneous diagonalizability and link identification.","marker":"[LSV05a]"},{"why":"Establishes that spectral/Ramanujan graphs give 0.5d two-sided vertex expansion and that this spectral guarantee is tight, defining the barrier being broken.","marker":"[Kah95]"},{"why":"Shows explicit algebraic Ramanujan graphs contain small sets with zero unique neighbors, motivating why a spectral expander alone cannot deliver the result.","marker":"[KK22]"},{"why":"Supplies the second-eigenvalue bound for bipartite graphs between subspaces in the spherical building, used in the link analysis for the triangle-density bound.","marker":"[GHK+22]"},{"why":"Provides the high-dimensional expander triangle-counting strategy that the new triangle-density proof adapts.","marker":"[DH24]"}],"fun_headline_variants":["First explicit two-sided expanders beat 0.5d barrier","Two-sided vertex expanders reach 0.6d unique-neighbor expansion","Explicit two-sided expanders: 0.6d small-set expansion","First explicit past the 0.5d spectral barrier","Breaking the spectral barrier: explicit 0.6d two-sided expanders"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the truncated vertex–face incidence graph of the Ramanujan clique complex satisfies the structured-bipartite common-neighborhood property with balanced special sets, a claim the paper asserts without giving the verification.","fun_headline_variants_meta":{"raw":{"variants":["First explicit two-sided expanders beat 0.5d barrier","Two-sided vertex expanders reach 0.6d unique-neighbor expansion","Explicit two-sided expanders: 0.6d small-set expansion","First explicit past the 0.5d spectral barrier","Breaking the spectral barrier: explicit 0.6d two-sided expanders"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000589,"raw_usage":{"total_tokens":2866,"prompt_tokens":1150,"completion_tokens":1716,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":766,"completion_tokens_details":{"reasoning_tokens":1621}},"tokens_in":766,"tokens_out":1716,"duration_ms":12771,"temperature":1.0,"reasoning_tokens":1621,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:19:17.812172+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the smallest nontrivial q and k=5 instance of the construction, enumerate for a fixed vertex u∈M and all v∈M_b with a common neighbor in R their common neighborhoods, and check that each equals Nbr_u(A_i) for one of the special sets A_i and that the A_i partition the neighbors of u into balanced groups; any deviation from Definition 2.3 disproves Lemma 3.18 and undermines the middle-to-right argument.","supporting_citations":[],"review_version":1}