View PDF HTML (experimental)

Abstract:We establish new properties of matroids and matroidal families associated with rigidity in dimension $2$, including the generic rigidity matroid family $\mathcal{R}$ and Kalai's hyperconnectivity matroid family $\mathcal{H}$.
Answering a question of Kalai in a strong form, we show that all connected cubic graphs, with exceptions of $K_4$ and $K_{3,3}$, are independent in every $2$-rigidity family. We also prove that $\mathcal{R}$ is the unique matroidal $2$-rigidity family in which $K_{3,3}$ is not a circuit. As a geometric corollary of this result and the Bolker-Roth theorem, it follows that $\mathcal{H}$ and $\mathcal{R}$ are the only $2$-rigidity families associated with algebraic curves in $\mathbb{R}^2$.
Bernstein used tropical geometry to characterize $\mathcal{H}$-independent graphs as those admitting an edge-ordering without directed cycles and alternating closed trails. We provide a combinatorial proof of the sufficiency direction, extending Bernstein's theorem to positive characteristic. It follows that the wedge power matroid of $n$ generic points in dimension $n-2$ does not depend on the field characteristic.
As a corollary, we obtain a new property of cubic graphs: every connected cubic graph except $K_4$ and $K_{3,3}$ has an orientation without directed and alternating cycles. The current proof of this purely graph theoretic statement relies on tropical geometry and matroid theory.

Submission history

From: Mykhaylo Tyomkyn [view email]
[v1] Thu, 12 Feb 2026 12:40:47 UTC (26 KB)
[v2] Thu, 6 Aug 2026 16:47:04 UTC (26 KB)