18 papers · 1 filter
Extremal, enumerative and probabilistic results on ordered hypergraph matchings
Michael Anastos, Zhihan Jin, Matthew Kwan +1
An ordered -matching is an -uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of -dimensional o…
Partitioning problems via random processes
Michael Anastos, Oliver Cooley, Mihyun Kang +1
There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, S…
The Exact Rank of Sparse Random Graphs
Margalit Glasgow, Matthew Kwan, Ashwin Sah +1
Two landmark results in combinatorial random matrix theory, due to Komlós and Costello-Tao-Vu, show that discrete random matrices and symmetric discrete random matrices are typical…
Books, Hallways and Social Butterflies: A Note on Sliding Block Puzzles
Florestan Brunck, Matthew Kwan
Recall the classical 15-puzzle, consisting of 15 sliding blocks in a grid. Famously, the configuration space of this puzzle consists of two connected components, corres…
Note on random Latin squares and the triangle removal process
Matthew Kwan, Ashwin Sah, Mehtaab Sawhney
This is a companion note to the paper "Almost all Steiner triple systems have perfect matchings (arXiv:1611.02246). That paper contains several general lemmas about random Steiner…
Friendly bisections of random graphs
Asaf Ferber, Matthew Kwan, Bhargav Narayanan +2
Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph admits a friendly bisection of its vertex set, i.e., a partition of its…