Bounds on the maximal number of graph embeddings

Description

Rigidity theory is the branch of mathematics that studies the embeddings (or equivalently realizations) of graphs in an euclidean space or a manifold.If the number of realizations satisfying edge length constraints is finite up to rigid motions, then the embedding is called rigid, otherwise it is called flexible. These embeddings can be related to the real solutions of certain algebraic systems and their complex solutions extend the notion of rigidity to $\mathbb{C}^d$. One of the major open problems in rigidity theory is to find tight upper bounds on the numbers of rigid graph realizations in an embedding space for a given number of vertices.Given a minimally rigid graph $G(V,E)$, the upper bound of embeddings in $\mathbb{R}^d$ used to be $O\left(2^{d \cdot |V|}\right)$, while for the cases of $d=2$ and $d=3$ it has been proved that there are graphs with $\Omega\left(2.3003^{|V|}\right)$ and $\Omega\left(2.5198^{|V|}\right)$ realizations respectively. In this thesis, we display methods that reduce the gap between the existing upper bounds and asymptotic lower bounds on the maximal number of realizations on euclidean spaces or spheres.We propose two methods to compute a bound on the number of realizations using the multihomogeneous Bézout (m-Bézout) bound of well-constrained algebraic systems. The first one relates the m-Bézout bound with the number of certain oudegree-constrained graph orientations, while the second uses matrix permanent formulation. Then, we examine the exactness of these bounds on the number of complex embeddings.First with computations indicating that the m-Bézout bounds are tight for certain classes of graphs. Consequently, we exploit Bernstein's second theorem on the exactness of mixed volume, and relate it to the m-Bézout bound by analyzing the associated Newton Polytopes. Using these two methods, we improve the upper bounds on the number of graph embeddings. A first improvement is achieved for realizations of graphs in $d\geq 5$ and planar graphs in $\mathbb{C}^3$ applying existing bounds on permanents and orientations of planar graphs. Then we introduce an elimination technique on a graphical construction that further decreases these bounds in all dimensions. This approach gives $O\left(3.7764^{|V|}\right)$ and $O\left(6.8399^{|V|}\right)$ as bounds for $d=2$ and $d=3$ respectively, which is the first improvement on the asymptotic upper bound for these cases.Finally, we try to find edge lengths that can maximize the number of real embeddings in the plane, space and on the sphere for certain graphs.In order to achieve that, we use methods that sample efficiently a vast space of parameters. Our results provide a full classification according to their maximal number of real embeddings of all 7-vertex graphs in $\mathbb{R}^2$ and $\mathbb{R}^3$, while for the previously untreated case of $S^2$ we give a full characterization for all 6-vertex graphs. We also establish new asymptotic lower bounds on the maximal number of realizations (or simply lower bounds) proving that in $\mathbb{R}^2, S^2$ and $\mathbb{R}^3$ there exist graphs with $\Omega\left(2.3780^{|V|}\right)$, $\Omega\left(2.5198^{|V|}\right)$ and $\Omega\left(2.6553^{|V|}\right)$ embeddings respectively.

Abstract (French)

La théorie de la rigidité est la branche des mathématiques qui étudie les plongements (ou équivalents, les réalisations) de graphes dans un espace euclidien ou une variété. Si le nombre de réalisations satisfaisant des contraintes de longueur d'arête est fini jusqu'aux mouvements rigides, alors le plongement est appelé rigide, sinon il est appelé flexible. Ces plongements peuvent être liés aux solutions réelles de certains systèmes algébriques et leurs solutions complexes étendent la notion de rigidité à $\mathbb{C}^d$. Un des problèmes ouverts majeurs en théorie de la rigidité est de trouver des bornes supérieures serrées sur le nombre de réalisations de graphes rigides dans un espace d'incorporation pour un nombre donné de sommets. Pour un graphe minimalement rigide $G(V,E)$, la borne supérieure des plongements dans $\mathbb{R}^d$ était autrefois $O\left(2^{d \cdot |V|}\right)$, alors que pour les cas de $d=2$ et $d=3$, il a été prouvé qu'il existe des graphes avec respectivement $\Omega\left(2.3003^{|V|}\right)$ et $\Omega\left(2.5198^{|V|}\right)$ réalisations. Dans cette thèse, nous présentons des méthodes qui réduisent l'écart entre les bornes supérieures existantes et les bornes inférieures asymptotiques sur le nombre maximal de réalisations dans des espaces euclidiens ou des sphères. Nous proposons deux méthodes pour calculer une borne sur le nombre de réalisations en utilisant la borne de Bézout multihomogène (m-Bézout) de systèmes algébriques bien contraints. La première relie la borne de m-Bézout au nombre de certaines orientations de graphes contraints en degré sortant, tandis que la seconde utilise une formulation de la permanent d'une matrice. Ensuite, nous examinons la précision de ces bornes sur le nombre de plongements complexes, d'abord avec des calculs indiquant que les bornes de m-Bézout sont serrées pour certaines classes de graphes. En conséquence, nous exploitons le deuxième théorème de Bernstein sur la précision du volume mixte, et le relions à la borne de m-Bézout en analysant les polytopes de Newton associés. En utilisant ces deux méthodes, nous améliorons les bornes supérieures sur le nombre de plongements de graphes. Une première amélioration est réalisée pour les réalisations de graphes dans $d\geq 5$ et les graphes planaires dans $\mathbb{C}^3$ en appliquant des bornes existantes sur les permanents et les orientations de graphes planaires. Ensuite, nous introduisons une technique d'élimination sur une construction graphique qui réduit davantage ces bornes dans toutes les dimensions. Cette approche donne des bornes de $O\left(3.7764^{|V|}\right)$ et $O\left(6.8399^{|V|}\right)$ pour $d=2$ et $d=3$ respectivement, ce qui constitue la première amélioration de la borne supérieure asymptotique pour ces cas. Enfin, nous essayons de trouver des longueurs d'arête qui maximisent le nombre de plongements réels dans le plan, l'espace et sur la sphère pour certains graphes. Pour y parvenir, nous utilisons des méthodes qui échantillonnent efficacement un vaste espace de paramètres. Nos résultats fournissent une classification complète selon leur nombre maximal de plongements réels de tous les graphes à 7 sommets dans $\mathbb{R}^2$ et $\mathbb{R}^3$, tandis que pour le cas précédemment non traité de $S^2$, nous donnons une caractérisation complète de tous les graphes à 6 sommets. Nous établissons également de nouvelles bornes inférieures asymptotiques sur le nombre maximal de réalisations (ou simplement \emph{bornes inférieures}), prouvant qu'il existe dans $\mathbb{R}^2, S^2$ et $\mathbb{R}^3$ des graphes avec respectivement $\Omega\left(2.3780^{|V|}\right)$, $\Omega\left(2.5198^{|V|}\right)$ et $\Omega\left(2.6553^{|V|}\right)$ plongements.

Additional details