MKMatthew Kwan

Matthew Kwan

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Matthew Kwan has a total of 42 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    No‐(k+1)‐in‐line problem for large constant k

    by Alexandr Grebennikov, Matthew Kwan

    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

    Entangled States are Typically Incomparable

    by Vishesh Jain, Matthew Kwan, Marcus Michelen

    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$$ n × 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 )$$ X X † / tr ( X X † ) majorises the spectrum of $$Y Y^\dagger / \operatorname {tr}(Y Y^\dagger )$$ Y Y † / tr ( Y Y † ) 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

    Counting Perfect Matchings in Dirac Hypergraphs

    by Matthew Kwan, Roodabeh Safavi, Yiting Wang

    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 d < k , and for n divisible by k , let $$m_{d}(k,n)$$ 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)$$ 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)$$ ( 1 + γ ) m d ( k , n ) (for any constant $$\gamma >0$$ γ > 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.

  • Open Access

    Resolution of the quadratic Littlewood–Offord problem

    by Matthew Kwan, Lisa Sauermann

    Consider a quadratic polynomial upper Q left parenthesis xi 1 comma ellipsis comma xi Subscript n Baseline right parenthesis Q ( ξ 1 , … , ξ n ) $Q(\xi_{1},\ldots,\xi_{n})$ of independent Rademacher random variables xi 1 comma ellipsis comma xi Subscript n Baseline ξ 1 , … , ξ n $\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 ( ξ 1 , … , ξ n ) $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 ( ξ 1 , … , ξ n ) $Q(\xi_{1},\ldots,\xi_{n})$ ‘robustly depends on at least m of the xi Subscript i ξ 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 ( ξ 1 , … , ξ n ) $Q(\xi_{1},\ldots,\xi_{n})$ by fixing values for fewer than m of the variables xi Subscript i ξ 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 P r [ Q ( ξ 1 , … , ξ n ) = 0 ] ≤ O ( 1 / m ) $\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 ξ 1 , … , ξ n $\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 Access

    No-$(k+1)$-in-line problem for large constant $k$

    by Alexandr Grebennikov, Matthew Kwan

    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

    by Zach Hunter, Matthew Kwan, Lisa Sauermann, Mehtaab Sawhney

    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

    by Zach Hunter, Matthew Kwan, Lisa Sauermann

    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

    by Matthew Kwan, Kalina Petrova, Mehtaab Sawhney

    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.

  • The exact rank of sparse random graphs

    by Margalit Glasgow, Matthew Kwan, Ashwin Sah, Mehtaab Sawhney

    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

    Smoothed Analysis for Graph Isomorphism

    by Michael Anastos, Matthew Kwan, Benjamin Moore