@inproceedings{20007, abstract = {There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph.}, author = {Anastos, Michael and Kwan, Matthew Alan and Moore, Benjamin}, booktitle = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing}, isbn = {9798400715105}, issn = {0737-8017}, location = {Prague, Czechia}, pages = {2098--2106}, publisher = {Association for Computing Machinery}, title = {{Smoothed analysis for graph isomorphism}}, doi = {10.1145/3717823.3718173}, year = {2025}, } @article{20504, abstract = {Let r, k, be integers such that 0 ≤ ≤ (k/r). Given a large r-uniform hypergraph G, we consider the fraction of k-vertex subsets that span exactly edges. If is 0 or (k/r), this fraction can be exactly 1 (by taking G to be empty or complete), but for all other values of , one might suspect that this fraction is always significantly smaller than 1. In this paper we prove an essentially optimal result along these lines: if is not 0 or (k/r), then this fraction is at most (1/e) + ε, assuming k is sufficiently large in terms of r and ε > 0, and G is sufficiently large in terms of k. Previously, this was only known for a very limited range of values of r, k, (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujic). Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested this as a hypergraph generalization of their edge-statistics conjecture. We also prove a much stronger bound when is far from 0 and (k/r).}, author = {Jain, Vishesh and Kwan, Matthew Alan and Mubayi, Dhruv and Tran, Tuan}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {18}, publisher = {Oxford University Press}, title = {{The edge-statistics conjecture for hypergraphs}}, doi = {10.1093/imrn/rnaf273}, volume = {2025}, year = {2025}, } @article{18753, abstract = {We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs C, a hero in C is any digraph H such that H -free digraphs in C have bounded dichromatic number. We show that if F is an oriented star of degree at least five, the only heroes for the class of F -free digraphs are transitive tournaments. For oriented stars F of degree exactly four, we show the only heroes in F -free digraphs are transitive tournaments, or possibly special joins of transitive tournaments. Aboulker et al. characterized the set of heroes of {H,K1+P2→} -free digraphs almost completely, and we show the same characterization for the class of {H,rK1+P3→} -free digraphs. Lastly, we show that if we forbid two "valid" orientations of brooms, then every transitive tournament is a hero for this class of digraphs.}, author = {Carbonero, Alvaro and Koerts, Hidde and Moore, Benjamin and Spirkl, Sophie}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{On heroes in digraphs with forbidden induced forests}}, doi = {10.1016/j.ejc.2024.104104}, volume = {125}, year = {2025}, } @article{19433, abstract = {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 orders. The theory of ordered 2-matchings is well developed and has connections and applications to extremal and enumerative combinatorics, probability and geometry. On the other hand, in the case r≥3 much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński made some first steps towards a general theory of ordered r-matchings, and in this paper we substantially improve several of their results and introduce some new directions of study. Many intriguing open questions remain.}, author = {Anastos, Michael and Jin, Zhihan and Kwan, Matthew Alan and Sudakov, Benny}, issn = {2050-5094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{Extremal, enumerative and probabilistic results on ordered hypergraph matchings}}, doi = {10.1017/fms.2024.144}, volume = {13}, year = {2025}, } @article{19554, abstract = {In 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erdős–Rényi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthening this classical result, and answering a question of Aronson, Frieze and Pittel, we prove a central limit theorem in the same setting: the fluctuations in the matching number of a sparse random graph are asymptotically Gaussian. Our new contribution is to prove this central limit theorem in the subcritical and critical regimes, according to a celebrated algorithmic phase transition first observed by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem has recently been proved in the PhD thesis of Kreačić, using a stochastic generalisation of the differential equation method (comparing the so-called Karp–Sipser process to a system of stochastic differential equations). Our proof builds on these methods, and introduces new techniques to handle certain degeneracies present in the subcritical and critical cases. Curiously, our new techniques lead to a non-constructive result: we are able to characterise the fluctuations of the matching number around its mean, despite these fluctuations being much smaller than the error terms in our best estimates of the mean. We also prove a central limit theorem for the rank of the adjacency matrix of a sparse random graph.}, author = {Glasgow, Margalit and Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {4}, publisher = {Wiley}, title = {{A central limit theorem for the matching number of a sparse random graph}}, doi = {10.1112/jlms.70101}, volume = {111}, year = {2025}, } @article{21263, abstract = {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 G(n,n,p) and the adjacency matrix of an Erdős–Rényi random graph 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 G(n,n,c/n) or G(n,c/n) in terms of such local dependencies, for all constants c=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 G(n,c/n).}, author = {Glasgow, Margalit and Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab}, issn = {1435-9863}, journal = {Journal of the European Mathematical Society}, publisher = {European Mathematical Society Press}, title = {{The exact rank of sparse random graphs}}, doi = {10.4171/jems/1692}, year = {2025}, } @article{18583, abstract = {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, Seymour, van der Zypen and Wood states that every directed graph has a 3-colouring such that for every vertex v, at most half of the out-neighbours of v have the same colour as . As another example, the internal partition conjecture, due to DeVos and to Ban and Linial, states that for every d, all but finitely many d-regular graphs have a partition into two non-empty parts such that for every vertex v, at least half of the neighbours of v lie in the same part as v. We prove several results in this spirit: in particular, two of our results are that the majority colouring conjecture holds for Erdős–Rényi random directed graphs (of any density), and that the internal partition conjecture holds if we permit a tiny number of ‘exceptional vertices’. Our proofs involve a variety of techniques, including several different methods to analyse random recolouring processes. One highlight is a personality-changing scheme: we ‘forget’ certain information based on the state of a Markov chain, giving us more independence to work with.}, author = {Anastos, Michael and Cooley, Oliver and Kang, Mihyun and Kwan, Matthew Alan}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {6}, publisher = {Wiley}, title = {{Partitioning problems via random processes}}, doi = {10.1112/jlms.70010}, volume = {110}, year = {2024}, } @article{17376, abstract = {The inertia bound and ratio bound (also known as the Cvetković bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number α(G) of a graph G in terms of spectral information about a weighted adjacency matrix of G. For both inequalities, given a graph G, one needs to make a judicious choice of weighted adjacency matrix to obtain as strong a bound as possible. While there is a well-established theory surrounding the ratio bound, the inertia bound is much more mysterious, and its limits are rather unclear. In fact, only recently did Sinkovic find the first example of a graph for which the inertia bound is not tight (for any weighted adjacency matrix), answering a longstanding question of Godsil. We show that the inertia bound can be extremely far from tight, and in fact can significantly underperform the ratio bound: for example, one of our results is that for infinitely many n, there is an n-vertex graph for which even the unweighted ratio bound can prove α(G)≤4n3/4, but the inertia bound is always at least n/4. In particular, these results address questions of Rooney, Sinkovic, and Wocjan--Elphick--Abiad.}, author = {Kwan, Matthew Alan and Wigderson, Yuval}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {10}, pages = {3196--3208}, publisher = {London Mathematical Society}, title = {{The inertia bound is far from tight}}, doi = {10.1112/blms.13127}, volume = {56}, year = {2024}, } @article{17475, abstract = {As a discrete analogue of Kac’s celebrated question on ‘hearing the shape of a drum’ and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency matrix). A striking conjecture in this area, due to van Dam and Haemers, is that ‘almost all graphs are determined by their spectrum’, meaning that the fraction of unlabelled n-vertex graphs which are determined by their spectrum converges to 1 as n → ∞. In this paper, we make a step towards this conjecture, showing that there are exponentially many n-vertex graphs which are determined by their spectrum. This improves on previous bounds (of shape e c √ n ). We also propose a number of further directions of research. }, author = {Koval, Illya and Kwan, Matthew Alan}, issn = {1464-3847}, journal = {Quarterly Journal of Mathematics}, number = {3}, pages = {869--899}, publisher = {Oxford University Press}, title = {{Exponentially many graphs are determined by their spectrum}}, doi = {10.1093/qmath/haae030}, volume = {75}, year = {2024}, } @article{14499, abstract = {An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clog2n (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a C-Ramsey graph. This brings together two ongoing lines of research: the study of ‘random-like’ properties of Ramsey graphs and the study of small-ball probability for low-degree polynomials of independent random variables. The proof proceeds via an ‘additive structure’ dichotomy on the degree sequence and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics and low-rank approximation. In particular, a key ingredient is a new sharpened version of the quadratic Carbery–Wright theorem on small-ball probability for polynomials of Gaussians, which we believe is of independent interest. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős reiterated in several of his open problem collections and for which he offered one of his notorious monetary prizes.}, author = {Kwan, Matthew Alan and Sah, Ashwin and Sauermann, Lisa and Sawhney, Mehtaab}, issn = {2050-5086}, journal = {Forum of Mathematics, Pi}, keywords = {Discrete Mathematics and Combinatorics, Geometry and Topology, Mathematical Physics, Statistics and Probability, Algebra and Number Theory, Analysis}, publisher = {Cambridge University Press}, title = {{Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture}}, doi = {10.1017/fmp.2023.17}, volume = {11}, year = {2023}, }