{"id":"ea70ff06-5cc4-4f61-8d37-1928f7877d15","arxiv_id":"2505.22652","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A paper introducing PyRigi, a Python package for testing rigidity, global rigidity, and related properties of graphs and frameworks.","lead":"PyRigi is a new open-source Python package that computes rigidity and flexibility properties of bar-and-joint frameworks, such as whether a graph has finitely many distance-preserving drawings in the plane. It bundles algorithms from the rigidity-theory literature with mathematical documentation, aiming to become a standard computational tool for researchers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Paper omits the probability-to-range conversion for its randomized generic/global rigidity tests, leaving a silent false-negative risk in the central reliability claim.","rationale":"The strongest claim is that PyRigi reliably determines generic rigidity, global rigidity, and redundant rigidity. The 2D generic and global rigidity cases have exact combinatorial algorithms (Laman and Jackson-Jordan, respectively), so those decisions are trustworthy in principle, though the paper's statement of the Jackson-Jordan theorem omits the small-graph caveat, which is a documentation error worth fixing. The load-bearing uncertainty is the randomized method used for generic rigidity in arbitrary dimensions and for global rigidity generally. The paper asserts a user-controllable false-negative bound, but gives no formula, no code excerpt, and no experiment showing that the implemented coordinate range achieves the claimed bound. Because a too-small range silently corrupts the decision, the central reliability claim cannot be accepted on the evidence presented. This is exactly the reader's weakest assumption, and the concrete test above would settle it by source inspection plus a simple randomized trial. If the test passes, the paper needs only documentation improvements; if it fails, the package's headline capability is compromised. The reader's conditional verdict remains appropriate.","tokens_in":16224,"tokens_out":8142,"duration_ms":87581,"concrete_test":"Inspect the PyRigi source to find where a user-supplied false-negative probability is converted into the coordinate range for the randomized rank test (likely in pyrigi/graph/_rigidity/generic.py and global_.py). Independently derive the Schwartz-Zippel bound: for a generically rigid graph with n vertices in dimension d, the relevant maximal minor of the rigidity matrix is a nonzero polynomial of degree at most d n, so with coordinates chosen uniformly from {-N,...,N}, a false negative occurs with probability at most (d n)/(2N+1). Verify that the implemented N satisfies (d n)/(2N+1) <= epsilon for the user-specified epsilon, and that the rank computation is performed exactly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 states that the randomized method for generic and global rigidity, based on Gortler, Healy, and Thurston (2010, Alg 5.2, Prop 5.7), never gives false positives and that a user can specify an upper bound on the probability of a false negative. The paper never documents the formula that converts this probability bound into the range of the randomly chosen integer coordinates, nor how the implementation selects that range. Since the method is the default for dimensions other than 1 and 2, the central claim that PyRigi can determine rigidity properties with reliable and robust algorithms depends on this undocumented parameter. If the range is too small, a random realization of a genuinely rigid graph can land on the singular locus of the rigidity matrix with probability exceeding the advertised bound, producing a silent not-rigid answer. This is not a purely theoretical worry: the paper itself notes that the current random linear algebra lacks the modular lifting approach that GHT recommend, but provides no tests or theoretical check that the exact integer rank computation is consistent with the claimed probability guarantee. Without documenting or empirically validating the conversion, the package's key reliability claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents PyRigi, an open-source Python package for the rigidity and flexibility of bar-and-joint frameworks. It describes the package's design around three classes (Graph, Framework, Motion) and surveys the implemented functionality: generic, infinitesimal, redundant, and global rigidity checks; (k,l)-sparsity via pebble-game algorithms; rigidity-matroid operations; NAC-colorings; drawing and plotting tools; and numerical and parametric motion generation. The central claim is that PyRigi is a general-purpose, reliable, and robust computational tool that lets working mathematicians determine rigidity properties that would be infeasible by hand. The manuscript emphasizes the tight coupling between mathematical definitions/theorems and the code documentation, and it outlines the project's development infrastructure, testing levels, and planned extensions.","tokens_in":16430,"tokens_out":5667,"duration_ms":66639,"significance":"If the claims hold, PyRigi is a useful community resource: it unifies many algorithms from the recent literature in one open-source package, provides documented links from code to mathematical theorems, and includes databases, visualization, and motion tools. The reliance on independent external results (Laman, Pollaczek-Geiringer, Jackson-Jordán, Gortler-Healy-Thurston, Connelly-Whiteley) is a strength, and the authors are explicit about current limitations. However, the paper's stated reliability guarantees are not backed by any empirical evaluation or by a complete description of the randomized methods' probability parameters, so the practical significance is currently underevidenced.","major_comments":[{"comment":"The randomized method is described as never giving false positives and as allowing the user to specify an upper bound on the probability of a false negative, but the paper does not document how that bound is converted into the range of randomly chosen integer coordinates, nor how the implementation selects the range. Since this method is the only generic-rigidity option in dimensions d >= 3 and the global-rigidity check also rests on the same Gortler-Healy-Thurston algorithm, the reader cannot verify the advertised probability guarantee. Please state the conversion formula (as derived from GHT Prop 5.7) and the exact procedure used in code, or provide an empirical verification of the bound on a battery of representative graphs.","section":"Section 3.2, 'Generic Rigidity'"},{"comment":"The statement that a graph is globally 2-rigid if and only if it is 3-connected and redundantly rigid omits the standard caveat for small complete graphs, and the version of 3-connectivity in use (minimum vertex count) is not specified. If the algorithm='redundancy' path is applied literally to a complete graph on three vertices, it could return False even though such graphs are globally rigid under the usual definitions. Please state the exact theorem with its vertex-count hypothesis and describe how PyRigi treats the exceptional small cases.","section":"Section 3.2, 'Global Rigidity'"},{"comment":"The paper asserts 'high test coverage' and repeatedly calls the algorithms reliable and robust, but it reports no test-results summary, no benchmarks, and no explicit validation against known graphs or frameworks. For a software paper whose central claim is practical reliability, at least one representative evaluation is needed: for example, a small table of correctness results on a suite of graphs with known rigidity/global-rigidity status, along with runtimes and any known failure modes, or a reproducible test suite with summary output. Without this, the central claim is unverified.","section":"Section 4, 'Development Tools'"}],"minor_comments":[{"comment":"There are two typos: 'summerized' should be 'summarized' and 'taylored' should be 'tailored'.","section":"Section 1, Introduction"},{"comment":"The citation for the NP-completeness of the NAC-coloring existence problem points to Garamvölgyi (2022), but the title of that paper concerns global rigidity on the line; please verify the reference and correct it if a different source is intended.","section":"Section 3.2, 'NAC-colorings'"},{"comment":"The numerical mode uses a 'predefined numeric tolerance' whose default value is not stated in the paper; please document the default tolerance and how a user-overridden tolerance affects the symbolic-versus-numerical comparison.","section":"Section 3.1, 'Equivalence and Congruence'"}],"recommendation":"major_revision","confidential_remarks":"This manuscript is a software introduction rather than a mathematical research article. The editors should consider whether the journal's software-paper policy requires an evaluation section; if so, the current submission is not yet complete. The authors' self-citations are mostly to algorithms they are implementing, which is appropriate and not a concern in itself."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe take-home: PyRigi is a genuinely useful infrastructure piece for rigidity theory, and this paper is an honest introduction to it. It deserves peer review, but the reliability claims need support before I'd trust them fully.\n\nWhat's new is the package itself. It integrates many known algorithms—Laman-type sparsity, pebble games, NAC-colorings, global rigidity checks, motion tracking—into one open-source Python library with a GUI, graph and framework databases, and documentation that ties each method to its mathematical definition. That integration is real value: earlier tools are specialized or research artifacts. The authors are explicit that the algorithms come from the literature; the contribution is scope, usability, and community infrastructure. That's appropriate for a software paper.\n\nWhat the paper does well: the documentation philosophy is sound, the examples are concrete, and the bibliography is thorough. The code is on GitHub with a described test pipeline, and the NAC-coloring and motion sections are useful overviews.\n\nThe soft spots, in proportion:\n\nFirst, the randomized generic and global rigidity methods are underspecified. The paper says the user can specify an upper bound on the false-negative probability, but it never documents how that bound is converted into the range of randomly chosen integer coordinates, nor does it give empirical evidence that the integer linear algebra achieves the advertised bound. The authors note that GHT's modular-lifting approach is not implemented. Given the abstract's claim of \"reliable and robust algorithms,\" this is a real gap. It is fixable, but as written the central reliability promise is unsupported for dimensions above two and for global rigidity.\n\nSecond, the paper states the Jackson–Jordán characterization without the small-graph caveat. As written, \"a graph is globally 2-rigid if and only if it is 3-connected and redundantly rigid\" is false for small graphs like K3. This is a minor error, but it could mislead a user who reads the math documentation.\n\nThird, there are no benchmarks, no test-results summary, and no comparison with existing software. For a package paper that is a noticeable omission. A few paragraphs on correctness tests and performance on standard graph families would be enough.\n\nThe mathematical background is standard and the implementation approach seems sound. The citation pattern, including self-citations to the authors' own algorithms, is appropriate.\n\nBottom line: this is a useful software paper with two specific technical wrinkles and a missing evaluation section. Send it to peer review, ask the authors to document the randomized method's probability parameter, fix the small-graph caveat, and add a minimal set of correctness and performance tests. Then I'd be happy to use it.","headline":"A useful, well-documented rigidity software package that merits peer review, but the paper must document the randomized methods' failure-probability conversion and fix a small misstatement of the Jackson–Jordán theorem.","tokens_in":16919,"tokens_out":4118,"would_cite":true,"duration_ms":46745,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"PyRigi is an open-source Python package that decides whether a bar-and-joint framework is rigid, globally rigid, or redundantly rigid in the plane, and computes flexes, stresses, and motions.","keywords":["rigidity theory","bar-and-joint frameworks","generic rigidity","global rigidity","redundant rigidity","infinitesimal flexes","NAC-colorings","Python package"],"falsifier":"Run the randomized generic-rigidity check many times on a graph known to be generically rigid in the plane (for example, the complete graph on four vertices) with a false-negative bound of $10^{-9}$; if any run returns False, the probability guarantee is broken. A stronger test compares randomized results with the deterministic (2,3)-tightness criterion on all graphs up to, say, eight vertices and checks that disagreements occur no more often than the requested bound.","tokens_in":16043,"feed_emoji":"📐","tokens_out":10373,"duration_ms":102374,"temperature":0.7,"pith_summary":"This paper introduces PyRigi, an open-source Python package for the rigidity and flexibility of bar-and-joint frameworks. Its central claim is that PyRigi can decide, for any graph, whether a generic planar framework has finitely many embeddings up to isometries given edge lengths, whether the embedding is unique, and whether these properties survive the removal of any edge. The package implements algorithms from the literature for generic, global, and redundant rigidity, along with tools for infinitesimal flexes, equilibrium stresses, NAC-colorings, and numerical approximation of motions. The authors argue that the software is reliable, well documented, and ready for everyday use by researchers who want to replace hand computation with a general-purpose tool.","feed_headline":"PyRigi settles rigidity questions for bar-and-joint frameworks","feed_subtitle":"Open-source package tests generic, global, and redundant rigidity and animates motions.","key_machinery":"The central object is the rigidity matrix, the Jacobian of the edge-length equations, whose kernel gives infinitesimal flexes and whose cokernel gives equilibrium stresses. The argument for reliability rests on three kinds of machinery: exact symbolic or integer linear algebra over this matrix; combinatorial criteria such as (2,3)-tightness—$|E|=2|V|-3$ with every nonempty subgraph on $n'$ vertices spanning at most $2n'-3$ edges—checked by the pebble game algorithm; and randomized generic-position checks for generic and global rigidity that never report false positives and take a user-specified false-negative bound. A distinctive mechanism of the paper is the tight coupling of each method's docstring to a precise mathematical statement, so the user knows exactly which theorem is being invoked.","core_discovery":"The paper's contribution is a working computational platform that unifies many rigidity notions in one place. On a graph, PyRigi can test generic d-rigidity, minimal rigidity, redundant and vertex-redundant rigidity, global rigidity, and weak global linkedness of vertex pairs; on a framework, it can test infinitesimal rigidity, prestress stability, and second-order rigidity, and can return bases of infinitesimal flexes and equilibrium stresses. The underlying algorithms combine exact symbolic linear algebra with randomized methods that, when used for generic and global rigidity, never give false positives and accept a user-supplied upper bound on the probability of a false negative. The package also provides graph transformations (coning, k-extensions), pebble-game sparsity checks, rigid-component decomposition, counting of complex realizations of minimally rigid graphs, and methods to compute and animate parametrized or numerically approximated motions. The claim is that this collection of features is both broad enough and reliable enough to serve as a general-purpose tool for the working mathematician.","pith_inferences":["The undocumented mapping from a requested false-negative probability to a coordinate range is the most likely failure point; a quick empirical stress test against the deterministic 2D criterion would settle whether the claimed bound is actually honored.","Because the package exposes documented definitions for each method, it could serve as a teaching platform for rigidity theory, letting students test conjectures on small graphs before proving them.","The same architecture could absorb future notions—gain graphs, symmetric frameworks, line-constrained frameworks—and the maintainers explicitly list these as future work; extending the randomized backend to modular arithmetic, as the paper notes, would probably speed up large instances."],"forward_implications":["A researcher can now check generic, global, and redundant rigidity of a graph in one environment, with deterministic or randomized backends, instead of writing custom codes.","The package turns rigidity certificates into visible objects: infinitesimal flexes and equilibrium stresses are computed and plotted, and flexible frameworks can be animated along numeric or parametric motions.","Pebble-game routines make (k,l)-sparsity and tightness checks available as building blocks for new rigidity results.","Counting complex realizations of a minimally rigid graph is exposed through a wrapper around an existing library, extending the package's reach to algebraic rigidity questions."],"supporting_citations":[{"why":"Supplies the classical (2,3)-sparsity characterization of planar rigidity used by the default `is_rigid` and `is_min_rigid`.","marker":"Pollaczek-Geiringer (1927)"},{"why":"Provides the same planar rigidity characterization in modern form, foundational for the default graph rigidity checks.","marker":"Laman (1970)"},{"why":"Gives pebble game algorithms for (k,l)-sparsity and tightness, implemented in PyRigi for rigidity and sparsity checks.","marker":"Lee and Streinu (2008)"},{"why":"Introduces the pebble game algorithm for 2D rigidity percolation, a core component of the graph-based methods.","marker":"Jacobs and Hendrickson (1997)"},{"why":"Establishes that generic global rigidity is a graph property and provides the randomized algorithm with false-negative probability bounds used by PyRigi.","marker":"Gortler, Healy, and Thurston (2010)"},{"why":"Characterizes 2D global rigidity as 3-connectivity plus redundant rigidity, giving PyRigi an alternative deterministic algorithm.","marker":"Jackson and Jordán (2005)"},{"why":"Defines prestress stability and second-order rigidity and proves that they imply continuous rigidity, supporting the corresponding PyRigi checks.","marker":"Connelly and Whiteley (1996)"},{"why":"Proves that flexible realizations correspond to NAC-colorings, the basis for PyRigi's NAC-colorings method.","marker":"Grasegger, Legerský, and Schicho (2019)"},{"why":"Provides the faster incremental NAC-coloring algorithm that the package includes.","marker":"Laštovička and Legerský (2024)"}],"fun_headline_variants":["PyRigi: one Python package for rigidity and flexibility","Test generic, global, and redundant rigidity with PyRigi","PyRigi brings rigidity theory to Python, open source","PyRigi computes rigidity and animates motions of frameworks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The randomized algorithms assume that the requested false-negative probability is correctly translated into a safe range for the randomly chosen coordinates, and that the random generator and exact integer arithmetic behave as expected; if this translation is wrong, the software could silently call a rigid graph flexible.","fun_headline_variants_meta":{"raw":{"variants":["PyRigi: one Python package for rigidity and flexibility","Test generic, global, and redundant rigidity with PyRigi","PyRigi brings rigidity theory to Python, open source","PyRigi computes rigidity and animates motions of frameworks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1508,"prompt_tokens":903,"completion_tokens":605,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":537}},"tokens_in":519,"tokens_out":605,"duration_ms":6688,"temperature":1.0,"reasoning_tokens":537,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:03:05.879306+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the randomized generic-rigidity check many times on a graph known to be generically rigid in the plane (for example, the complete graph on four vertices) with a false-negative bound of $10^{-9}$; if any run returns False, the probability guarantee is broken. A stronger test compares randomized results with the deterministic (2,3)-tightness criterion on all graphs up to, say, eight vertices and checks that disagreements occur no more often than the requested bound.","supporting_citations":[],"review_version":1}