Descriptive graph theory
June 27 to July 1, 2022
American Institute of Mathematics,
San Jose, California
and Slawomir Solecki
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:
- 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?
- 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?
- 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.