English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of combinatorially determining the rank of the 3-dimensionalbar-joint {\em rigidity matroid} of a graph is an important open problem incombinatorial rigidity theory. Maxwell's condition states that the edges of agraph $G=(V, E)$ are {\em independent} in its $d$-dimensional generic rigiditymatroid only if $(a)$ the number of edges $|E|$ $\le$ $d|V| - {d+1\choose 2}$,and $(b)$ this holds for every induced subgraph with at least $d$ vertices. Wecall such graphs {\em Maxwell-independent} in $d$ dimensions. Laman's theoremshows that the converse holds for $d=2$ and thus every maximalMaxwell-independent set of $G$ has size equal to the rank of the 2-dimensionalgeneric rigidity matroid. While this is false for $d=3$, we show that everymaximal, Maxwell-independent set of a graph $G$ has size at least the rank ofthe 3-dimensional generic rigidity matroid of $G$. This answers a questionposed by Tib\'or Jord\'an at the 2008 rigidity workshop at BIRS\cite{bib:birs}.  Along the way, we construct subgraphs (1) that yield alternative formulae fora rank upper bound for Maxwell-independent graphs and (2) that contain amaximal (true) independent set. We extend this bound to special classes ofnon-Maxwell-independent graphs. One further consequence is a simpler proof ofcorrectness for existing algorithms that give rank bounds.

Maxwell-independence: a new rank estimate for 3D rigidity matroids