2026/07/28 by Bill Jackson, Tibor Jordán, Soma Villányi
Mathematics · #math.CO #msc:52C25
arxiv created 2026/07/28 · arxiv updated 2026/07/30
The problems of characterizing the graphs G which are generically rigid in \mathbb Rd, or more generally, determining the rank function of the d-dimensional rigidity matroid \cal Rd(G) of an arbitrary graph G, have been solved when d≤ 2 but are major open problems in discrete geometry when d≥ 3. In this paper we shall concentrate on the case when d=3. We first revisit a conjecture of Dress from 1987 that the rank of the \cal R3-closure of a graph G is determined by its maximal complete subgraphs of size at least five. We show that his conjectured value for the rank of the closure gives an upper bound on the actual value. We also deduce that the truth of this conjecture would imply a good characterization of the rank of \cal R3(G) for all graphs G. The rank formula in Dress's conjecture leads us to consider the family of Kt-covered graphs, i.e., graphs in which every edge belongs to a complete subgraph Kt, for some t≥ 3. This family contains several well-studied graph classes such as body-pin graphs, combinatorial zeolites, and molecular graphs. We introduce a new notion of rank contributions of vertices in an arbitrary matroid on the edge set of a graph G, and use it to obtain lower bounds on the rank contributions of vertices in \cal R3(G) and \cal C12(G) when G is Kt-covered. We use these bounds to show that a conjectured min-max formula for the rank of body-pin graphs in \cal R3 holds for the C21-cofactor matroid (which is conjectured by Whiteley to be equal to \cal R3), and to obtain new sufficient connectivity conditions for the (global) rigidity of K4- and K5-covered graphs in \mathbb R3.