5 citations · 15 across the 13 of their papers we have counts for
6 papers · 1 filter
A note on simplicial cliques
Maria Chudnovsky, Alex Scott, Paul Seymour +1
Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is…
Optimal labelling schemes for adjacency, comparability, and reachability
Marthe Bonamy, Louis Esperet, Carla Groenland +1
We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing -vertex graphs as . This regime contains many cla…
Powers of paths in tournaments
Nemanja Draganić, François Dross, Jacob Fox +7
In this short note we prove that every tournament contains the -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also g…
Surfaces have (asymptotic) dimension 2
Marthe Bonamy, Nicolas Bousquet, Louis Esperet +3
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric,…
Finding a shortest odd hole
Maria Chudnovsky, Alex Scott, Paul Seymour
An odd hole in a graph is a induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time a…
A universal exponent for homeomorphs
Peter Keevash, Jason Long, Bhargav Narayanan +1
We prove a uniform bound on the topological Turán number of an arbitrary two-dimensional simplicial complex : any -vertex two-dimensional complex with at least $C_S n^{3-1/5}…