Abstract. We consider the global rigidity problem for bar-joint frameworks where each vertex is constrained to lie on a particular line in [Formula: see text]. In our setting, we allow multiple vertices to be constrained to the same line. We give a combinatorial characterization of generic rigidity in this setting for arbitrary line sets. Further, under a mild assumption on the given set of lines, we give a complete combinatorial characterization of graphs that are generically globally rigid. This gives a [Formula: see text]-dimensional extension of the well-known combinatorial characterization of two-dimensional global rigidity. In particular, our results imply that global rigidity is a generic property in this setting.

Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirected hypergraphs, Kapralov, Krauthgamer, Tardos, and Yoshida~(2022) have proved an $\varepsilon$-spectral sparsifier of the optimal $O^*(n)$ size, where $n$ is the number of vertices and $O^*$ suppresses the $\varepsilon^{-1}$ and $\log n$ factors. For directed hypergraphs, however, the optimal sparsifier size has not been known. Our main contribution is the first algorithm that constructs an $O^*(n^2)$-size $\varepsilon$-spectral sparsifier for a weighted directed hypergraph. Our result is optimal up to the $\varepsilon^{-1}$ and $\log n$ factors since there is a lower bound of $Ω(n^2)$ even for directed graphs. We also show the first non-trivial lower bound of $Ω(n^2/\varepsilon)$ for general directed hypergraphs. The basic idea of our algorithm is borrowed from the spanner-based sparsification for ordinary graphs by Koutis and Xu~(2016). Their iterative sampling approach is indeed useful for designing sparsification algorithms in various circumstances. To demonstrate this, we also present a similar iterative sampling algorithm for undirected hypergraphs that attains one of the best size bounds, enjoys parallel implementation, and can be transformed to be fault-tolerant.

In the random subgraph model we consider random subgraphs $G(t)$ of a graph $G$ obtained as follows: for each edge in $G$ we independently decide to retain the edge with probability $t$ and discard the edge with probability $1-t$ for some $0\leq t\leq 1$. A special case of this model is the Erdös--Rényi random graph model, where the host graph is the complete graph $K_n$. In this paper we analyze the rigidity properties of random subgraphs and give new upper bounds on the threshold $t_0$ for which $G(t)$ is asymptotically almost surely (a.a.s.) rigid or globally rigid when $t\geq t_0$. By specializing our results to complete host graphs we obtain, among others, that an Erdös--Rényi random graph is a.a.s. globally rigid in $\mathbb{R}^d$ if $t\geq \frac{C_d\log n}{n}$ for some constant $C_d$. We also consider random subframeworks of (bar-and-joint) frameworks, which are geometric realizations of our graphs. Our bounds for the rigidity threshold of random subgraphs are in terms of the smallest nonzero eigenvalue of the stiffness matrix of the framework, which is the Gramian of its normalized rigidity matrix. Motivated by this connection, we introduce the concept of $d$-dimensional algebraic connectivity of graphs and provide upper and lower bounds for this value of several fundamental graph classes. The case $d=1$ corresponds to the well-known algebraic connectivity, that is, the second smallest Laplacian eigenvalue of the graph. We also consider the rigidity threshold in random molecular graphs, also called bond-bending networks, which are used in the study of rigidity properties of molecules. In this model we are concerned with the rigidity of the square graph of some graph $G$. We give an upper bound for the rigidity threshold of the square of random subgraphs in terms of the algebraic connectivity of the host graph. This enables us to derive an upper bound for the rigidity threshold for sparse host graphs.

We consider the problem of characterizing the generic rigidity of bar-joint frameworks in $\mathbb{R}^d$ in which each vertex is constrained to lie in a given affine subspace. The special case when $d=2$ was previously solved by Streinu and Theran [ Discrete Comput. Geom., 44 (2020), pp. 812--837] and the case when each vertex is constrained to lie in an affine subspace of dimension $t$, and $d\geq t(t-1)$ was solved by Cruickshank et al. [ Int. Math. Res. Not. IMRN, 12 (2020), pp. 3824--3840]. We extend the latter result by showing that the given characterization holds whenever $d\geq 2t$.

A rigidity theory is developed for bar-joint frameworks in $\mathbb{R}^{d+1}$ whose vertices are constrained to lie on concentric $d$-spheres with independently variable radii. In particular, combinatorial characterizations are established for the rigidity of generic frameworks for d=1 with an arbitrary number of independently variable radii, and for $d=2$ with at most two variable radii. This includes a characterization of the rigidity or flexibility of uniformly expanding spherical frameworks in $\mathbb{R}^{3}$. Due to the equivalence of the generic rigidity between Euclidean space and spherical space, these results interpolate between rigidity in one and two dimensions and to some extent between rigidity in two and three dimensions. Symmetry-adapted counts for the detection of symmetry-induced continuous flexibility in frameworks on spheres with variable radii are also provided.

This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegative k-submodular functions. This improves upon the previous max{1/3, 1/(1 + a)}-approximation by Ward and Živný [18], where a = . We also show that for monotone k-submodular functions there is a polynomial-time k/(2k – 1)-approximation algorithm while for any ∊ > 0 a ((k + 1)/2k + ∊)-approximation algorithm for maximizing monotone k-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skewbisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

We consider planar bar-and-joint frameworks with discrete point group symmetry in which the joint positions are as generic as possible subject to the symmetry constraint. We provide combinatorial characterizations for symmetry-forced rigidity of such structures with rotation symmetry or dihedral symmetry of order 2 k with odd k , unifying and extending previous work on this subject. We also explore the matroidal background of our results and show that the matroids induced by the row independence of the orbit matrices of the symmetric frameworks are isomorphic to gain sparsity matroids defined on the quotient graph of the framework, whose edges are labeled by elements of the corresponding symmetry group. The proofs are based on new Henneberg type inductive constructions of the gain graphs that correspond to the bases of the matroids in question, which can also be seen as symmetry preserving graph operations in the original graph.

Periodic body-and-bar frameworks are abstractions of crystalline structures made of rigid bodies connected by fixed-length bars and subject to the action of a lattice of translations. We give a Maxwell--Laman characterization for minimally rigid periodic body-and-bar frameworks in terms of their quotient graphs. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.

We propose new symmetry-adapted rigidity matrices to analyze the infinitesimal rigidity of bar-joint frameworks of arbitrary-dimension with Abelian point group symmetries. These matrices define new symmetry-adapted rigidity matroids on group-labeled quotient graphs. Using these new tools, we establish combinatorial characterizations of infinitesimally rigid two-dimensional bar-joint frameworks whose joints are positioned as generically as possible subject to the symmetry constraints imposed by a reflection, a half-turn, or a threefold rotation in the plane. For bar-joint frameworks which are generic with respect to any other cyclic point group in the plane, we provide a number of necessary conditions for infinitesimal rigidity.

Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462] introduced a concept of $k$-submodular function as a generalization of ordinary submodular (set) functions and bisubmodular functions and obtained a min-max theorem for the minimization of $k$-submodular functions. Also Kuivinen [Discrete Optim., 8 (2011), pp. 459--477] considered submodular functions on (product lattices of) diamonds and showed a min-max theorem for the minimization of submodular functions on diamonds. In the present paper we consider a common generalization of $k$-submodular functions and submodular functions on diamonds, which we call a transversal submodular function (a t-submodular function, for short). We show a min-max theorem for the minimization of t-submodular functions in terms of a new norm composed of $\ell_1$ and $\ell_\infty$ norms. This reveals a relationship between the obtained min-max theorem and that for the minimization of ordinary submodular set functions due to Edmonds [Submodular functions, matroids, and certain polyhedra, in Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, New York, 1970, pp. 69--87].We also show how our min-max theorem for t-submodular functions can be used to prove the min-max theorem for $k$-submodular functions by Huber and Kolmogorov and that for submodular functions on diamonds by Kuivinen. Moreover, we show a counterexample to a characterization, given by Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462], of extreme points of the $k$-submodular polyhedron and make it a correct one by fixing a flaw therein.

We consider the problems of completing a low-rank positive semidefinite square matrix $M$ or a low-rank rectangular matrix $N$ from a given subset of their entries. Following the approach initiated by Singer and Cucuringu [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1621--1641] we study the local and global uniqueness of such completions by analyzing the structure of the graphs determined by the positions of the known entries of $M$ or $N$. We present combinatorial characterizations of local and global (unique) completability for special families of graphs. We characterize local and global completability in all dimensions for cluster graphs, i.e. graphs which can be obtained from disjoint complete graphs by adding a set of independent edges. These results correspond to theorems for body-bar frameworks in rigidity theory. We also provide a characterization of two-dimensional local completability of planar bipartite graphs, which leads to a characterization of two-dimensional local completability in the rectangular matrix model when the underlying bipartite graph is planar. These results are based on new observations that certain graph operations preserve local or global completability, as well as on a further connection between rigidity and completability. We also prove that a rank condition on the completability stress matrix of a graph is a sufficient condition for global completability. This verifies a conjecture of Singer and Cucuringu given in the paper cited above.

As an extension of a classical tree-partition problem, we consider decompositions of graphs into edge-disjoint (rooted-)trees with an additional matroid constraint. Specifically, suppose that we are given a graph $G=(V,E)$, a multiset ${\bm R} = \{r_1,\dots, r_t\}$ of vertices in $V$, and a matroid ${\cal M}$ on ${\bm R}$. We prove a necessary and sufficient condition for $G$ to be decomposed into $t$ edge-disjoint subgraphs $G_1=(V_1,T_1), \dots, G_t=(V_t,T_t)$ such that (i) for each $i$, $G_i$ is a tree with $r_i\in V_i$, and (ii) for each $v\in V$, the multiset $\{r_i\in {\bm R} \mid v\in V_i\}$ is a base of ${\cal M}$. If ${\cal M}$ is a free matroid, this is a decomposition into $t$ edge-disjoint spanning trees; thus, our result is a proper extension of Nash-Williams' tree-partition theorem. Such a matroid constraint is motivated by combinatorial rigidity theory. As a direct application of our decomposition theorem, we present characterizations of the infinitesimal rigidity of frameworks with nongeneric “boundary,” which extend classical the Laman's theorem for generic 2-rigidity of bar-joint frameworks and Tay's theorem for generic $d$-rigidity of body-bar frameworks.

Flexibility studies of macromolecules modeled as mechanical frameworks rely on computationally expensive, yet numerically imprecise simulations. Much faster approaches for degree-of-freedom counting and rigid component calculations are known for finite structures characterized by theorems of Maxwell-Laman type, but such results are exceedingly rare and difficult to obtain. The situation is even more complex for infinite, periodic structures such as those appearing in the study of crystalline materials. Here, an adequate rigidity theoretical formulation has been proposed only recently, opening the way to a combinatorial treatment.

We prove that the linear matroid that defines the generic rigidity of $d$-dimensional body-rod-bar frameworks (i.e., structures consisting of disjoint bodies and rods mutually linked by bars) can be obtained from the union of ${d+1 \choose 2}$ copies of a graphic matroid by applying variants of Dilworth truncation operations $n_r$ times, where $n_r$ denotes the number of rods. This result leads to an alternative proof of Tay's combinatorial characterizations of the generic rigidity of rod-bar frameworks and that of identified body-hinge frameworks.

A body-and-hinge framework is a structure consisting of rigid bodies connected by hinges in d-dimensional space. The generic infinitesimal rigidity of a body-and-hinge framework has been characterized in terms of the underlying graph independently by Tay and Whiteley as follows: A graph G can be realized as an infinitesimally rigid body-and-hinge framework by mapping each vertex to a body and each edge to a hinge if and only if ({d+1/2}-1)G contains {d+1/2} edge-disjoint spanning trees, where ({d+1/2}-1)G is the graph obtained from $G$ by replacing each edge by (d+1/2-1) parallel edges. In 1984 they jointly posed a question about whether their combinatorial characterization can be further applied to a nongeneric case. Specifically, they conjectured that G can be realized as an infinitesimally rigid body-and-hinge framework if and only if G can be realized as that with the additional "hinge-coplanar" property, i.e., all the hinges incident to each body are contained in a common hyperplane. This conjecture is called the Molecular Conjecture due to the equivalence between the infinitesimal rigidity of "hinge-coplanar" body-and-hinge frameworks and that of bar-and-joint frameworks derived from molecules in 3-dimension. In 2-dimensional case this conjecture has been proved by Jackson and Jordán in 2006. In this paper we prove this long standing conjecture affirmatively for general dimension. Also, as a corollary, we obtain a combinatorial characterization of the 3-dimensional bar-and-joint rigidity matroid of the square of a graph.

A non-crossing geometric graph is a graph embedded on a given set of points in the plane with non-crossing straight line segments. In this paper we present a new general framework for enumerating non-crossing geometric graphs for a given point set. By applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees and non-crossing minimally rigid frameworks. Furthermore, we also obtain efficient enumeration algorithms for non-crossing geometric graph classes, for which no enumeration algorithm has been reported so far, such as non-crossing matchings, non-crossing blue-and-red matchings, non-crossing k-vertex or k-edge connected graphs or non-crossing directed spanning trees. The proposed idea is relatively simple, and can be potentially applied to various other enumeration problems of non-crossing geometric graphs.