You are here

Enumerating interval graphs and d-representable complexes

Amzi Jeffs, Carnegie Mellon University
Wednesday, October 26, 2022 - 3:30pm to 5:00pm
PDL C-38 and via Zoom Link:
Amzi Jeffs
Amzi Jeffs


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(\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:
Meeting ID: 915 4733 5974