기초과학연구원 이산수학그룹
On December 3, 2024, Yulai Ma from Paderborn University gave a talk on the existence and non-existence of many disjoint perfect matchings in regular graphs with various edge-connectivity conditions at the Discrete Math Seminar. The title of his talk was “Pairwise disjoint perfect matchings in regular graphs“.
Due to a technical issue, some parts of the video were not properly recorded.
An $r$-graph is an $r$-regular graph in which every odd set of vertices is connected to its complement by at least $r$ edges. A central question regarding $r$-graphs is determining the maximum number of pairwise disjoint perfect matchings they can contain. This talk explores how edge connectivity influences this parameter.
For ${0 \leq \lambda \leq r}$, let $m(\lambda,r)$ denote the maximum number $s$ such that every $\lambda$-edge-connected $r$-graph contains $s$ pairwise disjoint perfect matchings. The values of $m(\lambda,r)$ are known only in limited cases; for example, $m(3,3)=m(4,r)=1$, and $m(r,r) \leq r-2$ for all $r \not = 5$, with $m(r,r) \leq r-3$ when $r$ is a multiple of $4$. In this talk, we present new upper bounds for $m(\lambda,r)$ and examine connections between $m(5,5)$ and several well-known conjectures for cubic graphs.
This is joint work with Davide Mattiolo, Eckhard Steffen, and Isaak H. Wolf.