Upcoming Events

Logic Colloquium

October 18, 2024, 4:10 PM

60 Evans Hall

Andrew Bacon
USC

Logic Colloquium

November 01, 2024, 4:10 PM

60 Evans Hall

Felix Weilacher
UC Berkeley

Shannon’s Theorem and the Unbalanced Matching Problem in the Measurable Context

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.

Logic Colloquium

November 01, 2024, 4:10 PM

60 Evans Hall

Felix Weilacher
UC Berkeley

Logic Colloquium

November 15, 2024, 4:10 PM

60 Evans Hall

Eyal Kaplan
UC Berkeley

Logic Colloquium

December 06, 2024, 4:10 PM

60 Evans Hall

Isaac Goldbring
UC Irvine

Logic Colloquium

January 24, 2025, 4:10 PM

60 Evans Hall

Alexi Block Gorman
Ohio State University

Logic Colloquium

February 14, 2025, 4:10 PM

60 Evans Hall

Gaia Belardinelli
Stanford

Logic Colloquium

February 28, 2025, 4:10 PM

60 Evans Hall

Simon Huttegger
UC Irvine

Logic Colloquium

March 14, 2025, 4:10 PM

60 Evans Hall

Eddy Keming Chen
UC Davis

Logic Colloquium

March 28, 2025, 4:10 PM

60 Evans Hall

TBD

Logic Colloquium

April 11, 2025, 4:10 PM

60 Evans Hall

Francesca Zaffora Blando
CMU

Logic Colloquium

April 25, 2025, 4:10 PM

60 Evans Hall

TBD