The strength of König's edge coloring theorem

Carl Mummert (Marshall University)

03-Sep-2020, 18:00-19:00 (5 years ago)

Abstract: König's edge coloring theorem says that a bipartite graph with maximal degree nn has an edge coloring with no more than nn colors. We study the computability theory and Reverse Mathematics of this theorem. Computable bipartite graphs with degree bounded by nn have computable edge colorings with 2n12n-1 colors, but the theorem that there is an edge coloring with nn colors is equivalent to WKL0\mathsf{WKL}_0 over RCA0\mathsf{RCA}_0. The number of colors permitted affects the computability of the solution. We obtain an additional proof of the following theorem of Paul Shafer: WKL0\mathsf{WKL}_0 is equivalent over RCA0\mathsf{RCA}_0 to the principle that a countable bipartite n-regular graph is the union of n complete matchings.

combinatoricslogic

Audience: researchers in the topic


Online logic seminar

Series comments: Description: Seminar on all areas of logic

Organizer: Wesley Calvert*
*contact for this listing

Export talk to
This website uses cookies to improve your experience.