Enumerating interval graphs and d-representable complexes

Abstract:

How many different ways can we arrange $n$ convex sets in ${\mathbf{R}}^d$? One answer is provided by counting the number of $d$-representable complexes on vertex set $[n]$. We show that there are $\exp (\mathrm{\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. 

Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.

Join Zoom Meeting: https://washington.zoom.us/j/91547335974
Meeting ID: 915 4733 5974