TY - JOUR
AB - 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.
AU - Kwan, Matthew Alan
AU - Sah, Ashwin
AU - Sawhney, Mehtaab
ID - 11186
JF - Bulletin of the London Mathematical Society
SN - 0024-6093
TI - Large deviations in random latin squares
ER -
TY - JOUR
AB - 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.
AU - Kwan, Matthew Alan
AU - Sauermann, Lisa
AU - Zhao, Yufei
ID - 11443
IS - 6
JF - Transactions of the American Mathematical Society
SN - 0002-9947
TI - Extension complexity of low-dimensional polytopes
VL - 375
ER -
TY - JOUR
AB - We say that (Formula presented.) if, in every edge coloring (Formula presented.), we can find either a 1-colored copy of (Formula presented.) or a 2-colored copy of (Formula presented.). The well-known states that the threshold for the property (Formula presented.) is equal to (Formula presented.), where (Formula presented.) is given by (Formula presented.) for any pair of graphs (Formula presented.) and (Formula presented.) with (Formula presented.). In this article, we show the 0-statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques.
AU - Liebenau, Anita
AU - Mattos, Letícia
AU - Mendonca Dos Santos, Walner
AU - Skokan, Jozef
ID - 11706
JF - Random Structures and Algorithms
SN - 1042-9832
TI - Asymmetric Ramsey properties of random graphs involving cliques and cycles
ER -
TY - CONF
AB - 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.
AU - Ferber, Asaf
AU - Kwan, Matthew Alan
AU - Sauermann, Lisa
ID - 11145
SN - 0272-5428
T2 - 62nd Annual IEEE Symposium on Foundations of Computer Science
TI - List-decodability with large radius for Reed-Solomon codes
VL - 2022
ER -
TY - JOUR
AB - 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.
AU - Ferber, Asaf
AU - Kwan, Matthew Alan
AU - Sauermann, Lisa
ID - 10775
IS - 6
JF - IEEE Transactions on Information Theory
SN - 0018-9448
TI - List-decodability with large radius for Reed-Solomon codes
VL - 68
ER -
TY - JOUR
AB - We consider a generalised model of a random simplicial complex, which arises from a random hypergraph. Our model is generated by taking the downward-closure of a non-uniform binomial random hypergraph, in which for each k, each set of k+1 vertices forms an edge with some probability pk independently. As a special case, this contains an extensively studied model of a (uniform) random simplicial complex, introduced by Meshulam and Wallach [Random Structures & Algorithms 34 (2009), no. 3, pp. 408–417].
We consider a higher-dimensional notion of connectedness on this new model according to the vanishing of cohomology groups over an arbitrary abelian group R. We prove that this notion of connectedness displays a phase transition and determine the threshold. We also prove a hitting time result for a natural process interpretation, in which simplices and their downward-closure are added one by one. In addition, we determine the asymptotic behaviour of cohomology groups inside the critical window around the time of the phase transition.
AU - Cooley, Oliver
AU - Del Giudice, Nicola
AU - Kang, Mihyun
AU - Sprüssel, Philipp
ID - 11740
IS - 3
JF - Electronic Journal of Combinatorics
TI - Phase transition in cohomology groups of non-uniform random simplicial complexes
VL - 29
ER -