- 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

**[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

- 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: Graphings as limits of bounded degree graphs,
ergodicity, measurable chromatic numbers, Borel matchings without short augmenting paths - 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)

Chapter 18.3 in [L]; Chapters 5 and 8 in Kechris-Marks "Descriptive Graph Combinatorics" (manuscript 2018); Elek-Lippner Borel oracles. An analytical approach to constant-time algorithms" (PAMS 2010)

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

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.

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