Descriptive graph theory

June 27 to July 1, 2022

at the

American Institute of Mathematics, San Jose, California

organized by

Clinton Conley, Stephen Jackson, Andrew Marks, and Slawomir Solecki

Original Announcement

This workshop will be devoted to the study of descriptive graph theory, which focuses on finding definable or measurable solutions to combinatorial problems on infinite graphs.

Particular focuses of the workshop will be:

  1. Dichotomy theorems: A great deal of structure exists in the field of descriptive graph combinatorics which is absent from classical graph theory because of the prevalence of dichotomy theorems. These are results of the form that if a graph is combinatorially complicated, the complication is caused by some canonical object. Can we characterize the graphs $G$ for which there is a dichotomy characterizing when there is a Borel homomorphism to $G$ (in the class of Borel graphs)? Is there a dichotomy for when a graph has infinite chromatic number assuming the axiom of determinacy?

  2. Connections with ergodic theory: The study of the measurable combinatorics of graphs associated to group actions has had remarkable successes from relating dynamical properties of group actions with combinatorial ideas. Can we use the techniques of measurable combinatorics to make progress on ergodic theoretic problems of treeability? Does a Borel graphing of a treeable equivalence relation always have a subtreeing almost everywhere? Can local algorithms for cutting cycles in graphs be used to expand the class of groups known to have fixed price?

  3. Combinatorial problems on measurable graphs of small degrees: recent advances in the field have yielded an asymptotic understanding of several combinatorial problems as the degree of the involved graphs increases to infinity. For example, we now have an asymptotic understanding of the approximate measurable chromatic numbers of graphs of large girth. However, many of these questions remain stubbornly open for graphs of small degree. What is the measure-theoretic chromatic number of the graph arising from the free part of the Bernoulli shift of the free group on two generators? Does every acyclic $3$-regular graph admit a measure-theoretic matching?

    Material from the workshop

    A list of participants.

    The workshop schedule.

    A report on the workshop activities.

    A list of open problems.