{"id":"6378581d-c575-411c-be5a-7797ad1ae084","arxiv_id":"2412.14364","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves that minimum degree (n+d)/2 - 1 forces d-rigidity for d=O(sqrt n), and (n+2d)/2 - 1 forces d-rigidity for d=O(n/log^2 n), plus a matching pseudoachromatic-number bound.","lead":"The paper proves minimum-degree thresholds that force a graph to be rigid, or structurally stable, when placed in d-dimensional space, for d up to about n/log^2(n). The thresholds are tight for small d and off by at most a factor of two for larger d, so the result advances a central conjecture in graph rigidity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No internal error found; the least-secure premise is the imported Villányi Lemma 3.3, on which Theorem 1.1 fully depends.","rationale":"The reader's weakest-assumption analysis correctly identifies the imported theorems as the most fragile load-bearing premises. My independent pass over the paper's own derivations did not surface any internal flaw: the random-colouring lemma has correct Chernoff bounds and Lipschitz constants, the close-to-bipartite construction yields a legitimate strong d-rigid partition, the super-regular tripartite connectivity argument is sound, and the extension lemma plus 0-extension property closes Proposition 4.2 cleanly. The only substantive risk is that Theorem 1.1 depends on Villányi's Lemma 3.3, a strong structural statement from a recent preprint that the paper uses without proof. If that lemma is correct, the central claims are established; if it is not, the small-d theorem fails. Since this is a dependency on external results rather than evidence of an internal error, the appropriate disposition is to keep the ACCEPT verdict while flagging the dependency. The proposed concrete test would settle whether the dependency is actually safe.","tokens_in":20006,"tokens_out":33632,"duration_ms":285457,"concrete_test":"Independently reconstruct the proof of Lemma 3.3 from its stated hypotheses, checking specifically whether the permutation construction requires d-connectivity or some stronger condition than delta >= d(d+1). Alternatively, search exhaustively for small counterexamples (e.g., n=6..10, d=2..3) among graphs satisfying the neighbourhood and clique-intersection hypotheses of Lemma 3.3, verifying whether every permutation sigma gives |E_sigma| < dn. If a counterexample exists, Theorem 1.1's tight range fails; if no counterexample appears and the proof reconstructs cleanly, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the main internal arguments: Lemma 4.3's coupling together with the Chernoff/Azuma estimates, Proposition 4.1's bipartite-adjustment chain and Claims 4.6-4.7, Proposition 4.16's connectivity cases, Lemma 4.8's super-regular reduction, and Lemma 4.19's counting argument. They are sound, and I found no algebraic or probabilistic error that would shake Theorems 1.2 or 1.3. The genuinely load-bearing unproven premise is Lemma 3.3 from Villányi's preprint [25], used in the proof of Lemma 3.1: it asserts that any graph with minimum degree at least d(d+1), no clique neighbourhoods, and all pairwise maximal-clique intersections of size at most d-2 admits a permutation sigma with |E_sigma| >= dn. Theorem 1.1 collapses entirely if this lemma carries a hidden restriction or a flaw, and the paper does not reproduce its proof. The companion Lemma 3.2 and the imported Theorem 2.3 are also black boxes, but Lemma 3.3 is the most consequential because the paper's tight small-d result rests on it alone. This is a legitimate external dependency rather than an internal contradiction, but it is exactly where correctness is least secured.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies minimum-degree sufficient conditions for generic rigidity in R^d. Theorem 1.1 gives a tight bound for small d: for d = O(sqrt n), every n-vertex graph with minimum degree at least (n+d)/2 - 1 is d-rigid. The proof passes through the d-closure of the graph and uses two lemmas of Vill\\'anyi, one of which asserts that every d-closed graph with minimum degree at least d(d+1) has a simplicial vertex. Theorem 1.2 gives an approximate result for d = O(n/log^2 n): the same conclusion holds when the minimum degree is at least (n+2d)/2 - 1, which is tight up to a factor of two in the coefficient of d. The proof splits into a bipartite case (Proposition 4.1, via random pseudocomplete colourings and strong d-rigid partitions) and a non-bipartite case (Proposition 4.2, via the regularity lemma and super-regular triples). Theorem 1.3, a byproduct, states that every n-vertex graph with minimum degree at least d has pseudoachromatic number at least d+1 when d = O(n/log^2 n), and this is tight. The paper is clearly written and the internal proofs are carefully structured, but it relies on substantial unproved external results.","tokens_in":20207,"tokens_out":36083,"duration_ms":295919,"significance":"If the external lemmas are valid, this is a noteworthy advance on a natural conjecture about minimum degree and rigidity. Theorem 1.1 confirms the conjectured threshold in the range d = O(sqrt n), and Theorem 1.2 narrows the gap to within a factor of two in the linear-in-d term for a much wider range. Theorem 1.3 is a clean, tight byproduct. The paper's own contributions are strong: the probabilistic estimates in Lemmas 4.3 and 4.4 use explicit constants and correct Chernoff/Azuma bounds; the super-regular reduction in Lemma 4.8 and Corollary 4.15 is standard and correctly applied; Proposition 4.16's connectivity case analysis is complete; and Lemma 4.19's extension argument is elegant. The main caveat is that Theorem 1.1, one of the two headline results, rests entirely on Lemma 3.3, which is quoted from an unpublished preprint and not proved in the manuscript.","major_comments":[{"comment":"Theorem 1.1 is conditional on Lemma 3.3, which is stated without proof and attributed to the unpublished preprint [25]. This lemma is load-bearing: the entire proof of Lemma 3.1, and hence of Theorem 1.1, collapses if Lemma 3.3 has a hidden restriction or an error. The manuscript does not reproduce or even sketch its proof. Please include a complete proof of Lemma 3.3, or replace the reference with a peer-reviewed version, so that the main small-d theorem is not contingent on an inaccessible black box.","section":"3 (proof of Lemma 3.1)"},{"comment":"The first bullet of Lemma 4.3 guarantees P(v in V_i) >= 1/(2d) only for i in [d], omitting the (d+1)-st colour class, even though the proof of the lemma establishes the bound for all i in [d+1]. Proposition 4.1 applies Lemma 4.3 with parameter d-1 and then uses the probability bound for all d colour classes A_1,...,A_d, including the last one. As stated, the lemma does not formally cover that final class. Please restate the first bullet of Lemma 4.3 to cover all colour classes, or state the stronger consequence explicitly in Proposition 4.1.","section":"4.1 (Lemma 4.3 and Proposition 4.1)"}],"minor_comments":[{"comment":"The notation A' and B' is overloaded: first they denote the two sides of the bipartition, and later they are reused for the unions A_1 cup ... cup A_d and B_1 cup ... cup B_d of the random colour classes. This makes the proof hard to follow and should be fixed, for example by using X and Y for the two sides.","section":"4.1 (proof of Proposition 4.1)"},{"comment":"The sentence 'G[H1 union H2 union {v}] is not complete, and hence not d-rigid' is not true for arbitrary graphs and should explicitly invoke that G is d-closed. In a d-closed graph, an induced subgraph that contains a d-rigid spanning subgraph would force the whole induced subgraph to be complete, but this reasoning is currently suppressed.","section":"3 (proof of Lemma 3.1)"},{"comment":"The proof uses the implication 'D-rigid implies d-rigid for d <= D' in order to pass from a strong D-rigid partition of H to d-rigidity of H. This is a standard fact, but it is not stated in the preliminaries. A one-sentence reference or proof would make the argument self-contained.","section":"4.2.2 (proof of Proposition 4.2)"},{"comment":"The phrase 'tight up to a factor of two in the coefficient of d' is used for Theorem 1.2, but no construction is given showing that the coefficient 2 cannot be improved. Please clarify whether this means tight only against the conjectured optimal bound in Conjecture 1, or whether a matching lower-bound construction is known.","section":"Abstract and Section 1"},{"comment":"There is a typo: 'p reserves the distance' should read 'preserves the distance'.","section":"1 (Introduction)"}],"recommendation":"major_revision","confidential_remarks":"The central internal arguments are sound, and I found no internal contradiction. The main risk is external: Theorem 1.1 depends wholly on Vill\\'anyi's Lemma 3.3, which is not proved in the manuscript and is from an unpublished preprint. I would advise the editor to require the authors to supply a proof of Lemma 3.3 or a peer-reviewed reference before publication, since the tight small-d result is the paper's headline contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Good paper. It settles the small-d case of Conjecture 1 exactly (d=O(sqrt n), threshold (n+d)/2 - 1) and gets within a factor of two for d=O(n/log^2 n). That's real progress over the previous d ~ k/log n bounds from [18]. The pseudoachromatic byproduct (Theorem 1.3) is a nice bonus and the sharpness examples look right.\n\nThe internal arguments are careful. I checked the probabilistic estimates: Lemma 4.3's colouring construction with the Chernoff/Azuma bounds has explicit constants and the negative correlation step is fine. Proposition 4.1's case analysis for strong d-rigid partitions is complete. The regularity part in Section 4.2 is standard and the extension argument via Lemma 4.19 is correct. No internal error jumped out.\n\nThe soft spot is exactly where the stress-test points: Theorem 1.1 depends entirely on Villányi's Lemma 3.3, imported from a preprint and not proved here. If that lemma has a hidden restriction or a flaw, the small-d theorem collapses. Same for Lemma 3.2 and for Theorem 2.3 from [19], though those are less consequential. This is a legitimate external dependency rather than a sign of trouble, and the paper says so, but it means the tight small-d claim is only as good as that lemma. I'd want a referee to check the Villányi argument carefully before accepting.\n\nAlso, the self-citations to [18] and [19] are fine: they are used as prior tools and comparisons, not disguised as new equivalents. The paper is honest about what remains open: full Conjecture 1 for linear d is still open.\n\nVerdict: worth publishing after review. The main theorems are new, the proofs are mostly self-contained, and the remaining black boxes are clearly identified. A serious referee should spend time on Lemma 3.3's provenance; otherwise the paper is in good shape.","headline":"Strong and honest progress on a known conjecture: tight small-d and near-tight large-d minimum-degree thresholds for rigidity, with the main vulnerability being its reliance on an imported lemma from Villányi's preprint.","tokens_in":20819,"tokens_out":1505,"would_cite":true,"duration_ms":12920,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52C25","05C35","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that n-vertex graphs with minimum degree just above half the vertices are generically rigid in $\\mathbb{R}^d$ for all $d$ up to about $n/\\log^2 n$, with an exact threshold for $d$ up to about $\\sqrt{n}$.","keywords":["graph rigidity","minimum degree","d-rigid","rigid partitions","pseudoachromatic number","regularity lemma","d-closure","generic embeddings"],"falsifier":"A concrete refutation would be a single $n$-vertex graph with $\\delta(G) \\ge (n+2d)/2 - 1$ for some $d \\le cn/\\log^2 n$ whose rigidity matrix at a generic embedding has rank below $dn - \\binom{d+1}{2}$; such a graph would disprove Theorem 1.2. The analogous check with $\\delta(G) \\ge (n+d)/2 - 1$ and $d \\le c\\sqrt{n}$ would settle Theorem 1.1.","tokens_in":19757,"feed_emoji":"📐","tokens_out":13356,"duration_ms":99379,"temperature":0.7,"pith_summary":"The paper establishes that a minimum degree just above half the vertex count makes a graph generically rigid in $\\mathbb{R}^d$, for a wide range of $d$. For $d$ up to order $\\sqrt{n}$, the threshold $\\delta(G) \\ge (n+d)/2 - 1$ is exactly what connectivity demands, and the paper proves it suffices for $d$-rigidity. For $d$ up to order $n/\\log^2 n$, the slightly stronger threshold $\\delta(G) \\ge (n+2d)/2 - 1$ suffices, and this is tight up to a factor of two in the coefficient of $d$. A byproduct is a sharp lower bound on the pseudoachromatic number: every $n$-vertex graph with minimum degree at least $d$ has a partition of its vertices into $d+1$ parts with at least one edge between every pair of parts.","feed_headline":"Rigidity threshold proven for d up to n/log² n","feed_subtitle":"Exact for d=O(√n), within a factor of two for larger d; a pseudoachromatic bound follows.","key_machinery":"The central object is the strong $d$-rigid partition: a partition of the vertex set into $d$ parts, each of size at least one, such that $G[V_i,V_j]$—the subgraph with all edges between $V_i$ and $V_j$—is connected for every $1 \\le i \\le j \\le d$. The imported Theorem 2.3 says that any graph admitting such a partition is $d$-rigid, so the whole problem for large $d$ reduces to constructing these partitions. For small $d$, the paper uses the $d$-closure—the graph formed by adding every non-edge that does not increase the rigidity matrix rank—together with an imported lemma that any $d$-closed graph with minimum degree at least $d(d+1)$ contains a simplicial vertex; a short argument then forces the closure to be complete, which is equivalent to $d$-rigidity. For large $d$, the engine is the strong $d$-rigid partition, whose existence is obtained by two structural routes: random colourings with strong cross-connectivity in the near-bipartite case, and a Regularity-Lemma reduction to a super-regular tripartite graph in the far-from-bipartite case.","core_discovery":"On its own terms, the paper's central claim is that the conjectural minimum-degree threshold for $d$-rigidity, $\\max\\{(n+d)/2 - 1,\\ 2d - d(d+1)/n\\}$, is correct for $d = O(\\sqrt{n})$ (Theorem 1.1) and is correct up to a factor of two in the second term's coefficient for $d = O(n/\\log^2 n)$ (Theorem 1.2). The proof works by showing that such graphs admit strong $d$-rigid partitions—partitions into $d$ parts such that every part and every pair of parts induces a connected cross-subgraph—when the graph is close to bipartite, and by showing $d$-rigidity directly for far-from-bipartite graphs via a regularity-lemma reduction to a super-regular tripartite subgraph. Since a strong $d$-rigid partition implies $d$-rigidity, the first case is immediate; the second uses a $0$-extension argument to grow a large $d$-rigid subgraph to the whole graph. The same random-colouring machinery yields the pseudoachromatic result (Theorem 1.3).","pith_inferences":["If the random-colouring lemma generalizes, the same method may give pseudocomplete colourings with $d+1$ colours for graphs of minimum degree $d$ in other sparse settings, such as random graphs with minimum degree constraints.","The factor-two gap in Theorem 1.2 is an invitation: the conjecture predicts the exact threshold, and the near-bipartite/far-bipartite split suggests the obstruction should be located in one of the two regimes rather than in a mixed regime.","The strong-rigid-partition reduction, combined with the regularity lemma, suggests that any graph containing a super-regular tripartite subgraph of linear size is $d$-rigid for $d$ up to order $n/\\log n$; this could be a route to rigidity thresholds in dense random and quasirandom graphs."],"forward_implications":["Conjecture 1 is confirmed in the range $d = O(\\sqrt{n})$, where the connectivity threshold $(n+d)/2 - 1$ is shown to be the exact minimum-degree threshold for $d$-rigidity.","For $d = O(n/\\log^2 n)$, the threshold $(n+2d)/2 - 1$ guarantees $d$-rigidity, so the conjectured threshold is known within a factor of two in the coefficient of $d$.","Every $n$-vertex graph with minimum degree at least $d$ (for $d = O(n/\\log^2 n)$) has a pseudocomplete colouring with $d+1$ colours, and this is best possible.","The proof's random-colouring construction (Lemma 4.3) yields, with high probability, a pseudocomplete colouring in which each of $d+1$ colour classes captures most vertices with probability at least $1/(2d)$, independently across vertices—a new structural tool.","The small-$d$ result extends the previously known rigidity range for this degree condition from $d = O(\\sqrt{n}/\\log n)$ to $d = O(\\sqrt{n})$."],"supporting_citations":[{"why":"Defines generic rigidity and proves that for generic embeddings rigidity depends only on the graph and equals infinitesimal rigidity; foundational for the whole paper.","marker":"[1]"},{"why":"Proves the sufficient condition that a strong $d$-rigid partition implies $d$-rigidity (Theorem 2.3), the key reduction used in Propositions 4.1 and 4.2.","marker":"[19]"},{"why":"Supplies the lemmas used to show every $d$-closed graph with minimum degree at least $d(d+1)$ has a simplicial vertex; this drives Theorem 1.1.","marker":"[25]"},{"why":"Provides the observation on $d$-closed graphs (two common neighbours of a $d$-clique are adjacent), used in Lemma 3.4 to force the $d$-closure to be complete.","marker":"[20]"},{"why":"Gives the $0$-extension property used to add a vertex of degree at least $d$ to a $d$-rigid graph while preserving rigidity, the step that grows a large rigid subgraph to the whole graph.","marker":"[23]"},{"why":"Stability theorem used to show the reduced graph of a far-from-bipartite dense graph contains a triangle.","marker":"[4]"},{"why":"The degree form of the Regularity Lemma, used to find a super-regular tripartite subgraph in the far-from-bipartite case.","marker":"[16]"},{"why":"Provides the argument for Lemma 4.19, which finds a vertex with at least $d$ neighbours in any large rigid set, enabling the $0$-extension step.","marker":"[13]"}],"fun_headline_variants":["Exact rigidity threshold for d up to sqrt(n)","Near-tight rigidity bounds for large d in graphs","Minimum degree for rigidity: tight and near-tight","Graph rigidity threshold proven to within factor 2","Pseudoachromatic bound from rigidity proof"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's main theorems rest on two imported black-box results—that a strong $d$-rigid partition implies $d$-rigidity, and that a $d$-closed graph with minimum degree at least $d(d+1)$ has a simplicial vertex—so if either imported theorem has a hidden restriction or gap, the corresponding minimum-degree result does not follow from the arguments given.","fun_headline_variants_meta":{"raw":{"variants":["Exact rigidity threshold for d up to sqrt(n)","Near-tight rigidity bounds for large d in graphs","Minimum degree for rigidity: tight and near-tight","Graph rigidity threshold proven to within factor 2","Pseudoachromatic bound from rigidity proof"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000622,"raw_usage":{"total_tokens":2914,"prompt_tokens":1011,"completion_tokens":1903,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":627,"completion_tokens_details":{"reasoning_tokens":1843}},"tokens_in":627,"tokens_out":1903,"duration_ms":13064,"temperature":1.0,"reasoning_tokens":1843,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:19:36.530341+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete refutation would be a single $n$-vertex graph with $\\delta(G) \\ge (n+2d)/2 - 1$ for some $d \\le cn/\\log^2 n$ whose rigidity matrix at a generic embedding has rank below $dn - \\binom{d+1}{2}$; such a graph would disprove Theorem 1.2. The analogous check with $\\delta(G) \\ge (n+d)/2 - 1$ and $d \\le c\\sqrt{n}$ would settle Theorem 1.1.","supporting_citations":[{"cited_title":"MR 511410 ↑1, 2","cited_arxiv_id":null,"evidence_quote":"Defines generic rigidity and proves that for generic embeddings rigidity depends only on the graph and equals infinitesimal rigidity; foundational for the whole paper."},{"cited_title":"Rigidity expander graphs","cited_arxiv_id":"2304.01306","evidence_quote":"Proves the sufficient condition that a strong $d$-rigid partition implies $d$-rigidity (Theorem 2.3), the key reduction used in Propositions 4.1 and 4.2."},{"cited_title":"Every $d(d+1)$-connected graph is globally rigid in $\\mathbb{R}^d$","cited_arxiv_id":"2312.02028","evidence_quote":"Supplies the lemmas used to show every $d$-closed graph with minimum degree at least $d(d+1)$ has a simplicial vertex; this drives Theorem 1.1."},{"cited_title":"Raz, Sharp threshold for rigidity of random graphs , Bull","cited_arxiv_id":null,"evidence_quote":"Provides the observation on $d$-closed graphs (two common neighbours of a $d$-clique are adjacent), used in Lemma 3.4 to force the $d$-closure to be complete."},{"cited_title":"Dual French-English text","cited_arxiv_id":null,"evidence_quote":"Gives the $0$-extension property used to add a vertex of degree at least $d$ to a $d$-rigid graph while preserving rigidity, the step that grows a large rigid subgraph to the whole graph."},{"cited_title":"MR 205876 ↑13","cited_arxiv_id":null,"evidence_quote":"Stability theorem used to show the reduced graph of a far-from-bipartite dense graph contains a triangle."},{"cited_title":"2 (Keszthely, 1993), J´ anos Bolyai Math","cited_arxiv_id":null,"evidence_quote":"The degree form of the Regularity Lemma, used to find a super-regular tripartite subgraph in the far-from-bipartite case."},{"cited_title":"MR 3548301 ↑2, 16","cited_arxiv_id":null,"evidence_quote":"Provides the argument for Lemma 4.19, which finds a vertex with at least $d$ neighbours in any large rigid set, enabling the $0$-extension step."}],"review_version":1}