BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Carl Mummert (Marshall University) DTSTART:20200903T180000Z DTEND:20200903T190000Z DTSTAMP:20260423T052330Z UID:OLS/21 DESCRIPTION:Title: The strength of König's edge coloring theorem\nby Carl Mummert (Marshall University) as part of Online logic seminar\n\n\nAbstract\nKönig's edge coloring theorem says that a bipartite graph with\nmaximal degree $n$ has an edge coloring with no more than $n$ colors.\nWe study the computability theory and Reverse Mathematics of this theorem. Computable bipartite grap hs with degree bounded by $n$ have computable edge colorings with $2n-1$ c olors\, but the theorem that there is an edge coloring with $n$ colors is equivalent to $\\mathsf{WKL}_0$ over $\\mathsf{RCA}_0$. The number of colo rs permitted affects the computability of the solution. We obtain an add itional proof of the following theorem of Paul Shafer: $\\mathsf{WKL}_0$ is equivalent over $\\mathsf{RCA}_0$ to the \nprinciple that a countable b ipartite n-regular graph is the union of n complete matchings.\n LOCATION:https://researchseminars.org/talk/OLS/21/ END:VEVENT END:VCALENDAR