Upcoming Events
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 15, 2024, 4:10 PM
60 Evans Hall
Eyal Kaplan
UC Berkeley
The potentialist principle
A Σ2 statement ϕ is called possible if, for every ordinal alpha, ϕ holds in a generic extension which preserves Vα (set of sets of rank less than α). Woodin’s Σ2 potentialist principle is the statement that every possible Σ2 sentence is true. In a joint work with Omer Ben-Neria and Gabriel Goldberg, we proved that a supercompact cardinal suffices to force the potentialist principle. Also, the principle implies the consistency of a Woodin cardinal. In the talk, we will present the principle and sketch the proof that it can be forced from a supercompact cardinal.
Logic Colloquium
December 06, 2024, 4:10 PM
60 Evans Hall
Isaac Goldbring
UC Irvine
On the undecidability of the QWEP for C*-algebras
In his landmark 1993 paper, Kirchberg introduced a property of C*-algebras called the QWEP, which stands for “quotient of the weak expectation property.” As the name suggests, the property is defined by the fact that the algebra is a quotient of a C*-algebra with the weak expectation property, which was a property introduced by Lance years earlier in connection with the theory of tensor products of C*-algebras. While at first glance this seems to be a strange property, Kirchberg showed that whether or not every C*-algebra has the QWEP is equivalent to the famous Connes Embedding Problem (CEP) from von Neumann algebra theory. The CEP remained open for nearly 50 years until its recent refutation in 2020 via a result in quantum complexity theory (as well as the equivalence with Kirchberg’s QWEP conjecture).
Several years ago, I showed that the QWEP is an axiomatizable property of C*-algebras. In this talk, I will present joint work with Aruseelan and Hart where we show that the QWEP does not have an effective axiomatization and, in fact, there can be no effectively axiomatizable satisfiable theory of C*-algebras all of whose models have the QWEP (modulo some nontrivially conditions). The proofs use the connection with the quantum complexity results mentioned above as well as other techniques from C*-algebra theory.
Logic Colloquium
January 31, 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
May 02, 2025, 4:10 PM
60 Evans Hall
Omer Ben-Neria
UCLA