@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},
publisher = {Wiley},
title = {{Large deviations in random latin squares}},
doi = {10.1112/blms.12638},
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{11706,
abstract = {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. },
author = {Liebenau, Anita and Mattos, Letícia and Mendonca Dos Santos, Walner and Skokan, Jozef},
issn = {1098-2418},
journal = {Random Structures and Algorithms},
publisher = {Wiley},
title = {{Asymmetric Ramsey properties of random graphs involving cliques and cycles}},
doi = {10.1002/rsa.21106},
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{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},
}
@article{11740,
abstract = {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.},
author = {Cooley, Oliver and Del Giudice, Nicola and Kang, Mihyun and Sprüssel, Philipp},
issn = {1077-8926},
journal = {Electronic Journal of Combinatorics},
number = {3},
publisher = {Electronic Journal of Combinatorics},
title = {{Phase transition in cohomology groups of non-uniform random simplicial complexes}},
doi = {10.37236/10607},
volume = {29},
year = {2022},
}