for this workshop
Descriptive graph theory
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:
- 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?
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 workshops@aimath.org
