Moduli spaces of geometric graphs

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≥1, let WG, d ⊆ ℝd×n denote the space of nondegenerate realizations of G in ℝd. For example, if G is the empty graph, then WG, 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 WG, d is nonempty. However, WG, d need not be connected, even when it is nonempty, and we refer to the connected components of WG, d as rigid isotopy classes of G in ℝd. We study the topology of these rigid isotopy classes. First, regarding the connectivity of WG, d, we generalize a result of Maehara that WG, d is nonempty for d ≥ n to show that WG, d is k–connected for d ≥ n+k+1, and so WG, ∞ is always contractible. While πk(WG, d)=0 for G, k fixed and d large enough, we also prove that, in spite of this, when d → ∞ the structure of the nonvanishing homology of WG, 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 WG, 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 WG, d as d tends to infinity. Finally, we give asymptotic estimates on the number of rigid isotopy classes of Rd–geometric graphs on n vertices for d fixed and n tending to infinity. When d=1 we show that asymptotically as n → ∞, 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. ©