Consider a matroid $M$ whose ground set is equipped with a labeling to an abelian group. A basis of $M$ is called $F$-avoiding if the sum of the labels of its elements is not in a forbidden label set $F$. Hörsch, Imolay, Mizutani, Oki, and Schwarcz (2024) conjectured that if an $F$-avoiding basis exists, then any basis can be transformed into an $F$-avoiding basis by exchanging at most $|F|$ elements. This proximity conjecture is known to hold for certain specific groups; in the case where $|F| \le 2$; or when the matroid is subsequence-interchangeably base orderable (SIBO), which is a weakening of the so-called strongly base orderable (SBO) property. In this paper, we settle the proximity conjecture for sparse paving matroids or in the case where $|F| \le 4$. Related to the latter result, we present the first known example of a non-SIBO matroid. We further address the setting of multiple group-label constraints, showing proximity results for the cases of two labelings, SIBO matroids, matroids representable over a fixed, finite field, and sparse paving matroids.

Abstract. A [Formula: see text]-dimensional framework is a pair [Formula: see text], where [Formula: see text] is a graph and [Formula: see text] maps the vertices of [Formula: see text] to points in [Formula: see text]. The edges of [Formula: see text] are mapped to the corresponding line segments. A graph [Formula: see text] is said to be globally rigid in [Formula: see text] if every generic [Formula: see text]-dimensional framework [Formula: see text] is determined, up to congruence, by its edge lengths. A finer property is global linkedness: we say that a vertex pair [Formula: see text] of [Formula: see text] is globally linked in [Formula: see text] in [Formula: see text] if in every generic [Formula: see text]-dimensional framework [Formula: see text] the distance between [Formula: see text] and [Formula: see text] is uniquely determined by the edge lengths. In this paper we investigate globally linked pairs in graphs in [Formula: see text]. We give several characterizations of those rigid graphs [Formula: see text] in which a pair [Formula: see text] is globally linked if and only if there exist [Formula: see text] internally disjoint paths from [Formula: see text] to [Formula: see text] in [Formula: see text]. We call these graphs [Formula: see text]-joined. Among others, we show that [Formula: see text] is [Formula: see text]-joined if and only if for each pair of generic frameworks of [Formula: see text] with the same edge lengths, one can be obtained from the other by a sequence of partial reflections along hyperplanes determined by [Formula: see text]-separators of [Formula: see text]. We also show that the family of [Formula: see text]-joined graphs is closed under edge addition, as well as under gluing along [Formula: see text] or more vertices. As a key ingredient to our main results, we prove that rigid graphs in [Formula: see text] contain no crossing [Formula: see text]-separators. Our results give rise to new families of graphs for which global linkedness (and global rigidity) in [Formula: see text] can be tested in polynomial time.

A tensegrity graph is a graph with edges labeled as bars, cables and struts. A realization of a tensegrity graph T is a pair (T,p), where p maps the vertices of T into Rd for some d≥1. The realization is globally rigid if any realization (T,q) in Rd in which the bars have the same length and the cables and struts are not longer and not shorter, respectively, is an isometric image of (T,p). A tensegrity graph is weakly globally rigid in Rd if it has a generic globally rigid realization in Rd, and strongly globally rigid in Rd if every generic realization in Rd is globally rigid. In this paper we give a necessary condition for weak global rigidity in Rd and prove that in the d=1 case the same condition is also sufficient. In particular, our results imply that a tensegrity graph has a generic globally rigid realization in R1 if and only if it has a generic universally rigid realization in R1. We also show that recognizing strongly globally rigid tensegrity graphs in Rd is co-NP-hard for all d≥1.

Abstract A d-dimensional framework is a pair (G, p), where $$G=(V,E)$$ G = ( V , E ) is a graph and p is a map from V to $$\mathbb {R}^d$$ R d . The length of an edge $$uv\in E$$ u v ∈ E in (G, p) is the distance between p(u) and p(v). The framework is said to be globally rigid in $$\mathbb {R}^d$$ R d if every other d-dimensional framework (G, q), in which the corresponding edge lengths are the same, is congruent to (G, p). In a recent paper Gortler, Theran, and Thurston proved that if every generic framework (G, p) in $$\mathbb {R}^d$$ R d is globally rigid for some graph G on $$n\ge d+2$$ n ≥ d + 2 vertices (where $$d\ge 2$$ d ≥ 2 ), then already the set of (unlabeled) edge lengths of a generic framework (G, p), together with n, determine the framework up to congruence. In this paper we investigate the corresponding unlabeled reconstruction problem in the case when the above generic global rigidity property does not hold for the graph. We provide families of graphs G for which the set of (unlabeled) edge lengths of any generic framework (G, p) in d-space, along with the number of vertices, uniquely determine the graph, up to isomorphism. We call these graphs weakly reconstructible. We also introduce the concept of strong reconstructibility; in this case the labeling of the edges is also determined by the set of edge lengths of any generic framework. For $$d=1,2$$ d = 1 , 2 we give a partial characterization of weak reconstructibility as well as a complete characterization of strong reconstructibility of graphs. In particular, in the low-dimensional cases we describe the family of weakly reconstructible graphs that are rigid but not redundantly rigid.

A $d$-dimensional bar-and-joint framework $(G,p)$, where $G$ is a graph and $p$ maps the vertices of $G$ to points in $\mathbb{R}^d$, is said to be globally rigid if every $d$-dimensional framework $(G,q)$ with the same graph and same edge lengths is congruent to $(G,p)$. Global rigidity of frameworks and graphs is a well-studied area of rigidity theory with a number of applications, including the localization problem of sensor networks. Motivated by this application we consider the new notion of unit ball global rigidity, which can be defined similarly, except that $(G,p)$ as well as $(G,q)$ are required to be unit ball frameworks in the above definition. In a unit ball framework two vertices are adjacent if and only if their distance is less than a fixed constant (which corresponds to the sensing radius in a sensor network). In this paper we initiate a theoretical analysis of this version of global rigidity and prove several structural results. Among others we identify families of frameworks (and corresponding graphs $G$) in $\mathbb{R}^d$ for all $d\geq 1$ which are unit ball globally rigid without being globally rigid in the usual sense. These families contain minimally rigid graphs, too, which have fewer edges than any of the globally rigid graphs on the same number of vertices.