Enumeration of interval graphs and d-representable complexes (Amzi Jeffs, CMU)

Combinatorics Seminar
Friday, April 12, 2024 - 3:15pm for 1 hour (actually 50 minutes)
Amzi Jeffs – Carnegie Mellon University – amzij@cmu.eduhttps://www.math.cmu.edu/~amzij/
Evelyne Smith-Roberge

How many different ways can we arrange n convex sets in R^d? One answer is provided by counting the number of d-representable complexes on vertex set [n]. We show that there are exp(Theta(n^d log n))-many such complexes, and provide bounds on the constants involved. As a consequence, we show that d-representable complexes comprise a vanishingly small fraction of the class of d-collapsible complexes. In the case d = 1 our results are more precise, and improve the previous best estimate for the number of interval graphs.