@article{14444, abstract = {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, resolving a conjecture of Linial that there exist Latin squares with arbitrarily high girth. As a consequence, we see that the number of order- n Latin squares with no intercalate (i.e., no 2×2 Latin subsquare) is at least (e−9/4n−o(n))n2. Equivalently, P[N=0]≥e−n2/4−o(n2)=e−(1+o(1))EN , where N is the number of intercalates in a uniformly random order- n Latin square. In fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant 0<δ≤1 we have P[N≤(1−δ)EN]=exp(−Θ(n2)) and for any constant δ>0 we have P[N≥(1+δ)EN]=exp(−Θ(n4/3logn)). Finally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order- n Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate 2×2 submatrices with the same arrangement of symbols) is of order n4, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative'' the quasigroup associated with the Latin square is.}, author = {Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab and Simkin, Michael}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {2}, pages = {363--416}, publisher = {Springer Nature}, title = {{Substructures in Latin squares}}, doi = {10.1007/s11856-023-2513-9}, volume = {256}, year = {2023}, } @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}, } @article{10775, abstract = {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 focus on the case where the list-decoding radius is of the form r = 1-ε for ε tending to zero. Our main result states that there exist Reed–Solomon codes with rate Ω(ε) which are (1 - ε, O(1/ε))-list-decodable, meaning that any Hamming ball of radius 1-ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.}, author = {Ferber, Asaf and Kwan, Matthew Alan and Sauermann, Lisa}, issn = {1557-9654}, journal = {IEEE Transactions on Information Theory}, number = {6}, pages = {3823--3828}, publisher = {IEEE}, title = {{List-decodability with large radius for Reed-Solomon codes}}, doi = {10.1109/TIT.2022.3148779}, volume = {68}, year = {2022}, } @inproceedings{11145, abstract = {List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.}, author = {Ferber, Asaf and Kwan, Matthew Alan and Sauermann, Lisa}, booktitle = {62nd Annual IEEE Symposium on Foundations of Computer Science}, isbn = {9781665420556}, issn = {0272-5428}, location = {Denver, CO, United States}, pages = {720--726}, publisher = {IEEE}, title = {{List-decodability with large radius for Reed-Solomon codes}}, doi = {10.1109/FOCS52979.2021.00075}, volume = {2022}, year = {2022}, } @article{11186, abstract = {In this note, we study large deviations of the number 𝐍 of intercalates ( 2×2 combinatorial subsquares which are themselves Latin squares) in a random 𝑛×𝑛 Latin square. In particular, for constant 𝛿>0 we prove that exp(−𝑂(𝑛2log𝑛))⩽Pr(𝐍⩽(1−𝛿)𝑛2/4)⩽exp(−Ω(𝑛2)) and exp(−𝑂(𝑛4/3(log𝑛)))⩽Pr(𝐍⩾(1+𝛿)𝑛2/4)⩽exp(−Ω(𝑛4/3(log𝑛)2/3)) . As a consequence, we deduce that a typical order- 𝑛 Latin square has (1+𝑜(1))𝑛2/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.}, author = {Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {4}, pages = {1420--1438}, publisher = {Wiley}, title = {{Large deviations in random latin squares}}, doi = {10.1112/blms.12638}, volume = {54}, year = {2022}, } @article{11443, abstract = {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 defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes. First, we prove that for a fixed dimension d, the extension complexity of a random d-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie on a circle) has extension complexity at most 24√n. This bound is tight up to the constant factor 24. Finally, we show that there exists an no(1)-dimensional polytope with at most n vertices and extension complexity n1−o(1). Our theorems are proved with a range of different techniques, which we hope will be of further interest.}, author = {Kwan, Matthew Alan and Sauermann, Lisa and Zhao, Yufei}, issn = {1088-6850}, journal = {Transactions of the American Mathematical Society}, number = {6}, pages = {4209--4250}, publisher = {American Mathematical Society}, title = {{Extension complexity of low-dimensional polytopes}}, doi = {10.1090/tran/8614}, volume = {375}, year = {2022}, } @article{9572, abstract = {We prove that every n-vertex tournament G has an acyclic subgraph with chromatic number at least n5/9−o(1), while there exists an n-vertex tournament G whose every acyclic subgraph has chromatic number at most n3/4+o(1). This establishes in a strong form a conjecture of Nassar and Yuster and improves on another result of theirs. Our proof combines probabilistic and spectral techniques together with some additional ideas. In particular, we prove a lemma showing that every tournament with many transitive subtournaments has a large subtournament that is almost transitive. This may be of independent interest.}, author = {Fox, Jacob and Kwan, Matthew Alan and Sudakov, Benny}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {2}, pages = {619--630}, publisher = {Wiley}, title = {{Acyclic subgraphs of tournaments with high chromatic number}}, doi = {10.1112/blms.12446}, volume = {53}, year = {2021}, } @article{9573, abstract = {It is a classical fact that for any ε>0, a random permutation of length n=(1+ε)k2/4 typically contains a monotone subsequence of length k. As a far-reaching generalization, Alon conjectured that a random permutation of this same length n is typically k-universal, meaning that it simultaneously contains every pattern of length k. He also made the simple observation that for n=O(k2logk), a random length-n permutation is typically k-universal. We make the first significant progress towards Alon's conjecture by showing that n=2000k2loglogk suffices.}, author = {He, Xiaoyu and Kwan, Matthew Alan}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {3}, pages = {515--529}, publisher = {Wiley}, title = {{Universality of random permutations}}, doi = {10.1112/blms.12345}, volume = {52}, year = {2020}, } @article{9576, abstract = {In 1989, Rota made the following conjecture. Given n bases B1,…,Bn in an n-dimensional vector space V⁠, one can always find n disjoint bases of V⁠, each containing exactly one element from each Bi (we call such bases transversal bases). Rota’s basis conjecture remains wide open despite its apparent simplicity and the efforts of many researchers (e.g., the conjecture was recently the subject of the collaborative “Polymath” project). In this paper we prove that one can always find (1/2−o(1))n disjoint transversal bases, improving on the previous best bound of Ω(n/logn)⁠. Our results also apply to the more general setting of matroids.}, author = {Bucić, Matija and Kwan, Matthew Alan and Pokrovskiy, Alexey and Sudakov, Benny}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {21}, pages = {8007--8026}, publisher = {Oxford University Press}, title = {{Halfway to Rota’s basis conjecture}}, doi = {10.1093/imrn/rnaa004}, volume = {2020}, year = {2020}, } @article{9577, abstract = {An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clogn⁠. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. Motivated by an old problem of Erd̋s and McKay, recently Narayanan, Sahasrabudhe, and Tomon conjectured that for any fixed C, every n-vertex C-Ramsey graph induces subgraphs of Θ(n2) different sizes. In this paper we prove this conjecture.}, author = {Kwan, Matthew Alan and Sudakov, Benny}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {6}, pages = {1621–1638}, publisher = {Oxford University Press}, title = {{Ramsey graphs induce subgraphs of quadratically many sizes}}, doi = {10.1093/imrn/rny064}, volume = {2020}, year = {2020}, } @article{9578, abstract = {How long a monotone path can one always find in any edge-ordering of the complete graph Kn? This appealing question was first asked by Chvátal and Komlós in 1971, and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was n2/3-o(1). In this paper we almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length n1-o(1).}, author = {Bucić, Matija and Kwan, Matthew Alan and Pokrovskiy, Alexey and Sudakov, Benny and Tran, Tuan and Wagner, Adam Zsolt}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {2}, pages = {663--685}, publisher = {Springer}, title = {{Nearly-linear monotone paths in edge-ordered graphs}}, doi = {10.1007/s11856-020-2035-7}, volume = {238}, year = {2020}, } @article{9581, abstract = {We show that for any 𝑛 divisible by 3, almost all order- 𝑛 Steiner triple systems have a perfect matching (also known as a parallel class or resolution class). In fact, we prove a general upper bound on the number of perfect matchings in a Steiner triple system and show that almost all Steiner triple systems essentially attain this maximum. We accomplish this via a general theorem comparing a uniformly random Steiner triple system to the outcome of the triangle removal process, which we hope will be useful for other problems. Our methods can also be adapted to other types of designs; for example, we sketch a proof of the theorem that almost all Latin squares have transversals.}, author = {Kwan, Matthew Alan}, issn = {1460-244X}, journal = {Proceedings of the London Mathematical Society}, number = {6}, pages = {1468--1495}, publisher = {Wiley}, title = {{Almost all Steiner triple systems have perfect matchings}}, doi = {10.1112/plms.12373}, volume = {121}, year = {2020}, } @article{9582, abstract = {The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least cH log d/log log d, thus nearly confirming one and proving another conjecture of Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak and Spencer.}, author = {Kwan, Matthew Alan and Letzter, Shoham and Sudakov, Benny and Tran, Tuan}, issn = {1439-6912}, journal = {Combinatorica}, number = {2}, pages = {283--305}, publisher = {Springer}, title = {{Dense induced bipartite subgraphs in triangle-free graphs}}, doi = {10.1007/s00493-019-4086-0}, volume = {40}, year = {2020}, } @article{9583, abstract = {We show that for any n divisible by 3, almost all order-n Steiner triple systems admit a decomposition of almost all their triples into disjoint perfect matchings (that is, almost all Steiner triple systems are almost resolvable).}, author = {Ferber, Asaf and Kwan, Matthew Alan}, issn = {2050-5094}, journal = {Forum of Mathematics}, publisher = {Cambridge University Press}, title = {{Almost all Steiner triple systems are almost resolvable}}, doi = {10.1017/fms.2020.29}, volume = {8}, year = {2020}, } @article{9580, abstract = {An r-cut of a k-uniform hypergraph H is a partition of the vertex set of H into r parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω)(m−−√) and this is best possible. That is, there exist cuts which exceed the expected size of a random cut by some multiple of the standard deviation. We study analogues of this and related results in hypergraphs. First, we observe that similarly to graphs, every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m−−√) larger than the expected size of a random r-cut. Moreover, in the case where k = 3 and r = 2 this bound is best possible and is attained by Steiner triple systems. Surprisingly, for all other cases (that is, if k ≥ 4 or r ≥ 3), we show that every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m5/9) larger than the expected size of a random r-cut. This is a significant difference in behaviour, since the amount by which the size of the largest cut exceeds the expected size of a random cut is now considerably larger than the standard deviation.}, author = {Conlon, David and Fox, Jacob and Kwan, Matthew Alan and Sudakov, Benny}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {1}, pages = {67--111}, publisher = {Springer}, title = {{Hypergraph cuts above the average}}, doi = {10.1007/s11856-019-1897-z}, volume = {233}, year = {2019}, } @article{9585, abstract = {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 an ongoing line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. More than 25 years ago, Erdős, Faudree and Sós conjectured that in any C-Ramsey graph there are Ω(n^5/2) induced subgraphs, no pair of which have the same numbers of vertices and edges. Improving on earlier results of Alon, Balogh, Kostochka and Samotij, in this paper we prove this conjecture.}, author = {Kwan, Matthew Alan and Sudakov, Benny}, issn = {1088-6850}, journal = {Transactions of the American Mathematical Society}, number = {8}, pages = {5571--5594}, publisher = {American Mathematical Society}, title = {{Proof of a conjecture on induced subgraphs of Ramsey graphs}}, doi = {10.1090/tran/7729}, volume = {372}, year = {2019}, } @article{9586, abstract = {Consider integers 𝑘,ℓ such that 0⩽ℓ⩽(𝑘2) . Given a large graph 𝐺 , what is the fraction of 𝑘 -vertex subsets of 𝐺 which span exactly ℓ edges? When 𝐺 is empty or complete, and ℓ is zero or (𝑘2) , this fraction can be exactly 1. On the other hand, if ℓ is far from these extreme values, one might expect that this fraction is substantially smaller than 1. This was recently proved by Alon, Hefetz, Krivelevich, and Tyomkyn who initiated the systematic study of this question and proposed several natural conjectures. Let ℓ∗=min{ℓ,(𝑘2)−ℓ} . Our main result is that for any 𝑘 and ℓ , the fraction of 𝑘 -vertex subsets that span ℓ edges is at most log𝑂(1)(ℓ∗/𝑘)√ 𝑘/ℓ∗, which is best-possible up to the logarithmic factor. This improves on multiple results of Alon, Hefetz, Krivelevich, and Tyomkyn, and resolves one of their conjectures. In addition, we also make some first steps towards some analogous questions for hypergraphs. Our proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anticoncentration inequalities, hypercontractivity, and a coupling trick for random variables defined on a ‘slice’ of the Boolean hypercube.}, author = {Kwan, Matthew Alan and Sudakov, Benny and Tran, Tuan}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {3}, pages = {757--777}, publisher = {Wiley}, title = {{Anticoncentration for subgraph statistics}}, doi = {10.1112/jlms.12192}, volume = {99}, year = {2019}, } @article{9565, abstract = {Let D(n,p) be the random directed graph on n vertices where each of the n(n-1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if p≥(logn+ω(1))/n then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically n!(p(1+o(1)))n. We also prove a hitting-time version of this statement, showing that in the random directed graph process, as soon as every vertex has in-/out-degrees at least 1, there are typically n!(logn/n(1+o(1)))n directed Hamilton cycles.}, author = {Ferber, Asaf and Kwan, Matthew Alan and Sudakov, Benny}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {4}, pages = {592--603}, publisher = {Wiley}, title = {{Counting Hamilton cycles in sparse random directed graphs}}, doi = {10.1002/rsa.20815}, volume = {53}, year = {2018}, } @article{9567, abstract = {Let P be a graph property which is preserved by removal of edges, and consider the random graph process that starts with the empty n-vertex graph and then adds edges one-by-one, each chosen uniformly at random subject to the constraint that P is not violated. These types of random processes have been the subject of extensive research over the last 20 years, having striking applications in extremal combinatorics, and leading to the discovery of important probabilistic tools. In this paper we consider the k-matching-free process, where P is the property of not containing a matching of size k. We are able to analyse the behaviour of this process for a wide range of values of k; in particular we prove that if k=o(n) or if n−2k=o(n−−√/logn) then this process is likely to terminate in a k-matching-free graph with the maximum possible number of edges, as characterised by Erdős and Gallai. We also show that these bounds on k are essentially best possible, and we make a first step towards understanding the behaviour of the process in the intermediate regime.}, author = {Krivelevich, Michael and Kwan, Matthew Alan and Loh, Po‐Shen and Sudakov, Benny}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {4}, pages = {692--716}, publisher = {Wiley}, title = {{The random k‐matching‐free process}}, doi = {10.1002/rsa.20814}, volume = {53}, year = {2018}, } @article{9568, abstract = {An intercalate in a Latin square is a 2×2 Latin subsquare. Let N be the number of intercalates in a uniformly random n×n Latin square. We prove that asymptotically almost surely N≥(1−o(1))n2/4, and that EN≤(1+o(1))n2/2 (therefore asymptotically almost surely N≤fn2 for any f→∞). This significantly improves the previous best lower and upper bounds. We also give an upper tail bound for the number of intercalates in two fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low-discrepancy Latin squares.}, author = {Kwan, Matthew Alan and Sudakov, Benny}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {2}, pages = {181--196}, publisher = {Wiley}, title = {{Intercalates and discrepancy in random Latin squares}}, doi = {10.1002/rsa.20742}, volume = {52}, year = {2018}, }