Upper Bounds on the Number of Eulerian Orientations of 4-Regular Graphs

In this project, we improve Schrijver’s asymptotic bound of \( {O}(6^{n/2}) \) for the number of Eulerian orientations in 4-regular loopless connected undirected graphs, where $n$ denotes the number of vertices of the graph. Specifically, we show that the number of Eulerian orientations for all connected $4$-regular graphs is at most \( {O}(2^n) \). This bound is refined for the cases of biconnected and separable graphs. These bounds are sharp; we exhibit families of graphs that attain these maximum values. Additionally, for simple graphs, we prove an upper bound of \( {O}(3^{n/2}) \) in the biconnected case and \( {O}(6^{n/3}) \) for the separable case. Our ongoing work aims to determine sharp bounds for simple graphs as well.

Bounds on the maximal number of graph embeddings

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 complex eucledian spaces. 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. 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.

An asymptotic upper bound for graph embeddings.

Published in Discrete Applied Mathematics .

New upper bounds for the number of embeddings of minimally rigid graphs.

Published in Discrete & Computational Geometry .

On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs.

Published in Applicable Algebra in Engineering, Communication and Computing (AAECC).

Source code available in zenodo .

On the maximal number of real embeddings of minimally rigid graphs in $ℝ^2$, $ℝ^3$ and $S^2$.

Published in Journal of Symbolic Computation (J.S.C.).

Summary of the project and source code is available in Jan's webpage and in zenodo .

Graph rigidity and applications .

This presentation included the methods that led to improved upper bounds on graph embedings.

Bounding the number of Roots for Multi-Homogeneous Systems

Appears in the proceedings of ISSAC 2022 .

In this presentation we relate the computation of the m-Bézout bound with constrained hypergraph orientations.

The m-Bézout Bound and Distance Geometry

Appears in the proceedings of CASC 2021 .

This presentation included results that generalize the use of graph orientations to compute the multihomogeneous bound of polynomial systems modeled by simple graphs.

Bounds on the number of embeddings of minimally rigid graphs

French Computational Geometry Days /Journées de Géométrie Algorithmique .

This presentation included results on the multi-homogeneous Bézout bounds for the embeddings of minimally rigid graphs and a conjecture on the degree of their determinantal varieties.

Algebraic and combinatorial methods for bounding the number of the complex embeddings of minimally rigid graphs

Geometric constraint systems: rigidity, flexibility and applications ( slides ).

This presentation included results on the computation of the multi-homogeneous Bézout bound for the embeddings of minimally rigid graphs and its exactness.

On the maximal number of real embeddings of spatial minimally rigid graphs

Appears in the proceedings of ISSAC 2018 (see also the slides the presentation).

The results of this work constitute a subset of our publication in J.S.C. .

Lower bounds on the maximal number of realizations

Bond-Node Structures .

This presentation is based on our article in J.S.C. and Lower Bounds on the Number of Realizations of Rigid Graphs by G.Grasegger, C.Koutschan & E.Tsigaridas.

ARCADES events

ARCADES training included a variety of events (doctoral shools, industrial and software workshops and other activities).

An overview of these events can be found here here .