{"id":"5a54ff7a-8d95-4086-9584-18d3a038ec8b","arxiv_id":"2506.19485","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"High-degree vertices in Minimum-Component-Distance GIRGs with dimension at least two form expander subgraphs with omega(1) expansion for every sublinear set.","lead":"This paper proves that high-degree nodes in a random social network model where people connect when they share at least one trait form an expander: every small group has many outside connections. This implies that rumours, diseases, and distributed algorithms on such networks spread or converge quickly.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Linear-size case of the expander claim rests on an unproved adaptation of [23] to G′; without it, Theorem 2 proves only |S|≤ε|V′|, not the abstract's full expander statement.","rationale":"The formal theorem (Theorem 2) is honest: it restricts to |S| ≤ ε|V′| and the appendix proves exactly that. The problem is that the abstract and Theorem 1 promise more. The bridge for the linear range is a two-sentence assertion that [23]'s result adapts to G′. This is the single most load-bearing assumption because an expander is typically defined by expansion for all sets up to half the vertices; without that range, G′ would only be an expander for small sets, which is a weaker and less useful property. I looked for flaws in the sublinear proof: Proposition 1's strip-counting union bound is coherent (the Stirling-based tail decays as exp(−Ω(s)), so a union over s is summable), Proposition 2's per-strip neighbourhood concentration is valid because each vertex has ω(log n) expected in-strip neighbours, and the subtraction of |S| in the proof of Theorem 2 is legitimate since distinct strips are disjoint and each S-vertex lies in one strip. The degree-threshold reduction at the end of Theorem 2 is sketched but plausible, with the same constant-factor slack that the theorem already allows. The one genuinely unproven step is the linear-size case. I also noted the unproved claim that G′ is connected; this is part of the same adaptation step, since [23]'s theorem concerns the giant component. This is not a fatal flaw—the sublinear theorem is a real contribution and probably the linear case can be recovered—but the paper currently overclaims in its abstract, and the condition in the verdict (provide the adaptation or restrict the statement) is exactly right.","tokens_in":17333,"tokens_out":22297,"duration_ms":203239,"concrete_test":"Independently re-derive the asserted adaptation of [23, Theorem 1.1 (Existence of small separators depends on geometry)] to the induced subgraph G′: for every S⊆V′ with ε|V′| ≤ |S| ≤ |V′|/2, prove |Next_{G′}(S)| ≥ ε|V′|, and prove the connectivity claim 'Since G′ is connected' (or else formulate the adaptation relative to the giant component of G′). If the adaptation requires an additional assumption—e.g., that external neighbours in G of a high-weight set S are themselves in V′, or a minimum degree condition on G′—then the headline expander statement must be restricted to |S| ≤ ε|V′| and the abstract/Theorem 1 adjusted accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2, the formal main result, proves expansion only for subsets S with |S| ≤ ε|V′| (Proof in Appendix A.2, using Propositions 1 and 2). The abstract and Theorem 1 claim the induced subgraph G′ is an expander for all subsets up to size |V′|/2. The gap for ε|V′| < |S| ≤ |V′|/2 is disposed of in one paragraph after Theorem 2: the authors assert that the linear-size separator result of [23] 'can readily be adapted' from the giant component of G to G′, and that 'Since G′ is connected, we may also drop the condition on the giant component.' No proof of either assertion is given. This is load-bearing because the headline 'expander' attribute for G′ requires constant expansion for all subsets up to half the vertices, and the paper's own Propositions 1 and 2 do not deliver this range: applying them at |S|=|V′|/2 yields k·log^{γ(3−τ)}n = O(|V′|) with a hidden constant that may be below 1, so subtracting |S| can produce a non-positive bound. The sublinear claim (|S|=o(|V′|) or |S|≤ε|V′|) appears internally correct, and Propositions 1 and 2 are coherent, but the linear case is the point where the central claim depends on an unproved transfer.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Minimum-Component Distance Geometric Inhomogeneous Random Graphs (MCD-GIRGs) in dimension d≥2, with power-law exponent τ∈(2,3) and parameter α>1. It claims that the subgraph induced by vertices of weight at least c′log^γ n, for γ>1/(3−τ), is with high probability an expander: every set S of size at most |V′|/2 has external neighbourhood at least ε|S|, and the expansion factor is ω(1) for |S|=o(|V′|). The formal main theorem (Theorem 2) proves the expansion bound for subsets S with |S|≤ε|V′|, with an explicit factor ε·min{log^{γ(3−τ)}n, (|V′|/|S|)^{1−1/c_d}}, via two propositions: a strip-counting union bound (Proposition 1) and a lower bound on strip-local neighbourhoods (Proposition 2). The linear-size case ε|V′|<|S|≤|V′|/2 is deferred to an unproved adaptation of a result from [23]. The proof is presented in Appendix A.2 and relies on earlier lemmas from [18] and [4]. The paper also claims the result transfers to subgraphs induced by degree thresholds, and discusses algorithmic implications of expander structure.","tokens_in":17523,"tokens_out":19183,"duration_ms":176137,"significance":"If completed, the result is significant: it would provide the first demonstration that a non-metric, 'match in some dimension' geometry can produce strong expander behaviour in the high-degree core, in sharp contrast to Euclidean GIRGs, which have small separators at all scales. The strip-based mechanism is natural, and the explicit trade-off between γ and the expansion factor is informative. The paper is careful about the tightness of γ and about transferring the result from weights to degrees, and it contains no fitted parameters or ad-hoc axioms; the sublinear case is supported by a detailed counting argument that appears coherent. The main open direction (generalization to all BDF-GIRGs) is honestly stated. The value of the paper is currently reduced by the missing proof for linear-size sets, because the full expander property is what the abstract, Theorem 1, and the applications require.","major_comments":[{"comment":"The abstract and Theorem 1 claim that the induced subgraph G′ is an expander, i.e. that every S⊆V′ with |S|≤|V′|/2 has external neighbourhood at least ε|S|. Theorem 2, however, only proves this for |S|≤ε|V′|; the proof in Appendix A.2 (via Propositions 1 and 2) does not cover the range ε|V′|<|S|≤|V′|/2. The paragraph after Theorem 2 dismisses this range with the assertions that the linear-size result of [23] 'can readily be adapted' to G′ and that 'Since G′ is connected, we may also drop the condition on the giant component.' No proof of either assertion is given, and connectivity of G′ is not established by the paper; the condition γ>1/(3−τ) only rules out isolated vertices whp, not multiple components. This gap is load-bearing: constant expansion for constant-fraction sets is part of the headline expander claim, and the paper's own propositions cannot deliver it, since at |S|=|V′|/2 the bound k·log^{γ(3−τ)}n is only O(|V′|) with a hidden constant that may be far below 1, making the subtraction of |S| problematic. Please supply the full adaptation (stating precisely which theorem of [23] is transferred and how) or weaken the abstract, Theorem 1, and the applications accordingly.","section":"Section 2.2, paragraph after Theorem 2"},{"comment":"Proposition 1 is stated pointwise: for each s=ω(1) it asserts the existence of k and a whp event, and the event may depend on s. In the proof of Theorem 2 the proposition is applied to every S with C≤|S|≤ε|V′| simultaneously, but no union bound over s is written. The proof of Proposition 1 actually gives pk,s≤exp(−Ω(s)) once the constants c1,c2,cd are fixed, so a union bound over s (with C chosen large enough) would close the gap; however, this is not stated in the manuscript. As written, the universal 'with high probability' conclusion for all S is not formally derived from the pointwise statement. Please state and prove a uniform version of Proposition 1 (with the union bound over s) or adjust the proof of Theorem 2 accordingly.","section":"Appendix A.2, Proposition 1 and proof of Theorem 2"},{"comment":"In the proof of the degree-threshold version, the inclusions are reversed: from the two preceding sentences one obtains V2⊆VH′⊆V1, but the text states 'V1⊆VH′⊆V2'. Moreover, the sentence 'it suffices to show that every subset S⊆V2 has at least f·|S| neighbours in V1' does not by itself imply the claimed external-neighbourhood bound for H′: neighbours counted in V1 may lie inside S, and the subtraction of |S| (used in the weight-based case) is not accounted for here. These points need to be fixed; with the correct inclusions and a suitably enlarged neighbour-count bound before subtracting |S|, the argument should go through.","section":"Appendix A.2, proof of Theorem 2, degree-threshold part"}],"minor_comments":[{"comment":"Typo: 'c′ > 0 be consatnts' should read 'c′ > 0 be constants'.","section":"Proposition 1, statement"},{"comment":"The phrase 'let γ > 1/(3−τ) and c′ > 0 c′2 > c′1 > 0 be constants' is malformed; it should introduce the constants c′1, c′2 separately.","section":"Proposition 2, statement"},{"comment":"The expression for the probability that a fixed S lies in the union of k strips is written as '(k⌊n/ log2γn⌋−1)s'; it should be (k/⌊n/log^{2γ}n⌋)^s, with the exponent and division displayed correctly.","section":"Proposition 1 proof"},{"comment":"The sentence 'The larger the weights we consider, the better the expansion factor log^{γ(3−τ)}n becomes' is somewhat loose, since the theorem's stated expansion factor is the same for the interval-restricted subgraph; consider rephrasing.","section":"Section 2.2, paragraph after Theorem 2"},{"comment":"The phrase 'The proof for vertices of degrees in the interval [...] is analogously' should be 'is analogous'.","section":"Theorem 2 proof"}],"recommendation":"major_revision","confidential_remarks":"The main unresolved issue is the unproved transfer of the linear-size separator result from [23] to the induced subgraph G′. Since [23] has overlapping authorship with this paper, the authors are in a good position to supply the proof, but it must appear in the manuscript before the expander claim is justified. The reversed inclusion in the degree-threshold proof suggests that the proof section needs a careful revision; this is a technical fix rather than a conceptual obstacle."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is worth refereeing. The paper proves that in MCD-GIRGs with d>=2 and tau in (2,3), the subgraph G' induced by weights at least c' log^gamma n has external neighborhood at least epsilon * min{log^{gamma(3-tau)} n, (|V'|/|S|)^{1-1/c_d}} * |S| for all |S| <= epsilon |V'|. That is a real extension of [23], which only gave constant expansion for linear-sized subsets of the giant component. The new part is the omega(1) factor on sublinear sets, and the strip-counting machinery delivers it: Proposition 1's union bound is algebraically coherent, Proposition 2's per-strip concentration is valid, and the proof of Theorem 2 in Appendix A.2 handles the epsilon regime properly. No fitted parameters, no circular argument. Reliance on [18] for expected degrees in G' and on [23] for the linear case is legitimate prior art; it should be flagged more explicitly, but not as a defect.\n\nThe soft spots, in proportion: the headline claim is wider than the formal theorem. The abstract and Theorem 1 say G' is an expander for all |S| <= |V'|/2. Theorem 2 proves the claim only for |S| <= epsilon |V'|. The linear regime is disposed of in a paragraph after Theorem 2: [23]'s result 'can readily be adapted' to G', and because G' is connected, the giant-component condition can be dropped. No proof is given. This is load-bearing. Applying the paper's own Propositions 1 and 2 at |S| = |V'|/2 does not give a positive bound, so the constant-fraction case really does rest on that unproved transfer. I do not think the transfer is impossible; it may be routine for someone familiar with [23]. But it is not shown, and the paper's main advertised conclusion currently depends on it. Either supply the adaptation or restrict the abstract and Theorem 1 to the proven range.\n\nMinor: the degree-threshold reduction in the proof of Theorem 2 is a sketch, and Proposition 2's statement has a duplicated c' typo. Both are fixable and do not affect the sublinear theorem.\n\nBottom line: for a reader working on geometric random graphs or rumor spreading, the sublinear-scale result is the real content and it looks right. The paper deserves a serious referee, and the referee should ask the authors to close or explicitly scope the linear-size gap. I would bring it to our reading group and would cite it once the gap is addressed.","headline":"The sublinear-scale expansion theorem is genuinely new and the appendix argument looks sound, but the advertised expander statement for sets up to |V'|/2 depends on an unproved adaptation of [23].","tokens_in":18137,"tokens_out":2739,"would_cite":true,"duration_ms":27850,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C48","60C05","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"When \"close enough\" means matching on any one dimension, random geometric social networks become strong expanders, unlike Euclidean versions.","keywords":["Geometric Inhomogeneous Random Graphs","Minimum-Component Distance","expander graphs","power-law degree distribution","small separators","random graph models","social networks"],"falsifier":"One concrete check: in an MCD-GIRG with $d\\ge 2$, $\\tau\\in(2,3)$, and $\\gamma>1/(3-\\tau)$, look for a sequence of vertex sets $S_n\\subset V'$ with $\\varepsilon|V'|\\le |S_n|\\le |V'|/2$ whose external neighbourhood in $G'$ is $o(|S_n|)$ with non-negligible probability. If such sets exist, the full expander statement fails in the constant-fraction regime, even if the $\\omega(1)$ expansion for sublinear sets survives. The natural candidate geometry to inspect is the cross-shaped MCD ball, where strip-aligned cuts may behave differently from Euclidean cube separators.","tokens_in":17046,"feed_emoji":"🌐","tokens_out":7373,"duration_ms":69799,"temperature":0.7,"pith_summary":"The paper studies Geometric Inhomogeneous Random Graphs in which two vertices are considered close if they agree along at least one latent dimension (Minimum-Component Distance, or MCD), rather than along all dimensions. It establishes that for dimension $d\\ge 2$, the subgraph induced by vertices of polylogarithmic weight or degree is a strong vertex expander: every subset of size $o(|V'|)$ has external neighbourhood of size $\\omega(1)$ times itself, and every subset up to a constant fraction has at least constant expansion. This is the opposite of the Euclidean version, which has small separators at every scale. The result matters because expanders support fast random walks, fast rumour and infection spread, robust routing, and fast distributed and approximation algorithms. The paper's quantitative statement gives expansion factor roughly $\\min\\{\\log^{\\gamma(3-\\tau)} n,\\ (|V'|/|S|)^{1-1/c_d}\\}$.","feed_headline":"Min-component distance turns social models into expanders","feed_subtitle":"High-degree subgraphs expand at every scale, so mixing, rumour spread, and algorithms run fast.","key_machinery":"The load-bearing objects are the Minimum-Component Distance and a strip partition of the torus ground space. MCD makes two vertices close when $\\min_i |x_{u,i}-x_{v,i}|$ is small, so edges form when the vertices match on any single coordinate; this is why the distance is not a metric and violates the triangle inequality. The proof divides each coordinate into strips of width roughly $n/\\log^{2\\gamma}n$, chosen so that two vertices of weight $\\log^\\gamma n$ in the same strip are connected with constant probability. Proposition 1 is a counting argument showing that, with high probability, any set $S$ of size $s$ spans many distinct strips in some coordinate, with the number $k$ of such strips at least of order $s\\cdot\\min\\{1,\\ (|V'|/s)^{1-1/c_d}/\\log^{\\gamma(3-\\tau)}n\\}$. Proposition 2 shows each vertex has $\\Theta(\\log^{\\gamma(3-\\tau)}n)$ neighbours of suitable weight inside its own strip. Adding these strip-neighbourhoods and subtracting $|S|$ gives the lower bound on the external neighbourhood.","core_discovery":"The central claim is Theorem 2: for each $d\\ge 2$ there is $c_d>1$ such that, with high probability, the subgraph $G'$ of an MCD-GIRG induced by vertices of weight at least $c'\\log^\\gamma n$ has the property that every $S\\subseteq V'$ with $|S|\\le \\varepsilon|V'|$ satisfies $|\\mathrm{Next}(S)\\cap V'| \\ge \\varepsilon\\min\\{\\log^{\\gamma(3-\\tau)} n,\\ (|V'|/|S|)^{1-1/c_d}\\}|S|$. In particular the expansion factor is $\\omega(1)$ whenever $|S|=o(|V'|)$. The same statement holds for subgraphs induced by degree thresholds and by degree intervals; the interval version is almost regular, with degrees within a factor $2+o(1)$. The paper notes that the regime of constant-fraction sets rests on adapting the earlier no-sublinear-separator result for the giant component to the induced subgraph $G'$, and the formal proof in the appendix covers only $|S|\\le\\varepsilon|V'|$.","pith_inferences":["If the same proof strategy extends to general Boolean Distance Functions that are not single-coordinate outer max, the expander-versus-separator split would become a full classification of all such geometries; the paper leaves this as an explicit open problem.","The strong expansion at sublinear scales suggests MCD-GIRGs may support sublinear-query estimation of global quantities, since a small random sample of high-degree vertices quickly reaches the rest of that subgraph.","The mechanism is essentially that 'OR' similarity — agreement on any one feature — makes neighbourhoods spread across many feature-strips, whereas 'AND' similarity concentrates them; this gives a design principle for synthetic networks that need fast mixing.","A direct empirical test: generate MCD-GIRG and Euclidean GIRG with the same degree sequence and measure the spectral gap of the normalized Laplacian of the high-degree subgraph; the dichotomy should be visible at moderate $n$."],"forward_implications":["Random walks on the high-degree subgraph $G''$ mix rapidly, so sampling vertices and computing PageRank-style quantities from local access becomes fast.","Rumour-spreading and SI infection models reach essentially all large-degree vertices in polylogarithmic rounds, and infection spreads among them in $o(\\log n)$ rounds.","Distributed consensus dynamics such as best-of-$k$ voting converge in $O(\\log n)$ rounds on the almost-regular subgraph.","The induced subgraph remains well-connected after random removal of a small constant fraction of edges or vertices, supporting robust routing.","Approximation algorithms for balanced cuts, colouring, independent set, and related NP-hard problems inherit expander-based guarantees when run on $G''$."],"supporting_citations":[{"why":"introduces the MCD-GIRG model, gives the basic geometry-independent properties including the bulk lemma connecting ordinary vertices to high-weight vertices, and supplies the clustering result.","marker":"[4]"},{"why":"proves that the giant component of MCD-GIRGs has no sublinear separators; this linear-size result is the piece the paper adapts for constant-fraction sets in Theorem 2.","marker":"[23]"},{"why":"supplies Lemma 10 on expected degree of vertices inside the threshold subgraph, which the proof uses throughout.","marker":"[18]"},{"why":"establishes the small-separator property of Euclidean GIRGs that motivates the contrast, and defines the original GIRG framework.","marker":"[3]"}],"fun_headline_variants":["MCD-GIRG hubs form strong expanders","Min-component distance yields expander subgraphs","High-degree subgraphs expand in social model","Social graph model guarantees hub expansion"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the previously known result of [23] — that linear-size subsets of the giant component of an MCD-GIRG have linear external neighbourhoods — can be transferred without loss to the induced subgraph $G'$ of high-weight vertices; the paper states this transfer is straightforward but does not prove it, and the formal proof only handles sets of size at most $\\varepsilon|V'|$.","fun_headline_variants_meta":{"raw":{"variants":["MCD-GIRG hubs form strong expanders","Min-component distance yields expander subgraphs","High-degree subgraphs expand in social model","Social graph model guarantees hub expansion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000226,"raw_usage":{"total_tokens":1524,"prompt_tokens":1057,"completion_tokens":467,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":673,"completion_tokens_details":{"reasoning_tokens":412}},"tokens_in":673,"tokens_out":467,"duration_ms":4886,"temperature":1.0,"reasoning_tokens":412,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:34:07.277435+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One concrete check: in an MCD-GIRG with $d\\ge 2$, $\\tau\\in(2,3)$, and $\\gamma>1/(3-\\tau)$, look for a sequence of vertex sets $S_n\\subset V'$ with $\\varepsilon|V'|\\le |S_n|\\le |V'|/2$ whose external neighbourhood in $G'$ is $o(|S_n|)$ with non-negligible probability. If such sets exist, the full expander statement fails in the constant-fraction regime, even if the $\\omega(1)$ expansion for sublinear sets survives. The natural candidate geometry to inspect is the cross-shaped MCD ball, where strip-aligned cuts may behave differently from Euclidean cube separators.","supporting_citations":[{"cited_title":"Advances in Applied Probability p","cited_arxiv_id":null,"evidence_quote":"introduces the MCD-GIRG model, gives the basic geometry-independent properties including the bulk lemma connecting ordinary vertices to high-weight vertices, and supplies the clustering result."},{"cited_title":"Existence of Small Separators Depends on Geometry for Geometric Inhomogeneous Random Graphs","cited_arxiv_id":"1711.03814","evidence_quote":"proves that the giant component of MCD-GIRGs has no sublinear separators; this linear-size result is the piece the paper adapts for constant-fraction sets in Theorem 2."},{"cited_title":"Internet Mathematics p","cited_arxiv_id":null,"evidence_quote":"supplies Lemma 10 on expected degree of vertices inside the threshold subgraph, which the proof uses throughout."},{"cited_title":"Theoretical Computer Science760, 35–54 (2019)","cited_arxiv_id":null,"evidence_quote":"establishes the small-separator property of Euclidean GIRGs that motivates the contrast, and defines the original GIRG framework."}],"review_version":2}