TCC Course "Descriptive Combinatorics"

Short Description

The course will concentrate on the emerging field of descriptive combinatorics that studies definable graphs on topological spaces and their combinatorial-type invariants (for example, the minimum number of colours needed for a proper vertex-colouring provided each colour class is Borel, or Lebesgue measurable, or has the property of Baire). This field connects combinatorics on one hand with descriptive set theory, limits of dicrete structures, measure theory, group actions, etc, on the other hand, where applications go in both directions. The survey "Descriptive Graph Combinatorics" by Alexander S. Kechris and Andrew S. Marks gives a good overview of this area. This course will concentrate on those aspects where the interplay between combinatorics and other areas of mathematics is most prominent.

Tentative List of Main Topics

Borel graphs and graphings

Graphings as limits of bounded degree graphs
* Graphings as global-local limits
* Hyperfiniteness

Borel Combinatorics

Borel greedy algorithms
Impossibility of some Borel colourings via determinacy approach
* Borel circle squaring
* Borel orbit equivalence relations

Definable solutions up to a measure-0 set

Measurable matchings in bipartite graphings with the expasion property
Measurable version of Banach-Tarski's theorem
Measurable vertex/edge colourings
Some impossibility results
* Non-invariant measures

Definable solutions up to a meager set

Banach-Tarski Paradox with pieces that have the property of Baire

* = if time permits

Prerequisites

Knowledge of the basics of graph theory, measure theory and topology will be assumed. No familiarity with descriptive set theory is required. Some suggested general references (e.g. if you need to look up a specific topic) are:

[BM] J.A.Bondy and U.S.R.Murty "Graph Theory", Springer 2008
[C] D.L.Cohn "Measure Theory", Birkhauser 2013
[K] A.S.Kechris "Classical Descriptive Set Theory", Springer 1995
[L] L.Lovasz "Large Networks and Graph Limits", American Mathematical Society, 2012
[T] A.Tserunyan "Introduction to Descriptive Set Theory", Lecture notes, 2018

Time

The lectures will take place 4-6pm on Thursdays, 17 January - 7 March 2019.

Content of lectures

17 Jan: Polish spaces and some operations preserving them, Borel hierachy, standard Borel spaces, bounded-degree Borel graphs and their basic properties.
Further reading: Chapters 3, 10 and 11 in [K]; Chapters 1 and 11 in [T]; Chapter 18.1 in [L].
24 Jan: Borel edge/vertex colourings; infinite games.
Further reading: Sections 3-4 of Kechris-Solecki-Todorcevic Borel Chromatic Numbers (Advances 1999); Chapters 13.A and 20.A in [K], Chapter 18.1 in [L]; Chapters 7.A, 11.E, 13.C in [T].
31 Jan: discussion of Borel determinacy; Marks' construction of d-regular acyclic Borel graphs without Borel d-coloring.
Further reading: 13.C in [T], Marks A determinacy approach to Borel combinatorics (JAMS 2016), Marks A short proof that an acyclic n-regular Borel graph may have Borel chromatic number n+1 (unpublished note 2013).
7 Feb: finishing Marks' proof; Baire measurable sets.
Further reading: Marks A determinacy approach to Borel combinatorics (JAMS 2016), Chapters 6.A-B and 9.A-B in [T].
14 Feb: generic ergodicity; Banach-Tarski paradox with Baire measurable pieces
Further reading: Chapter 20.D in [T]; Marks-Unger Baire measurable paradoxical decompositions via matchings (Advances 2016); Marks-Unger Baire measurable paradoxical decompositions (slides, 2015)
21 Feb: combinatorial part of Marks-Unger proof, invariant measures, graphings
Further reading: Chapter 18.2 in [L]; Marks-Unger Baire measurable paradoxical decompositions via matchings (Advances 2016); Marks-Unger Baire measurable paradoxical decompositions (slides, 2015)

28 Feb:

"Descriptive Graph Combinatorics"

Borel oracles. An analytical approach to constant-time algorithms"

7 Mar: a.e.-perfect Borel matchings in expanding bipartite graphs; measurable version of Banach-Tarski equidecomposition theorem
Further reading: Grabowski-Mathe-Pikhurko Measurable equidecompositions for group actions with an expansion property (preprint 2016); Lyons-Nazarov Perfect matchings as IID factors on non-amenable groups (Europ J Comb 2011)

Assessment

Those participants who need a grade will have to write an essay presenting one of the suggested topics (with their list to be added here later).

The aim of each essay is to understand some further results and explain them in a way accessible to other course participants.

Getting Help

If you have any course-related questions, please post them at the discussion group of the course:

https://groups.google.com/forum/#!forum/desriptive-combinatorics

Also, other messages related to the course are welcome on the group. In particular, if you see a question by somebody else and you know the answer or just want to add a comment, you are very welcome to post a follow-up message.

In order to join the group (which is open to members only), you can either request this via the group's webpage or email me.

Forthcoming Related Meetings in the UK

This course should be a useful preparation if you intend to take part in any of these meetings (especially for the second one):

Number Theory and Dynamics Conference, Cambridge, 25-29 March 2019

Workshop "Measurability, Ergodic Theory and Combinatorics", Warwick, 8-12 July 2019

Oleg Pikhurko (O dot Pikhurko at warwick dot ac dot uk)