Measurable edge-colourings of graphings

Graphs, Hypergraphs, and Computing

16 January 15:30 - 16:30

Oleg Pikhurko - University of Warwick

Consider a graph G=(X,E) on a standard Borel space X with maximum degree bounded by d whose edge set E is a Borel subset of X^2. It is known that G admits a Borel edge-colouring with 2d-1 colours (Kechris-Solecki-Todorcevic 1999) but not always with 2d-2 colours (Marks 2013). Suppose additionally that we have a probability measure on X such that G is a graphing (i.e. it can be represented by finitely many measure-preserving maps). Then there is a measurable d+o(d) edge-colouring. This is a joint work with Endre Csoka and Gabor Lippner.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to