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.