AI Proof WatchKeep up with AI contributions

Clique restrictions in minimally globally rigid graphs

Can an edge-minimal generically globally rigid graph in Rᵈ with at least d+3 vertices contain K_(d+2)? The conjectured exclusion retains K_(d+2) itself as the exceptional minimally globally rigid graph containing that clique.

Why it matters and what counts as progress

Why it matters: It asks how global rigidity constrains dense local subgraphs when every edge is essential.

What counts as progress: Prove the forbidden-clique structure for every dimension and allowed graph size, retaining the exceptional complete graph.

How the problem developed

  1. 1992 · Necessary conditions [1]

    Bruce Hendrickson Showed that generic global rigidity requires (d+1)-connectivity and redundant rigidity, outside the small complete-graph cases.

  2. 2005 · Sufficient condition [1]

    Robert Connelly Established a stress-matrix sufficient condition for generic global rigidity and conjectured it was also necessary.

  3. 2010 · Characterization [1]

    Steven J. Gortler, Alexander D. Healy and Dylan P. Thurston Proved Connelly’s conjecture, characterizing generic global rigidity through a stress matrix of rank n−d−1.

  4. 30 Apr 2026 · Clique restriction [2]

    Frédéric Portier Reported that an edge-minimal generically globally rigid graph in Rᵈ with at least d+3 vertices contains no K_(d+2), except the clique itself.

AI contribution

Sources

  1. Gortler, Healy and Thurston · Characterizing generic global rigidity (2010)
  2. Portier, Cliques in minimally globally rigid graphs
Website timeline

Publication dates and editorial changes.