Richard P. Stanley Seminar in Combinatorics: Asymptotic separation index as a tool in descriptive combinatorics

SEMINARS, HARVARD-MIT COMBINATORICS

Speaker:

Anton Bernshteyn - Georgia Tech

A common theme throughout mathematics is the search for "constructive" solutions to problems as opposed to mere existence results. For problems over R and other well-behaved spaces, this idea is nicely captured by the concept of a Borel construction. In particular, one can investigate Borel solutions to classical combinatorial problems such as graph colorings, perfect matchings, etc. The area studying these questions is called descriptive combinatorics. As I will explain in the talk, many facts in graph theory that we know and love---for example, Brooks’ theorem---turn out to be inherently "non-constructive" in this sense. The main result of this talk is that Borel versions of various classical combinatorial theorems nevertheless hold on graphs that can, in some sense, be easily decomposed into subgraphs with finite components. No prior familiarity with Borel combinatorics or descriptive set theory will be assumed. Based on joint work with Felix Weilacher.

===============================

For more info, see https://math.mit.edu/combin/