Matthew Kwan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Matthew Kwan has a total of 42 co-authors. Here are the top co-authors by number of shared publications:
Ashwin Sah
Department of Mathematics Massachusetts Institute of Technology Cambridge Massachusetts USA
5 shared publicationsMehtaab Sawhney
Department of Mathematics Columbia University New York New York USA
5 shared publications- Ashwin Sah
Massachusetts Institute of Technology, Cambridge, USA
4 shared publications - Lisa Sauermann
Institute for Applied Mathematics University of Bonn Germany
3 shared publications - Mehtaab Sawhney
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, USA
3 shared publications - Michael Anastos
Institute of Science and Technology Austria (ISTA) Klosterneurburg Austria
3 shared publications
Latest Publications
- Open Access
- 6 October 2026
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 58 (10) , e70510
No‐(k+1)‐in‐line problem for large constant k
How many points can be placed in an grid so that every (affine) line contains at most points? We prove that for the maximum number of points is exactly . Our proof builds on the recent work of Kovács, Nagy and Szabó (who proved an analogous result when is at least about ), incorporating ideas of Jain and Pham. Using the same approach, we also obtain new bounds for higher‐dimensional extensions of this problem.
- 6 October 2026
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 58 (10) , e70510
Open AccessNo‐(k+1)‐in‐line problem for large constant k
How many points can be placed in an grid so that every (affine) line contains at most points? We prove that for the maximum number of points is exactly . Our proof builds on the recent work of Kovács, Nagy and Szabó (who proved an analogous result when is at least about ), incorporating ideas of Jain and Pham. Using the same approach, we also obtain new bounds for higher‐dimensional extensions of this problem.
- Open Access
- 28 August 2026
- Published by Springer Nature in Communications in Mathematical Physics
- Vol. 407 (10) , 214
Entangled States are Typically Incomparable
Consider a bipartite quantum system, where Alice and Bob jointly possess a pure state $$|\psi \rangle $$ . Using local quantum operations on their respective subsystems, and unlimited classical communication, Alice and Bob may be able to transform $$|\psi \rangle $$ into another state $$|\phi \rangle $$ . Famously, Nielsen’s theorem [28] provides a necessary and sufficient algebraic criterion for such a transformation to be possible (namely, the entanglement spectrum of $$|\phi \rangle $$ should majorise the entanglement spectrum of $$|\psi \rangle $$ ). In the paper where Nielsen proved this theorem, he conjectured that in the limit of large dimensionality, for almost all pairs of states $$|\psi \rangle , |\phi \rangle $$ (according to the natural unitary invariant measure) such a transformation is not possible. That is to say, typical pairs of quantum states $$|\psi \rangle , |\phi \rangle $$ are entangled in fundamentally different ways, that cannot be converted to each other via local operations and classical communication. Via Nielsen’s theorem, this conjecture can be equivalently stated as a conjecture about majorisation of spectra of random matrices from the so-called trace-normalised complex Wishart–Laguerre ensemble . Concretely, let X and Y be independent $$n \times m$$ random matrices whose entries are i.i.d. standard complex Gaussians; then Nielsen’s conjecture says that the probability that the spectrum of $$X X^\dagger / \operatorname {tr}(X X^\dagger )$$ majorises the spectrum of $$Y Y^\dagger / \operatorname {tr}(Y Y^\dagger )$$ tends to zero as both n and m grow large. We prove this conjecture, and we also confirm some related predictions of Cunden et al. [12].- 28 August 2026
- Published by Springer Nature in Communications in Mathematical Physics
- Vol. 407 (10) , 214
Open AccessEntangled States are Typically Incomparable
Consider a bipartite quantum system, where Alice and Bob jointly possess a pure state $$|\psi \rangle $$ . Using local quantum operations on their respective subsystems, and unlimited classical communication, Alice and Bob may be able to transform $$|\psi \rangle $$ into another state $$|\phi \rangle $$ . Famously, Nielsen’s theorem [28] provides a necessary and sufficient algebraic criterion for such a transformation to be possible (namely, the entanglement spectrum of $$|\phi \rangle $$ should majorise the entanglement spectrum of $$|\psi \rangle $$ ). In the paper where Nielsen proved this theorem, he conjectured that in the limit of large dimensionality, for almost all pairs of states $$|\psi \rangle , |\phi \rangle $$ (according to the natural unitary invariant measure) such a transformation is not possible. That is to say, typical pairs of quantum states $$|\psi \rangle , |\phi \rangle $$ are entangled in fundamentally different ways, that cannot be converted to each other via local operations and classical communication. Via Nielsen’s theorem, this conjecture can be equivalently stated as a conjecture about majorisation of spectra of random matrices from the so-called trace-normalised complex Wishart–Laguerre ensemble . Concretely, let X and Y be independent $$n \times m$$ random matrices whose entries are i.i.d. standard complex Gaussians; then Nielsen’s conjecture says that the probability that the spectrum of $$X X^\dagger / \operatorname {tr}(X X^\dagger )$$ majorises the spectrum of $$Y Y^\dagger / \operatorname {tr}(Y Y^\dagger )$$ tends to zero as both n and m grow large. We prove this conjecture, and we also confirm some related predictions of Cunden et al. [12]. - Open Access
- 28 January 2026
- Published by Springer Nature in Combinatorica
- Vol. 46 (1) , 5
Counting Perfect Matchings in Dirac Hypergraphs
One of the foundational theorems of extremal graph theory is Dirac’s theorem , which says that if an n -vertex graph G has minimum degree at least n /2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy, Selkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles and perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise description of the numbers of Hamilton cycles and perfect matchings in a Dirac graph G (in terms of an entropy-like parameter of G ). In this paper we extend Cuckler and Kahn’s result to perfect matchings in hypergraphs. For positive integers $$d , and for n divisible by k , let $$m_{d}(k,n)$$ be the minimum d -degree that ensures the existence of a perfect matching in an n -vertex k -uniform hypergraph. In general, it is an open question to determine (even asymptotically) the values of $$m_{d}(k,n)$$ , but we are nonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if an n -vertex k -uniform hypergraph G has minimum d -degree at least $$(1+\gamma )m_{d}(k,n)$$ (for any constant $$\gamma >0$$ ), then the number of perfect matchings in G is controlled by an entropy-like parameter of G . This strengthens cruder estimates arising from work of Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.d < k - 28 January 2026
- Published by Springer Nature in Combinatorica
- Vol. 46 (1) , 5
Open AccessCounting Perfect Matchings in Dirac Hypergraphs
One of the foundational theorems of extremal graph theory is Dirac’s theorem , which says that if an n -vertex graph G has minimum degree at least n /2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy, Selkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles and perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise description of the numbers of Hamilton cycles and perfect matchings in a Dirac graph G (in terms of an entropy-like parameter of G ). In this paper we extend Cuckler and Kahn’s result to perfect matchings in hypergraphs. For positive integers $$d , and for n divisible by k , let $$m_{d}(k,n)$$ be the minimum d -degree that ensures the existence of a perfect matching in an n -vertex k -uniform hypergraph. In general, it is an open question to determine (even asymptotically) the values of $$m_{d}(k,n)$$ , but we are nonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if an n -vertex k -uniform hypergraph G has minimum d -degree at least $$(1+\gamma )m_{d}(k,n)$$ (for any constant $$\gamma >0$$ ), then the number of perfect matchings in G is controlled by an entropy-like parameter of G . This strengthens cruder estimates arising from work of Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.d < k - Open Access
- 1 December 2025
- Published by Cambridge University Press (CUP) in Compositio Mathematica
- Vol. 161 (12) , 3089-3139
Resolution of the quadratic Littlewood–Offord problem
Consider a quadratic polynomial upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ of independent Rademacher random variables xi 1 comma ellipsis comma xi Subscript n Baseline $\xi_{1},\ldots,\xi_{n}$ . To what extent can upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ concentrate on a single value? This quadratic version of the classical Littlewood–Offord problem was popularised by Costello, Tao and Vu in their study of symmetric random matrices. In this paper, we obtain an essentially optimal bound for this problem, as conjectured by Nguyen and Vu. Specifically, if upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ ‘robustly depends on at least m of the xi Subscript i $\xi_{i}$ ’ in the sense that there is no way to pin down the value of upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ by fixing values for fewer than m of the variables xi Subscript i $\xi_{i}$ , then we have normal upper P normal r left bracket upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis equals 0 right bracket less than or equals upper O left parenthesis 1 divided by StartRoot m EndRoot right parenthesis $\mathrm{Pr}[Q(\xi_{1},\ldots,\xi_{n})=0]\le O(1/\sqrt{m})$ . This also implies a similar result in the case where xi 1 comma ellipsis comma xi Subscript n Baseline $\xi_{1},\ldots,\xi_{n}$ have arbitrary distributions. Our proof combines a number of ideas that may be of independent interest, including an inductive decoupling scheme that reduces quadratic anticoncentration problems to high-dimensional linear anticoncentration problems. Also, one application of our main result is the resolution of a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn related to graph inducibility .- 1 December 2025
- Published by Cambridge University Press (CUP) in Compositio Mathematica
- Vol. 161 (12) , 3089-3139
Open AccessResolution of the quadratic Littlewood–Offord problem
Consider a quadratic polynomial upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ of independent Rademacher random variables xi 1 comma ellipsis comma xi Subscript n Baseline $\xi_{1},\ldots,\xi_{n}$ . To what extent can upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ concentrate on a single value? This quadratic version of the classical Littlewood–Offord problem was popularised by Costello, Tao and Vu in their study of symmetric random matrices. In this paper, we obtain an essentially optimal bound for this problem, as conjectured by Nguyen and Vu. Specifically, if upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ ‘robustly depends on at least m of the xi Subscript i $\xi_{i}$ ’ in the sense that there is no way to pin down the value of upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis $Q(\xi_{1},\ldots,\xi_{n})$ by fixing values for fewer than m of the variables xi Subscript i $\xi_{i}$ , then we have normal upper P normal r left bracket upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis equals 0 right bracket less than or equals upper O left parenthesis 1 divided by StartRoot m EndRoot right parenthesis $\mathrm{Pr}[Q(\xi_{1},\ldots,\xi_{n})=0]\le O(1/\sqrt{m})$ . This also implies a similar result in the case where xi 1 comma ellipsis comma xi Subscript n Baseline $\xi_{1},\ldots,\xi_{n}$ have arbitrary distributions. Our proof combines a number of ideas that may be of independent interest, including an inductive decoupling scheme that reduces quadratic anticoncentration problems to high-dimensional linear anticoncentration problems. Also, one application of our main result is the resolution of a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn related to graph inducibility . - Open AccessNo-$(k+1)$-in-line problem for large constant $k$How many points can be placed in an $n\times n$ grid so that every (affine) line contains at most $k$ points? We prove that for $n \ge k \ge 10^{37}$ the maximum number of points is exactly $kn$. Our proof builds on the recent work of Kovács, Nagy, and Szabó (who proved an analogous result when $k$ is at least about $\sqrt{n \log n}$), incorporating ideas of Jain and Pham. Using the same approach, we also obtain new bounds for higher-dimensional extensions of this problem.Open AccessNo-$(k+1)$-in-line problem for large constant $k$How many points can be placed in an $n\times n$ grid so that every (affine) line contains at most $k$ points? We prove that for $n \ge k \ge 10^{37}$ the maximum number of points is exactly $kn$. Our proof builds on the recent work of Kovács, Nagy, and Szabó (who proved an analogous result when $k$ is at least about $\sqrt{n \log n}$), incorporating ideas of Jain and Pham. Using the same approach, we also obtain new bounds for higher-dimensional extensions of this problem.
- Open Access
On random matrices with large corank
Let $1\le k\le n$ and $M$ be a random $n\times n$ matrix with independent uniformly random $\{\pm 1\}$-entries. We show that there exists an absolute constant $c > 0$ such that \[\mathbf{P}[\operatorname{rank}(M)\le n-k]\le \exp(-c nk).\]Open AccessOn random matrices with large corank
Let $1\le k\le n$ and $M$ be a random $n\times n$ matrix with independent uniformly random $\{\pm 1\}$-entries. We show that there exists an absolute constant $c > 0$ such that \[\mathbf{P}[\operatorname{rank}(M)\le n-k]\le \exp(-c nk).\] - Open Access
Exponential anticoncentration of the permanent
Let $A\in\mathbb{R}^{n\times n}$ be a random matrix with independent entries, and suppose that the entries are "uniformly anticoncentrated" in the sense that there is a constant $\varepsilon>0$ such that each entry $a_{ij}$ satisfies $\sup_{z}\Pr[a_{ij}=z]\le1-\varepsilon$ (for example, $A$ could be a uniformly random $n\times n$ matrix with $\pm1$ entries). Significantly improving previous bounds of Tao and Vu, we prove that the permanent of $A$ is exponentially anticoncentrated: there is $c_{\varepsilon}>0$ such that $\sup_{z}\Pr[\operatorname{per}(A)=z]\le\exp(-c_{\varepsilon}n)$. Our proof also works for the determinant, giving an alternative proof of a classical theorem of Kahn, Komlós and Szemerédi. As a consequence, we see that there are at least exponentially many different permanents of $n\times n$ matrices with $\pm1$ entries, resolving a problem of Ingram and Razborov.Open AccessExponential anticoncentration of the permanent
Let $A\in\mathbb{R}^{n\times n}$ be a random matrix with independent entries, and suppose that the entries are "uniformly anticoncentrated" in the sense that there is a constant $\varepsilon>0$ such that each entry $a_{ij}$ satisfies $\sup_{z}\Pr[a_{ij}=z]\le1-\varepsilon$ (for example, $A$ could be a uniformly random $n\times n$ matrix with $\pm1$ entries). Significantly improving previous bounds of Tao and Vu, we prove that the permanent of $A$ is exponentially anticoncentrated: there is $c_{\varepsilon}>0$ such that $\sup_{z}\Pr[\operatorname{per}(A)=z]\le\exp(-c_{\varepsilon}n)$. Our proof also works for the determinant, giving an alternative proof of a classical theorem of Kahn, Komlós and Szemerédi. As a consequence, we see that there are at least exponentially many different permanents of $n\times n$ matrices with $\pm1$ entries, resolving a problem of Ingram and Razborov. - Open Access
Parities in random Latin squares
In a Latin square, every row can be interpreted as a permutation, and therefore has a parity (even or odd). We prove that in a uniformly random $n\times n$ Latin square, the $n$ row parities are very well approximated by a sequence of $n$ independent unbiased coin flips: for example, the total variation error of this approximation tends to zero as $n\to\infty$. This resolves a conjecture of Cameron. In fact, we prove a generalisation of Cameron's conjecture for the joint distribution of the row parities, column parities and symbol parities (the latter are defined by the symmetry between rows, columns and symbols of a Latin square). Along the way, we introduce several general techniques for the study of random Latin squares, including a new re-randomisation technique via `stable intercalate switchings', and a new approximation theorem comparing random Latin squares with a certain independent model.Open AccessParities in random Latin squares
In a Latin square, every row can be interpreted as a permutation, and therefore has a parity (even or odd). We prove that in a uniformly random $n\times n$ Latin square, the $n$ row parities are very well approximated by a sequence of $n$ independent unbiased coin flips: for example, the total variation error of this approximation tends to zero as $n\to\infty$. This resolves a conjecture of Cameron. In fact, we prove a generalisation of Cameron's conjecture for the joint distribution of the row parities, column parities and symbol parities (the latter are defined by the symmetry between rows, columns and symbols of a Latin square). Along the way, we introduce several general techniques for the study of random Latin squares, including a new re-randomisation technique via `stable intercalate switchings', and a new approximation theorem comparing random Latin squares with a certain independent model. - 2 September 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
The exact rank of sparse random graphs
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 typically nonsingular. In particular, in the language of graph theory, when p is a fixed constant, the biadjacency matrix of a random Erdős–Rényi bipartite graph \mathbb{G}(n,n,p) and the adjacency matrix of an Erdős–Rényi random graph \mathbb{G}(n,p) are both nonsingular with high probability. However, very sparse random graphs (i.e., where p is allowed to decay rapidly with n ) are typically singular, due to the presence of “local” dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbour. In this paper, we give a combinatorial description of the rank of a sparse random graph \mathbb{G}(n,n,c/n) or \mathbb{G}(n,c/n) in terms of such local dependencies, for all constants c\ne e (and we present some evidence that the situation is very different for c=e ). This gives an essentially complete answer to a question raised by Vu (2014). As applications of our main theorem and its proof, we also determine the asymptotic singularity probability of the 2-core of a sparse random graph, we show that the rank of a sparse random graph is extremely well approximated by its matching number, and we deduce a central limit theorem for the rank of \mathbb{G}(n,c/n) .
- 2 September 2025
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
The exact rank of sparse random graphs
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 typically nonsingular. In particular, in the language of graph theory, when p is a fixed constant, the biadjacency matrix of a random Erdős–Rényi bipartite graph \mathbb{G}(n,n,p) and the adjacency matrix of an Erdős–Rényi random graph \mathbb{G}(n,p) are both nonsingular with high probability. However, very sparse random graphs (i.e., where p is allowed to decay rapidly with n ) are typically singular, due to the presence of “local” dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbour. In this paper, we give a combinatorial description of the rank of a sparse random graph \mathbb{G}(n,n,c/n) or \mathbb{G}(n,c/n) in terms of such local dependencies, for all constants c\ne e (and we present some evidence that the situation is very different for c=e ). This gives an essentially complete answer to a question raised by Vu (2014). As applications of our main theorem and its proof, we also determine the asymptotic singularity probability of the 2-core of a sparse random graph, we show that the rank of a sparse random graph is extremely well approximated by its matching number, and we deduce a central limit theorem for the rank of \mathbb{G}(n,c/n) .
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2098-2106
Smoothed Analysis for Graph Isomorphism
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2098-2106
Open AccessSmoothed Analysis for Graph Isomorphism