This note gives a detailed proof of the following statement. Let $din mathbb{N}$ and $m,n ge d + 1$, with $m + n ge binom{d+2}{2} + 1$. Then the complete bipartite graph $K_{m,n}$ is generically globally rigid in dimension $d$.
We show that universal rigidity of a generic bar and joint framework (G,p) in the line depends on more than the ordering of the vertices. In particular, we construct examples of one-dimensional generic frameworks with the same graph and ordering of t
he vertices, such that one is universally rigid and one is not. This answers, in the negative, a question of Jordan and Nguyen.
Let $G$ be a $3$-connected graph with $n$ vertices and $m$ edges. Let $mathbf{p}$ be a randomly chosen mapping of these $n$ vertices to the integer range $[1..2^b]$ for $bge m^2$. Let $mathbf{l}$ be the vector of $m$ Euclidean lengths of $G$s edges u
nder $mathbf{p}$. In this paper, we show that, WHP over $mathbf{p}$, we can efficiently reconstruct both $G$ and $mathbf{p}$ from $mathbf{l}$. In contrast to this average case complexity, this reconstruction problem is NP-HARD in the worst case. In fact, even the labeled version of this problem (reconstructing $mathbf{p}$ given both $G$ and $mathbf{l}$) is NP-HARD. We also show that our results stand in the presence of small amounts of error in $mathbf{l}$, and in the real setting with approximate length measurements. Our method is based on older ideas that apply lattice reduction to solve certain SUBSET-SUM problems, WHP. We also rely on an algorithm of Seymour that can efficiently reconstruct a graph given an independence oracle for its matroid.
Suppose one has a collection of disks of various sizes with disjoint interiors, a packing, in the plane, and suppose the ratio of the smallest radius divided by the largest radius lies between $1$ and $q$. In his 1964 book textit{Regular Figures} (MR
0165423), Laszlo Fejes Toth found a series of packings that were his best guess for the maximum density for any $1> q > 0.2$. Meanwhile Gerd Blind in (MR0275291,MR0377702) proved that for $1ge q > 0.72$, the most dense packing possible is $pi/sqrt{12}$, which is when all the disks are the same size. In (MR0165423), the upper bound of the ratio $q$ such that the density of his packings greater than $pi/sqrt{12}$ that Fejes Toth found was $0.6457072159..$. Here we improve that upper bound to $0.6585340820..$. Our new packings are based on a perturbation of a triangulated packing that have three distinct sizes of disks, found by Fernique, Hashemi, and Sizova, (MR4292755), which is something of a surprise.
We show that a jammed packing of disks with generic radii, in a generic container, is such that the minimal number of contacts occurs and there is only one dimension of equilibrium stresses. We also point out some connections to packings with differe
nt radii and results in the theory of circle packings whose graph forms a triangulation of a given topological surface. We also point out a counterexample, due to F. Nazarov, to a previous conjecture that that triangulated packings with fixed numbers of disks with fixed numbers of disks for each radius claiming that such packings were the most dense.
We prove that if a framework of a graph is neighborhood affine rigid in $d$-dimensions (or has the stronger property of having an equilibrium stress matrix of rank $n-d-1$) then it has an affine flex (an affine, but non Euclidean, transform of space
that preserves all of the edge lengths) if and only if the framework is ruled on a single quadric. This strengthens and also simplifies a related result by Alfakih. It also allows us to prove that the property of super stability is invariant with respect to projective transforms and also to the coning and slicing operations. Finally this allows us to unify some previous results on the Strong Arnold Property of matrices.
We prove that universal second-order rigidity implies universal prestress stability and that triangulated convex polytopes in three-space (with holes appropriately positioned) are prestress stable.
We describe a very simple condition that is necessary for the universal rigidity of a complete bipartite framework $(K(n,m),p,q)$. This condition is also sufficient for universal rigidity under a variety of weak assumptions, such as general position.
Even without any of these assumptions, in complete generality, we extend these ideas to obtain an efficient algorithm, based on a sequence of linear programs, that determines whether an input framework of a complete bipartite graph is universally rigid or not.
