Event Detail

A theorem of Shannon states that any multigraph of maximum degree d admits a proper edge coloring using at most 3d/2 colors. We investigate the status of this theorem in the setting of “descriptive” combinatorics. That is, we are interested in finding Borel, measurable, etc. edge colorings of Borel graphs on standard Borel spaces.

We focus on the measurable setting as this is where most of the work needed to be done. There, we obtain a full generalization of Shannon’s result: Any Borel multigraph of maximum degree d on a standard probability space admits a Borel edge coloring using at most 3d/2 colors almost everywhere. Similarly in the Baire category setting.

We also prove that losing a null/meager set is not necessary for graphs of subexponential growth rate.

The proof uses a coloring procedure first used in distributed computing by Ghaffari, Kuhn, Maus, and Uitto. In the measurable setting, the most difficult step turns out to be the following result, interesting in its own right: Let G be a Borel bipartite multigraph on a standard probability space where all vertices on one side have larger degree than all vertices on the other. Then there is a Borel matching of G covering almost all the large degree vertices. Though for measure preserving graphs this follows immediately from the well known Lyons-Nazarov theorem, the general result requires new ideas inspired by Grebik’s recent proof of the measurable Vizing’s theorem.

This is joint work with Anton Bernshteyn and Matt Bowen.