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, W G,d ⊆ R d×n denotes the space of nondegenerate realizations of G in R d .For example if G is the empty graph then W G,d is homotopy equivalent to the configuration space of n points in R d .Questions about when a certain graph G exists as a geometric in R 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 R 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 ≥ n to show that W G,d is k-connected for d ≥ n + k + 1, and so WG,∞ 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 ∞ 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)-many equally spaced clusters in degrees between dn 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 R dgeometric 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.