Matthew Kwan

Extremal, enumerative and probabilistic results on ordered hypergraph matchings

Michael Anastos, Zhihan Jin, Matthew Kwan +1

An ordered $r$ -matching is an $r$ -uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of $r$ -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 $4 \times 4$ grid. Famously, the configuration space of this puzzle consists of two connected components, corres…

math.CO2022★ 3 cited

Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture

Matthew Kwan, Ashwin Sah, Lisa Sauermann +1

An $n$ -vertex graph is called $C$ -Ramsey if it has no clique or independent set of size $C lo g_{2} n$ (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge-sta…

math.CO2022

Substructures in Latin squares

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney +1

We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares,…

math.CO2022★ 1 cited

High-Girth Steiner Triple Systems

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney +1

We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth.

Enumerating Matroids and Linear Spaces

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney

We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(c n + o (n))^{n^{2} /6}$ , where $c=e^{…

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 $G (n, 1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its…

Large deviations in random Latin squares

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney

In this note, we study large deviations of the number $N$ of intercalates ( $2 \times 2$ combinatorial subsquares which are themselves Latin squares) in a random $n \times n$ …

math.PR2021

Singularity of the k-core of a random graph

Asaf Ferber, Matthew Kwan, Ashwin Sah +1

Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of "low-degree dependencies'' such as isolated vertices and…

Geometric and o-minimal Littlewood-Offord problems

Jacob Fox, Matthew Kwan, Hunter Spink

The classical Erdős-Littlewood-Offord theorem says that for nonzero vectors $a_{1}, \dots, a_{n} \in R^{d}$ , any $x \in R^{d}$ , and uniformly random $(ξ_1,\dots,ξ_n)\in\{-1,1…

cs.IT2020

List-decodability with large radius for Reed-Solomon codes

Asaf Ferber, Matthew Kwan, Lisa Sauermann

List-decodability of Reed-Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focu…

Singularity of sparse random matrices: simple proofs

Asaf Ferber, Matthew Kwan, Lisa Sauermann

Consider a random $n \times n$ zero-one matrix with "density" $p$ , sampled according to one of the following two models: either every entry is independently taken to be one with pro…

math.PR2020

On the permanent of a random symmetric matrix

Matthew Kwan, Lisa Sauermann

Let $M_{n}$ denote a random symmetric $n \times n$ matrix, whose entries on and above the diagonal are i.i.d. Rademacher random variables (taking values $\pm 1$ with probability $1/…

Extension complexity of low-dimensional polytopes

Matthew Kwan, Lisa Sauermann, Yufei Zhao

Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope $P$ is…

Dirac-type theorems in random hypergraphs

Asaf Ferber, Matthew Kwan

For positive integers $d < k$ and $n$ divisible by $k$ , let $m_{d} (k, n)$ be the minimum $d$ -degree ensuring the existence of a perfect matching in a $k$ -uniform hypergraph. In the gr…