@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}, number = {4}, pages = {1035--1055}, publisher = {Wiley}, title = {{Asymmetric Ramsey properties of random graphs involving cliques and cycles}}, doi = {10.1002/rsa.21106}, volume = {62}, year = {2023}, } @article{14319, abstract = {We study multigraphs whose edge-sets are the union of three perfect matchings, M1, M2, and M3. Given such a graph G and any a1; a2; a3 2 N with a1 +a2 +a3 6 n - 2, we show there exists a matching M of G with jM \ Mij = ai for each i 2 f1; 2; 3g. The bound n - 2 in the theorem is best possible in general. We conjecture however that if G is bipartite, the same result holds with n - 2 replaced by n - 1. We give a construction that shows such a result would be tight. We also make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour multiplicities.}, author = {Anastos, Michael and Fabian, David and Müyesser, Alp and Szabó, Tibor}, issn = {1077-8926}, journal = {Electronic Journal of Combinatorics}, number = {3}, publisher = {Electronic Journal of Combinatorics}, title = {{Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets}}, doi = {10.37236/11714}, volume = {30}, year = {2023}, } @inproceedings{14344, abstract = {We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and respectively, each being best possible in its own setting.}, author = {Anastos, Michael}, booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {9781611977554}, location = {Florence, Italy}, pages = {2286--2323}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Fast algorithms for solving the Hamilton cycle problem with high probability}}, doi = {10.1137/1.9781611977554.ch88}, volume = {2023}, year = {2023}, } @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}, } @inproceedings{14867, abstract = {Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$ edges is presented chosen uniformly at random from the ones that have not been presented yet. We are then asked to choose at most one of the presented edges and add it to the current graph. Our goal is to construct a Hamiltonian graph with $(1+o(1))n$ edges within as few rounds as possible. We show that in this process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\log n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along the first $(0.5+o(1))n\log n$ rounds of the random graph process. This answers a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds is asymptotically optimal as the first $0.5n\log n$ edges do not span a Hamilton cycle w.h.p. The case $K=\Theta(\log n)$ implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most $(1+o(1))(1+(\log n)/2K) n$. This matches the $(1-o(1))(1+(\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky and Sudakov and resolves the problem of determining the Hamiltonicity threshold of the Achlioptas process with $K=\Theta(\log n)$. We also show that in the above process one can construct a graph $G$ that spans a matching of size $\lfloor V(G)/2) \rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\log n)/2K) n$ rounds w.h.p. Our proof relies on a robust Hamiltonicity property of the strong $4$-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong $4$-core into a cycle.}, author = {Anastos, Michael}, booktitle = {Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications}, issn = {2788-3116}, location = {Prague, Czech Republic}, pages = {36--41}, publisher = {Masaryk University Press}, title = {{Constructing Hamilton cycles and perfect matchings efficiently}}, doi = {10.5817/cz.muni.eurocomb23-005}, year = {2023}, } @article{13042, abstract = {Let Lc,n denote the size of the longest cycle in G(n, c/n),c >1 constant. We show that there exists a continuous function f(c) such that Lc,n/n→f(c) a.s. for c>20, thus extending a result of Frieze and the author to smaller values of c. Thereafter, for c>20, we determine the limit of the probability that G(n, c/n)contains cycles of every length between the length of its shortest and its longest cycles as n→∞.}, author = {Anastos, Michael}, issn = {1077-8926}, journal = {Electronic Journal of Combinatorics}, number = {2}, publisher = {Electronic Journal of Combinatorics}, title = {{A note on long cycles in sparse random graphs}}, doi = {10.37236/11471}, volume = {30}, 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{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}, } @article{12151, abstract = {The k-sample G(k,W) from a graphon W:[0,1]2→[0,1] is the random graph on {1,…,k}, where we sample x1,…,xk∈[0,1] uniformly at random and make each pair {i,j}⊆{1,…,k} an edge with probability W(xi,xj), with all these choices being mutually independent. Let the random variable Xk(W) be the number of edges in G(k,W). Vera T. Sós asked in 2012 whether two graphons U, W are necessarily weakly isomorphic if the random variables Xk(U) and Xk(W) have the same distribution for every integer k≥2. This question when one of the graphons W is a constant function was answered positively by Endre Csóka and independently by Jacob Fox, Tomasz Łuczak and Vera T. Sós. Here we investigate the question when W is a 2-step graphon and prove that the answer is positive for a 3-dimensional family of such graphons. We also present some related results.}, author = {Cooley, Oliver and Kang, M. and Pikhurko, O.}, issn = {1588-2632}, journal = {Acta Mathematica Hungarica}, keywords = {graphon, k-sample, graphon forcing, graph container}, pages = {1--26}, publisher = {Springer Nature}, title = {{On a question of Vera T. Sós about size forcing of graphons}}, doi = {10.1007/s10474-022-01265-8}, volume = {168}, year = {2022}, } @article{12286, abstract = {Inspired by the study of loose cycles in hypergraphs, we define the loose core in hypergraphs as a structurewhich mirrors the close relationship between cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes. Our main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$.}, author = {Cooley, Oliver and Kang, Mihyun and Zalla, Julian}, issn = {1077-8926}, journal = {The Electronic Journal of Combinatorics}, keywords = {Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science, Applied Mathematics, Discrete Mathematics and Combinatorics}, number = {4}, publisher = {The Electronic Journal of Combinatorics}, title = {{Loose cores and cycles in random hypergraphs}}, doi = {10.37236/10794}, volume = {29}, year = {2022}, } @inproceedings{12432, abstract = {We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥ 100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and Krivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n −1/2 respectively.}, author = {Anastos, Michael}, booktitle = {63rd Annual IEEE Symposium on Foundations of Computer Science}, isbn = {9781665455190}, issn = {0272-5428}, location = {Denver, CO, United States}, pages = {919--930}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Solving the Hamilton cycle problem fast on average}}, doi = {10.1109/FOCS54457.2022.00091}, volume = {2022-October}, year = {2022}, }