Matthew Kwan

Office: I21.EG.111 (ground floor, office building west)
Institute of Science and Technology Austria (ISTA)
Am Campus 1
A-3400 Klosterneuburg
Austria

Hi! Since September 2021, I am Assistant Professor at ISTA.

Previously, I was Szegő Assistant Professor in the mathematics department of Stanford University. Before that, my doctoral studies were at ETH Zurich under the guidance of Benny Sudakov, and my undergraduate studies were at UNSW (Sydney), where my adviser was Catherine Greenhill. You can find my CV here.

Those looking to join my group as interns, students and postdocs should apply for the ISTern program, the IST graduate school, or the IST-BRIDGE fellowship, respectively. Currently, other applications will be considered only under exceptional circumstances and will likely not receive a response.

Selected research papers

(A complete list of papers is available here)

• Singularity of the k-core of a random graph (with Asaf Ferber, Ashwin Sah and Mehtaab Sawhney). Duke Mathematical Journal, to appear.

  On the permanent of a random symmetric matrix (with Lisa Sauermann). Selecta Mathematica 8.15 (2022).

  In these papers we resolve two conjectures of Vu on discrete random matrices. First, we prove that the permanent of a uniformly random symmetric n×n matrix with ±1 entries typically has magnitude n^{n/2 + o(n)}. Second, although very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), we prove that this is only due to “low-degree dependencies”: for any fixed k ≥ 3 and c > 0, a random graph with n vertices and edge probability c/n typically has the property that its k-core (its maximal subgraph with minimum degree at least k) is nonsingular.

• Extension complexity of low-dimensional polytopes (with Lisa Sauermann and Yufei Zhao). Transactions of the American Mathematical Society, to appear.

  Sometimes, it is possible to represent a complicated polytope as a “shadow” of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a linear projection. It is an important question to understand the extent to which the extension complexity of a polytope is controlled by its dimension, and in this paper we prove three different results along these lines. First, we show that there exists an n^o(1)-dimensional polytope with at most n facets and extension complexity n^1−o(1). Second, we obtain optimal bounds for the extension complexity of random d-polytopes, and third, we obtain an optimal upper bound for the extension complexity of cyclic polygons (all of whose vertices lie on a common circle).

  Here is a recording of a talk I gave on the results in this paper.

• High-girth Steiner triple systems (with Ashwin Sah, Mehtaab Sawhney and Michael Simkin). Submitted.

  Almost all Steiner triple systems are almost resolvable (with Asaf Ferber). Forum of Mathematics, Sigma 8:E39 (2020).

  Almost all Steiner triple systems have perfect matchings. Proceedings of the London Mathematical Society 121.6 (2020), 1468–1495.

  In the theory of combinatorial design, a Steiner triple system of order n is a system of 3-element subsets (“triples”) of a ground set of size n, such that every pair of elements in the ground set is contained in exactly one triple. In a first paper, we prove a general theorem comparing a uniformly random Steiner triple system to the outcome of the so-called triangle removal process, and use this to show that for any n divisible by 3, almost all order-n Steiner triple systems have a perfect matching (in fact, we show that almost all such Steiner triple systems have essentially the maximum possible number of perfect matchings). In a second paper, we extend these ideas to show that almost all such Steiner triple systems in fact admit a decomposition of almost all their triples into disjoint perfect matchings. That is, almost all Steiner triple systems are almost resolvable. Finally, in a third paper we prove the existence of “locally sparse” Steiner triple systems with arbitrarily high girth, resolving an old conjecture of Erdős.

  Here is a recording of one of my talks that featured two of these results.

• Halfway to Rota's basis conjecture (with Matija Bucic, Alexey Pokrovskiy and Benny Sudakov). International Mathematics Research Notices, 2020.21 (2020), 8007–8026.

  Given n bases B₁,...,B_n in an n-dimensional vector space V, a transversal basis is a basis of V containing exactly one element from each B_i. Rota's basis conjecture posits that it is always possible to find n disjoint transversal bases. In this paper we prove the partial result that one can always find (1/2 − o(1)) n disjoint transversal bases, improving on the previous record of Ω(n/log n). Our result generalises to the setting of matroids.

  Here is a recording of a talk in which I gave a fairly complete outline of the proof of this theorem.

• Proof of a conjecture on induced subgraphs of Ramsey graphs (with Benny Sudakov). Transactions of the American Mathematical Society 372 (2019), 5571–5594.

  Ramsey graphs induce subgraphs of quadratically many sizes (with Benny Sudakov). International Mathematics Research Notices 2020.6 (2020), 1621–1638.

  An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. All known constructions of Ramsey graphs involve randomness in an essential way, and there is a line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. In these papers we prove two conjectures along these lines. First, we prove that for any fixed C, every n-vertex C-Ramsey graph induces subgraphs of Θ(n²) different sizes. This resolves a conjecture of Narayanan, Sahasrabudhe and Tomon, motivated by an old problem of Erdős and McKay. Second, we prove a conjecture of Erdős, Faudree and Sós that in any n-vertex C-Ramsey graph, there are Ω(n^5/2) induced subgraphs, no pair of which have the same numbers of edges and vertices. Note: a minor oversight in the definition of “(δ,ε)-richness” has been corrected since publication of these papers. The corrected versions can be found here or on the arXiv.