Videos

Algebraic and Analytic Methods in Combinatorics: Burling graphs and their generalizations

Presenter
March 20, 2025
Keywords:
  • extremal combinatorics
  • extremal graph theory
  • probabilistic combinatorics
  • discrete geometry
  • additive combinatorics
  • combinatorial geometry
  • incidence geometry
  • arithmetic progressions
  • Discrete analysis
MSC:
  • 05C25 - Graphs and abstract algebra (groups rings fields
  • etc.) [See also 20F65]
  • 05C35 - Extremal problems in graph theory [See also 90C35]
  • 05C50 - Graphs and linear algebra (matrices eigenvalues etc.)
  • 05D40 - Probabilistic methods in extremal combinatorics including polynomial methods (combinatorial Nullstellensatz etc.)
  • 52C35 - Arrangements of points flats hyperplanes (aspects of discrete geometry) [See also 14N20 32S22]
Abstract
In 1965, Burling constructed a sequence of triangle-free high-chromatic graphs that admit an intersection model by 3-dimensional boxes. In the last 12 years, Burling's construction has been used to solve several important problems in graph theory, most notably, to disprove Scott's conjecture on the chromatic number of graphs with excluded induced subdivisions. The class of graphs obtained from Burling's construction by taking all induced subgraphs, known as Burling graphs, has recently become a subject of study on its own. For instance, it is a minimal hereditary class of graphs with unbounded chromatic number—the only one known besides the "obvious" class of complete graphs. In this talk, I will present several points of view on Burling's construction, focusing or properties that make it different from other known constructions of triangle-free high-chromatic graphs. I will also present a generalization of Burling's construction that answers a recent question of Fox, Pach, and Suk, which is related to a 35-year-old conjecture that so-called k-quasi-planar graphs have linearly many edges. The latter is joint work with Aristotelis Chaniotis.