Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGlobal rigidity of complete bipartite graphs
95
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
Let $mathbf{p}$ be a configuration of $n$ points in $mathbb{R}^d$ for some $n$ and some $d ge 2$. Each pair of points has a Euclidean length in the configuration. Given some graph $G$ on $n$ vertices, we measure the point-pair lengths corresponding to the edges of $G$. In this paper, we study the question of when a generic $mathbf{p}$ in $d$ dimensions will be uniquely determined (up to an unknowable Euclidean transformation) from a given set of point-pair lengths together with knowledge of $d$ and $n$. In this setting the lengths are given simply as a set of real numbers; they are not labeled with the combinatorial data that describes which point-pair gave rise to which length, nor is data about $G$ given. We show, perhaps surprisingly, that in terms of generic uniqueness, labels have no effect. A generic configuration is determined by an unlabeled set of point-pair lengths (together with $d$ and $n$) iff it is determined by the labeled edge lengths.
The symmetries of complex molecular structures can be modeled by the {em topological symmetry group} of the underlying embedded graph. It is therefore important to understand which topological symmetry groups can be realized by particular abstract graphs. This question has been answered for complete graphs; it is natural next to consider complete bipartite graphs. In previous work we classified the complete bipartite graphs that can realize topological symmetry groups isomorphic to $A_4$, $S_4$ or $A_5$; in this paper we determine which complete bipartite graphs have an embedding in $S^3$ whose topological symmetry group is isomorphic to $mathbb{Z}_m$, $D_m$, $mathbb{Z}_r times mathbb{Z}_s$ or $(mathbb{Z}_r times mathbb{Z}_s) ltimes mathbb{Z}_2$.
We compute the eigenvalue fluctuations of uniformly distributed random biregular bipartite graphs with fixed and growing degrees for a large class of analytic functions. As a key step in the proof, we obtain a total variation distance bound for the Poisson approximation of the number of cycles and cyclically non-backtracking walks in random biregular bipartite graphs, which might be of independent interest. As an application, we translate the results to adjacency matrices of uniformly distributed random regular hypergraphs.
A bar-joint framework $(G,p)$ in a (non-Euclidean) real normed plane $X$ is the combination of a finite, simple graph $G$ and a placement $p$ of the vertices in $X$. A framework $(G,p)$ is globally rigid in $X$ if every other framework $(G,q)$ in $X$ with the same edge lengths as $(G,p)$ arises from an isometry of $X$. The weaker property of local rigidity in normed planes (where only $(G,q)$ within a neighbourhood of $(G,p)$ are considered) has been studied by several researchers over the last 5 years after being introduced by Kitson and Power for $ell_p$-norms. However global rigidity is an unexplored area for general normed spaces, despite being intensely studied in the Euclidean context by many groups over the last 40 years. In order to understand global rigidity in $X$, we introduce new generalised rigid body motions in normed planes where the norm is determined by an analytic function. This theory allows us to deduce several geometric and combinatorial results concerning the global rigidity of bar-joint frameworks in $X$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
