Final ACO Doctoral Examination and Defense of Dissertation of Xiaofan Yuan, Jun 9, 2022
Title: Matching problems in hypergraphs
Thesis draft:
https://drive.google.com/file/d/1nMDlACj81jpwYKNJEdtEsNdjqXMY_4XY/view?u...
Date: June 9, 2022 (Thursday)
Time: 10:00am EST
Location (Physical): Skiles 006
Location (Virtual): https://gatech.zoom.us/j/91659544858?pwd=SWZtVG15dGFiWEFXSHR1U0JNbVVBZz09
(Meeting ID: 916 5954 4858, Passcode: doctor)
Xiaofan Yuan
Ph.D. Candidate
Algorithms, Combinatorics, and Optimization
School of Mathematics
Georgia Institute of Technology
Committee:
Dr. Anton Bernshteyn, School of Mathematics, Georgia Institute of Technology
Dr. Hao Huang, Department of Mathematics, National University of Singapore
Dr. Santosh Vempala, College of Computing, Georgia Institute of Technology
Dr. Josephine Yu, School of Mathematics, Georgia Institute of Technology
Dr. Xingxing Yu, School of Mathematics, Georgia Institute of Technology
Advisor: Dr. Xingxing Yu, School of Mathematics, Georgia Institute of Technology
Reader: Dr. Hao Huang, Department of Mathematics, National University of Singapore
Abstract
Kühn, Osthus, and Treglown and, independently, Khan proved that if H is a 3-uniform hypergraph on n vertices, where n is a multiple of 3 and large, and the minimum vertex degree of H is greater than {(n-1) choose 2} - {2n/3 choose 2}, then H contains a perfect matching.
We show that for sufficiently large n divisible by 3, if F_1, ..., F_{n/3} are 3-uniform hypergraphs with a common vertex set and the minimum vertex degree in each F_i is greater than {(n-1) choose 2} - {2n/3 choose 2} for i = 1, ..., n/3, then the family {F_1, ..., F_{n/3}} admits a rainbow matching, i.e., a matching consisting of one edge from each F_i. This is done by converting the rainbow matching problem to a perfect matching problem in a special class of uniform hypergraphs.
We also prove that, for any integers k, l with k >= 3 and k/2 = 2k/3, n ≡ r (mod k), 0 = k, we can take m to be the minimum integer at least n/k - 2.
