dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Enumerating Interval Graphs and D-Representable Complexes

  • Start Date: March 6, 2023
  • Event Start Time: 2:00 PM
  • Event End Time: 3:00 PM
  • Seminar Series: Rutgers Discrete Mathematics Seminar
  • Presenter(s): Amzi Jeffs - Carnegie Mellon University
  • Event Location: Hill Center-Room 705
  • Event Additional Info: <p>See:&nbsp;<a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
  • Presentation Type: Stand Alone Presentation
  • 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.