Seminars & Colloquia Calendar
Enumerating interval graphs and d-representable complexes
Amzi Jeffs (Carnegie Mellon)
Location: Hill Center Room 705
Date & time: Monday, 06 March 2023 at 2:00PM - 3:00PM
Abstract: 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 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. These results are joint work with Boris Bukh.