An improvement on Łuczak's connected matchings method
Speaker: Shoham Letzter
Date: Thu, Feb 4, 2021
Location: Zoom, PIMS, University of Victoria
Conference: PIMS-UVic Discrete Math Seminar
Subject: Mathematics
Class: Scientific
Date: Thu, Feb 4, 2021
Location: Zoom, PIMS, University of Victoria
Conference: PIMS-UVic Discrete Math Seminar
Subject: Mathematics
Class: Scientific
Abstract:
A connected matching is a matching contained in a connected component. A well-known method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs.
I will describe Łuczak's reduction, introduce the new reduction, and mention potential applications of the improved method.
