Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.