Applications are closed
for this workshop

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

This workshop, sponsored by AIM and the NSF, 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?

    This event will be run as an AIM-style workshop. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

    The deadline to apply for support to participate in this workshop has passed.

    For more information email

    Plain text announcement or brief announcement.