Moduli spaces of geometric graphs

Belotti, Mara; Lerario, Antonio; Newman, Andrew

doi:10.2140/agt.2024.24.2039

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the Journal

Editorial Board

Subscriptions

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1472-2739 (online)

ISSN 1472-2747 (print)

Author Index

To Appear

Other MSP Journals

Moduli spaces of geometric graphs

Mara Belotti, Antonio Lerario and Andrew Newman

Algebraic & Geometric Topology 24 (2024) 2039–2090

DOI: 10.2140/agt.2024.24.2039

Abstract

We define a new family of graph invariants, studying the topology of the moduli space of their geometric realizations in Euclidean spaces, using a limiting procedure reminiscent of Floer homology.

Given a labeled graph $G$ on $n$ vertices and $d \geq 1$ , let $W_{G, d} \subseteq ℝ^{d \times n}$ denote the space of nondegenerate realizations of $G$ in $ℝ^{d}$ . For example, if $G$ is the empty graph, then $W_{G, d}$ is homotopy equivalent to the configuration space of $n$ points in $ℝ^{d}$ . Questions about when a certain graph $G$ exists as a geometric graph in $ℝ^{d}$ have been considered in the literature and in our notation have to do with deciding when $W_{G, d}$ is nonempty. However, $W_{G, d}$ need not be connected, even when it is nonempty, and we refer to the connected components of $W_{G, d}$ as rigid isotopy classes of $G$ in $ℝ^{d}$ . We study the topology of these rigid isotopy classes. First, regarding the connectivity of $W_{G, d}$ , we generalize a result of Maehara that $W_{G, d}$ is nonempty for $d \geq n$ to show that $W_{G, d}$ is $k$ –connected for $d \geq n + k + 1$ , and so $W_{G, \infty}$ is always contractible.

While $π_{k} (W_{G, d}) = 0$ for $G, k$ fixed and $d$ large enough, we also prove that, in spite of this, when $d \to \infty$ the structure of the nonvanishing homology of $W_{G, d}$ exhibits a stabilization phenomenon. The nonzero part of its homology is concentrated in at most $n - 1$ equally spaced clusters in degrees between $d - n$ and $(n - 1) (d - 1)$ , and whose structure does not depend on $d$ , for $d$ large enough. This leads to the definition of a family of graph invariants, capturing the asymptotic structure of the homology of the rigid isotopy class. For instance, the sum of the Betti numbers of $W_{G, d}$ does not depend on $d$ for $d$ large enough; we call this number the Floer number of the graph $G$ . This terminology comes by analogy with Floer theory, because of the shifting phenomenon in the degrees of positive Betti numbers of $W_{G, d}$ as $d$ tends to infinity.

Finally, we give asymptotic estimates on the number of rigid isotopy classes of $ℝ^{d}$ –geometric graphs on $n$ vertices for $d$ fixed and $n$ tending to infinity. When $d = 1$ we show that asymptotically as $n \to \infty$ , each isomorphism class corresponds to a constant number of rigid isotopy classes, on average. For $d > 1$ we prove a similar statement at the logarithmic scale.

Keywords

geometric graphs, semialgebraic sets, Betti numbers, graph invariant, Floer homology

Mathematical Subject Classification

Primary: 14P10, 55R80

Secondary: 05C30

References

Publication

Received: 18 February 2022

Revised: 24 March 2023

Accepted: 11 April 2023

Published: 16 July 2024

Authors

Mara Belotti
SISSA Trieste Italy	Chair of Discrete Mathematics/Geometry Technische Universität Berlin Berlin Germany

Antonio Lerario
SISSA Trieste Italy

Andrew Newman
Chair of Discrete Mathematics/Geometry Technische Universität Berlin Berlin Germany	Department of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA United States

Open Access made possible by participating institutions via Subscribe to Open.

Volume 24, issue 4 (2024)