Search

The cycle set of a graph $G$ is the set consisting of all sizes of cycles in $G$. Answering a conjecture of Erd\H{o}s and Faudree, Verstra\"{e}te showed that there are at most $2^{n - n^{1/10}}$ different cycle sets of graphs with $n$ vertices. We improve this bound to $2^{n - n^{1/2 - o(1)}}$. Our proof follows the general strategy of Verstra\"{e}te of reducing the problem to counting cycle sets of Hamiltonian graphs with many chords or a large maximum degree. The key new ingredients are near-optimal container lemmata for cycle sets of such graphs., Comment: 10 pages

Given a family of hypergraphs $\mathcal{H}$, we say that a hypergraph $\Gamma$ is $\mathcal{H}$-universal if it contains every $H \in \mathcal{H}$ as a subgraph. For $D, r \in \mathbb{N}$, we construct an $r$-uniform hypergraph with $\Theta\left(n^{r - r/D} \log^{r/D}(n)\right)$ edges which is universal for the family of all $r$-uniform hypergraphs with $n$ vertices and maximum degree at most $D$. This almost matches a trivial lower bound $\Omega(n^{r - r/D})$ coming from the number of such hypergraphs. On a high level, we follow the strategy of Alon and Capalbo used in the graph case, that is $r = 2$. The construction of $\Gamma$ is deterministic and based on a bespoke product of expanders, whereas showing that $\Gamma$ is universal is probabilistic. Two key new ingredients are a decomposition result for hypergraphs of bounded density, based on Edmond's matroid partitioning theorem, and a tail bound for branching random walks on expanders., Comment: 15 pages

We develop a variant of the hypergraph container lemma with non-uniform conditions on the co-degrees. In particular, an upper bound on the co-degree of some subset of vertices $T$ is allowed to depend on where the vertices in $T$ live in the hypergraph, rather than having one condition which holds for all subsets. We use this to extend recent results on nearly-orthogonal sets in $\mathbb{F}_p^d$. For a field $\mathbb{F}$ and integers $d, k$ and $\ell$, a set $A \subseteq \mathbb{F}^d$ is called $(k,\ell)$-nearly orthogonal if all vectors in $A$ are non-self-orthogonal and every $k+1$ vectors in $A$ contain $\ell + 1$ pairwise orthogonal vectors. Recently, Haviv, Mattheus, Milojevi\'{c} and Wigderson have improved the lower bound on nearly orthogonal sets over finite fields, using counting arguments and a hypergraph container lemma. They showed that for every prime $p$ and an integer $\ell$, there is a constant $\delta(p,\ell)$ such that for every field $\mathbb{F}$ of characteristic $p$ and for all integers $d \geq k \geq \ell + 1$, $\mathbb{F}^d$ contains a $(k,\ell)$-nearly orthogonal set of size $d^{\delta k / \log k}$. This nearly matches an upper bound $\binom{d+k}{k}$ coming from Ramsey theory. Moreover, they proved the same lower bound for the size of a largest set $A$ where for any two subsets of $A$ of size $k+1$ each, there is a vector in one of the subsets orthogonal to a vector in the other one. We prove that essentially the same lower bound holds for the size of a largest set $A \subseteq \mathbb{F}^d$ with the stronger property that given any family of subsets $A_1, \ldots, A_{\ell+1} \subset A$, each of size $k+1$, we can find a vector in each $A_i$ such that they are all pairwise orthogonal., Comment: 8 pages

A subset of $\mathbb{F}_q^2$ is called an arc if it does not contain three collinear points. We show that there are at most $\binom{(1 + o(1))q}{m}$ arcs of size $m \gg q^{1/2} (\log q)^{3/2}$, nearly matching a trivial lower bound $\binom{q}{m}$. This was previously known to hold for $m \gg q^{2/3} (\log q)^3$, due to Bhowmick and Roche-Newton. The lower bound on $m$ is best possible up to a logarithmic factor., Comment: 3 pages

An $n$-vertex graph $G$ is locally dense if every induced subgraph of size larger than $\zeta n$ has density at least $d > 0$, for some parameters $\zeta, d > 0$. We show that the number of induced subgraphs of $G$ with $m$ vertices and maximum degree significantly smaller than $dm$ is roughly $\binom{\zeta n}{m}$, for $m \ll \zeta n$ which is not too small. This generalises a result of Kohayakawa, Lee, R\"odl, and Samotij on the number of independent sets in locally dense graphs. As an application, we slightly improve a result of Balogh, Chen, and Luo on the generalised Erd\H{o}s-Rogers function for graphs with small extremal number., Comment: 4 pages; fixed minor issue in Lemma 2.1

Combining ideas of Pham, Sah, Sawhney, and Simkin on spread perfect matchings in super-regular bipartite graphs with an algorithmic blow-up lemma, we prove a spread version of the blow-up lemma. Intuitively, this means that there exists a probability measure over copies of a desired spanning graph $H$ in a given system of super-regular pairs which does not heavily pin down any subset of vertices. This allows one to complement the use of the blow-up lemma with the recently resolved Kahn-Kalai conjecture. As an application, we prove an approximate version of a conjecture of B\"ottcher, Parczyk, Sgueglia, and Skokan on the threshold for appearance of powers of Hamilton cycles in perturbed random graphs., Comment: 12 pages

We present a short and simple proof of the celebrated hypergraph container theorem of Balogh--Morris--Samotij and Saxton--Thomason. On a high level, our argument utilises the idea of iteratively taking vertices of largest degree from an independent set and constructing a hypergraph of lower uniformity which preserves independent sets and inherits edge distribution. The original algorithms for constructing containers also remove in each step vertices of high degree which are not in the independent set. Our modified algorithm postpones this until the end, which surprisingly results in a significantly simplified analysis., Comment: 4 pages

We initiate the systematic study of the following Tur\'an-type question. Suppose $\Gamma$ is a graph with $n$ vertices such that the edge density between any pair of subsets of vertices of size at least $t$ is at most $1 - c$, for some $t$ and $c > 0$. What is the largest number of edges in a subgraph $G \subseteq \Gamma$ which does not contain a fixed graph $H$ as an induced subgraph or, more generally, which belongs to a hereditary property $\mathcal{P}$? This provides a common generalization of two recently studied cases, namely $\Gamma$ being a (pseudo-)random graph and a graph without a large complete bipartite subgraph. We focus on the interesting case where $H$ is a bipartite graph. We determine the answer up to a constant factor with respect to $n$ and $t$, for certain bipartite $H$ and for $\Gamma$ either a dense random graph or a Paley graph with a square number of vertices. In particular, our bounds match if $H$ is a tree, or if one part of $H$ has $d$ vertices complete to the other part, all other vertices in that part have degree at most $d$, and the other part has sufficiently many vertices. As applications of the latter result, we answer a question of Alon, Krivelevich, and Samotij on the largest subgraph with a hereditary property which misses a bipartite graph, and determine up to a constant factor the largest number of edges in a string subgraph of $\Gamma$. The proofs are based on a variant of the dependent random choice and a novel approach for finding induced copies by inductively defining probability distributions supported on induced copies of smaller subgraphs., Comment: 20 pages

We show that if $n$ is odd and $p \ge C \log n / n$, then with high probability Hamilton cycles in $G(n,p)$ span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph $G$, that is, a graph $G$ with odd $n$ vertices and minimum degree $n/2 + C$ for sufficiently large constant $C$, span its cycle space.

Consider the Erd\H{o}s-R\'enyi random graph process $\{G_m\}_{m \ge 0}$ in which we start with an empty graph $G_0$ on the vertex set $[n]$, and in each step form $G_i$ from $G_{i-1}$ by adding one new edge chosen uniformly at random. Resolving a conjecture by Benjamini and Tzalik, we give a simple proof that w.h.p. as soon as $G_m$ has minimum degree $2$ it is globally rigid in the following sense: For any function $d \colon E(G_m) \rightarrow \mathbb{R}$, there exists at most one injective function $f \colon [n] \rightarrow \mathbb{R}$ (up to isometry) such that $d(ij) = |f(i) - f(j)|$ for every $ij \in E(G_m)$. We also resolve a related question of Gir\~{a}o, Illingworth, Michel, Powierski, and Scott in the sparse regime for the random graph and give some open problems., Comment: 5 pages

A graph $G$ is $\textit{universal}$ for a (finite) family $\mathcal{H}$ of graphs if every $H \in \mathcal{H}$ is a subgraph of $G$. For a given family $\mathcal{H}$, the goal is to determine the smallest number of edges an $\mathcal{H}$-universal graph can have. With the aim of unifying a number of recent results, we consider a family of graphs with bounded density. In particular, we construct a graph with $O_d\left( n^{2 - 1/(\lceil d \rceil + 1)} \right)$ edges which contains every $n$-vertex graph with density at most $d \in \mathbb{Q}$ ($d \ge 1$), which is close to a lower bound $\Omega(n^{2 - 1/d - o(1)})$ obtained by counting lifts of a carefully chosen (small) graph. When restricting the maximum degree of such graphs to be constant, we obtain a near-optimal universality. If we further assume $d \in \mathbb{N}$, we get an asymptotically optimal construction., Comment: 14 pages, updated version focusing on density, with new title and additional author

We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong $d$-regular expander graph $G$ with $n$ vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths $\mathcal P$ in $G$ and fulfills any series of two types of requests: 1. Given two vertices $a$ and $b$ such that each appears as an endpoint in $O(d)$ paths in $\mathcal P$ and, additionally, $|\mathcal P| = O(n d / \log n)$, the algorithm finds a path of length at most $\log n$ connecting $a$ and $b$ which is edge-disjoint from all other paths in $\mathcal P$, and adds it to $\mathcal P$. 2. Remove a given path $P \in \mathcal{P}$ from $\mathcal{P}$. Importantly, each request is processed before seeing the next one. The upper bound on the length of found paths and the constraints are the best possible up to a constant factor. This establishes the first online algorithm for finding edge-disjoint paths in expanders which also allows removals, significantly strengthening a long list of previous results on the topic., Comment: 13 pages

In this short note we confirm the deep structural correspondence between the complexity of a countable scattered chain (= strict linear order) and its big Ramsey combinatorics: we show that a countable scattered chain has finite big Ramsey degrees if and only if it is of finite Hausdorff rank. This also provides a complete characterization of countable chains whose big Ramsey spectra are finite. We expand the notion of big Ramsey spectrum to monomorphic structures and give a sufficient condition for a monomorphic countable structure to have finite big Ramsey spectrum.

We consider the following matching-based routing problem. Initially, each vertex $v$ of a connected graph $G$ is occupied by a pebble which has a unique destination $\pi(v)$. In each round the pebbles across the edges of a selected matching in $G$ are swapped, and the goal is to route each pebble to its destination vertex in as few rounds as possible. We show that if $G$ is a sufficiently strong $d$-regular spectral expander then any permutation $\pi$ can be achieved in $O(\log n)$ rounds. This is optimal for constant $d$ and resolves a problem of Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (1994), pp. 516--530]., Comment: 5 pages. Comments are welcome!

Consider the following two-player game on the edges of $K_n$, the complete graph with $n$ vertices: Starting with an empty graph $G$ on the vertex set of $K_n$, in each round the first player chooses $b \in \mathbb{N}$ edges from $K_n$ which have not previously been chosen, and the second player immediately and irrevocably picks one of these edges and adds it to $G$. We show that for any graph $H$ with at least one edge, if $b < c n^{1/m(H)}$, where $c = c(H) > 0$ only depends on $H$ and $m(H)$ is the usual density function, then the first player can ensure the resulting graph $G$ contains $\Omega(n^{v(H)} / b^{e(H)})$ copies of $H$. The bound on $b$ is the best possible apart from the constant $c$ and shows that the density of the resulting graph for which it is possible to enforce the appearance of $H$ coincides with a threshold for the appearance in the Erd\H{o}s-R\'enyi random graph. This resolves a conjecture by Bednarska-Bzd\c{e}ga, Hefetz, and Luczak and provides a prominent class of games for which probabilistic intuition accurately predicts the outcome. The strategy of the first player is deterministic with polynomial running time, with the degree depending on the size of $H$., Comment: 7 pages

We show that the size-Ramsey number of the $\sqrt{n} \times \sqrt{n}$ grid graph is $O(n^{5/4})$, improving a previous bound of $n^{3/2 + o(1)}$ by Clemens, Miralaei, Reding, Schacht, and Taraz., Comment: 8 pages, 1 figure

Given a $k$-uniform hypergraph $\mathcal{H}$ and sufficiently large $m \gg m_0(\mathcal{H})$, we show that an $m$-element set $I \subseteq V(\mathcal{H})$, chosen uniformly at random, with probability $1 - e^{-\omega(m)}$ is either not independent or is contained in an almost-independent set in $\mathcal{H}$ which, crucially, can be constructed from carefully chosen $o(m)$ vertices of $I$. As a corollary, this implies that if the largest almost-independent set in $\mathcal{H}$ is of size $o(v(\mathcal{H}))$ then $I$ itself is an independent set with probability $e^{-\omega(m)}$. More generally, $I$ is very likely to inherit structural properties of almost-independent sets in $\mathcal{H}$. The value $m_0(\mathcal{H})$ coincides with that for which Janson's inequality gives that $I$ is independent with probability at most $e^{-\Theta(m_0)}$. On the one hand, our result is a significant strengthening of Janson's inequality in the range $m \gg m_0$. On the other hand, it can be seen as a probabilistic variant of hypergraph container theorems, developed by Balogh, Morris and Samotij and, independently, by Saxton and Thomason. While being strictly weaker than the original container theorems in the sense that it does not apply to all independent sets of size $m$, it is nonetheless sufficient for many applications and admits a short proof using probabilistic ideas., Comment: 13 pages

We show that the size-Ramsey number of any cubic graph with $n$ vertices is $O(n^{8/5})$, improving a bound of $n^{5/3 + o(1)}$ due to Kohayakawa, R\"{o}dl, Schacht, and Szemer\'{e}di. The heart of the argument is to show that there is a constant $C$ such that a random graph with $C n$ vertices where every edge is chosen independently with probability $p \geq C n^{-2/5}$ is with high probability Ramsey for any cubic graph with $n$ vertices. This latter result is best possible up to the constant., Comment: 15 pages

Szemer\'edi's theorem implies that there are $2^{o(n)}$ subsets of $[n]$ which do not contain a $k$-term arithmetic progression. A sparse analogue of this statement was obtained by Balogh, Morris, and Samotij, using the hypergraph container method: For any $\beta > 0$ there exists $C > 0$, such that if $m \ge Cn^{1 - 1/(k-1)}$ then there are at most $\beta^m \binom{n}{m}$ $m$-element subsets of $\{1, \ldots, n\}$ without a $k$-term arithmetic progression. We give a short, inductive proof of this result. Consequently, this provides a short proof of the Szemer\'edi's theorem in random subsets of integers., Comment: 6 pages. Companion note to the paper "A new proof of the KLR conjecture" [arXiv:2108.05687]

Estimating the probability that the Erd\H{o}s-R\'enyi random graph $G(n,m)$ is $H$-free, for a fixed graph $H$, is one of the fundamental problems in random graph theory. If $m$ is such that each edge of $G(n,m)$ belongs to a copy of $H'$ for every $H' \subseteq H$, in expectation, then it is known that $G(n,m)$ is $H$-free with probability $\exp(- \Theta(m))$. The KLR conjecture, slightly rephrased, states that if we further condition on uniform edge distribution, the archetypal property of random graphs, the probability of being $H$-free becomes superexponentially small in the number of edges. While being interesting on its own, the conjecture has received significant attention due to its connection with the sparse regularity lemma, and the many results in random graphs that follow. It was proven by Balogh, Morris, and Samotij and, independently, by Saxton and Thomason, as one of the first applications of the hypergraph containers method. We give a new direct proof using induction., Comment: Comments are welcome!

We design a randomized algorithm that finds a Hamilton cycle in $\mathcal{O}(n)$ time with high probability in a random graph $G_{n,p}$ with edge probability $p\ge C \log n / n$. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. We use this method to obtain the following results. -We show that the size-Ramsey number of logarithmically long subdivisions of bounded degree graphs is linear in their number of vertices, settling a conjecture of Pak (2002). -We give a deterministic, polynomial time online algorithm for finding vertex-disjoint paths of prescribed length between given pairs of vertices in an expander graph. Our result answers a question of Alon and Capalbo (2007). -We show that relatively weak bounds on the spectral ratio of $d$-regular graphs force the existence of a topological minor of $K_t$ where $t=(1-o(1))d$. We also exhibit a construction which shows that the theoretical maximum $t=d+1$ cannot be attained even if $\lambda=O(\sqrt{d})$. This answers a question of Fountoulakis, K\"uhn and Osthus (2009)., Comment: improved exposition; typos fixed; new section and results about topological minors

The $r$-size-Ramsey number $\hat{R}_r(H)$ of a graph $H$ is the smallest number of edges a graph $G$ can have, such that for every edge-coloring of $G$ with $r$ colors there exists a monochromatic copy of $H$ in $G$. For a graph $H$, we denote by $H^q$ the graph obtained from $H$ by subdividing its edges with $q{-}1$ vertices each. In a recent paper of Kohayakawa, Retter and R{\"o}dl, it is shown that for all constant integers $q,r\geq 2$ and every graph $H$ on $n$ vertices and of bounded maximum degree, the $r$-size-Ramsey number of $H^q$ is at most $(\log n)^{20(q-1)}n^{1+1/q}$, for $n$ large enough. We improve upon this result using a significantly shorter argument by showing that $\hat{R}_r(H^q)\leq O(n^{1+1/q})$ for any such graph $H$., Comment: 12 pages, 1 figure

Let $r \ge 4$ be an integer and consider the following game on the complete graph $K_n$ for $n \in r \mathbb{Z}$: Two players, Maker and Breaker, alternately claim previously unclaimed edges of $K_n$ such that in each turn Maker claims one and Breaker claims $b \in \mathbb{N}$ edges. Maker wins if her graph contains a $K_r$-factor, that is a collection of $n/r$ vertex-disjoint copies of $K_r$, and Breaker wins otherwise. In other words, we consider a $b$-biased $K_r$-factor Maker-Breaker game. We show that the threshold bias for this game is of order $n^{2/(r+2)}$. This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen et al.\ who resolved the case $r \in \{3,4\}$ up to a logarithmic factor.

In this short note we study two questions about the existence of subgraphs of the hypercube $Q_n$ with certain properties. The first question, due to Erd\H{o}s--Hamburger--Pippert--Weakley, asks whether there exists a bounded degree subgraph of $Q_n$ which has diameter $n$. We answer this question by giving an explicit construction of such a subgraph with maximum degree at most 120. The second problem concerns properties of $k$-additive spanners of the hypercube, that is, subgraphs of $Q_n$ in which the distance between any two vertices is at most $k$ larger than in $Q_n$. Denoting by $\Delta_{k,\infty}(n)$ the minimum possible maximum degree of a $k$-additive spanner of $Q_n$, Arizumi--Hamburger--Kostochka showed that $$\frac{n}{\ln n}e^{-4k}\leq \Delta_{2k,\infty}(n)\leq 20\frac{n}{\ln n}\ln \ln n.$$ We improve their upper bound by showing that $$\Delta_{2k,\infty}(n)\leq 10^{4k} \frac{n}{\ln n}\ln^{(k+1)}n,$$where the last term denotes a $k+1$-fold iterated logarithm., Comment: 10 pages

Given a partial Steiner triple system (STS) of order $n$, what is the order of the smallest complete STS it can be embedded into? The study of this question goes back more than 40 years. In this paper we answer it for relatively sparse STSs, showing that given a partial STS of order $n$ with at most $r \le \varepsilon n^2$ triples, it can always be embedded into a complete STS of order $n+O(\sqrt{r})$, which is asymptotically optimal. We also obtain similar results for completions of Latin squares and other designs. This suggests a new, natural class of questions, called deficiency problems. Given a global spanning property $\mathcal{P}$ and a graph $G$, we define the deficiency of the graph $G$ with respect to the property $\mathcal{P}$ to be the smallest positive integer $t$ such that the join $G\ast K_t$ has property $\mathcal{P}$. To illustrate this concept we consider deficiency versions of some well-studied properties, such as having a $K_k$-decomposition, Hamiltonicity, having a triangle-factor and having a perfect matching in hypergraphs. The main goal of this paper is to propose a systematic study of these problems; thus several future research directions are also given.

The conjecture of Brown, Erd\H{o}s and S\'os from 1973 states that, for any $k \ge 3$, if a $3$-uniform hypergraph $H$ with $n$ vertices does not contain a set of $k+3$ vertices spanning at least $k$ edges then it has $o(n^2)$ edges. The case $k=3$ of this conjecture is the celebrated $(6,3)$-theorem of Ruzsa and Szemer\'edi which implies Roth's theorem on $3$-term arithmetic progressions in dense sets of integers. Solymosi observed that, in order to prove the conjecture, one can assume that $H$ consists of triples $(a, b, ab)$ of some finite quasigroup $\Gamma$. Since this problem remains open for all $k \geq 4$, he further proposed to study triple systems coming from finite groups. In this case he proved that the conjecture holds also for $k = 4$. Here we completely resolve the Brown-Erd\H{o}s-S\'os conjecture for all finite groups and values of $k$. Moreover, we prove that the hypergraphs coming from groups contain sets of size $\Theta(\sqrt{k})$ which span $k$ edges. This is best possible and goes far beyond the conjecture.

We show that if $G$ is a graph on $n$ vertices, with all degrees comparable to some $d = d(n)$, and without a sparse cut, for a suitably chosen notion of sparseness, then it contains a complete minor of order \[ \Omega\left( \sqrt{\frac{n d}{\log d}} \right). \] As a corollary we determine the order of a largest complete minor one can guarantee in $d$-regular graphs for which the second largest eigenvalue is bounded away from $d/2$, in $(d/n, o(d))$-jumbled graphs, and in random $d$-regular graphs, for almost all $d = d(n)$.

A seminal result by Koml\'os, Sark\"ozy, and Szemer\'edi states that if a graph $G$ with $n$ vertices has minimum degree at least $kn/(k + 1)$, for some $k \in \mathbb{N}$ and $n$ sufficiently large, then it contains the $k$-th power of a Hamilton cycle. This is easily seen to be the largest power of a Hamilton cycle one can guarantee, given such a minimum degree assumption. Following a recent trend of studying effects of adding random edges to a dense graph, the model known as the randomly perturbed graph, Dudek, Reiher, Ruci\'nski, and Schacht showed that if the minimum degree is at least $kn/(k + 1) + \alpha n$, for any constant $\alpha > 0$, then adding $O(n)$ random edges on top almost surely results in a graph which contains the $(k + 1)$-st power of a Hamilton cycle. We show that the effect of these random edges is significantly stronger, namely that one can almost surely find the $(2k + 1)$-st power. This is the largest power one can guarantee in such a setting., Comment: 18 pages; 6 figures; published version

For fixed graphs $F_1,\dotsc,F_r$, we prove an upper bound on the threshold function for the property that $G(n,p) \to (F_1,\dotsc,F_r)$. This establishes the $1$-statement of a conjecture of Kohayakawa and Kreuter., Comment: 12 pages; several minor changes

A seminal result of Hajnal and Szemer\'{e}di states that if a graph $G$ with $n$ vertices has minimum degree $\delta(G) \ge (r-1)n/r$ for some integer $r \ge 2$, then $G$ contains a $K_r$-factor, assuming $r$ divides $n$. Extremal examples which show optimality of the bound on $\delta(G)$ are very structured and, in particular, contain large independent sets. In analogy to the Ramsey-Tur\'an theory, Balogh, Molla, and Sharifzadeh initiated the study of how the absence of such large independent sets influences sufficient minimum degree. We show the following two related results: $\bullet$ For any $r > \ell \ge 2$, if $G$ is a graph satisfying $\delta(G) \ge (r - \ell)n/(r - \ell + 1) +\Omega(n)$ and $\alpha_\ell(G)=o(n)$, that is, a largest $K_\ell$-free induced subgraph has at most $o(n)$ vertices, then $G$ contains a $K_r$-factor. This is optimal for $\ell = r - 1$ and extends a result of Balogh, Molla, and Sharifzadeh who considered the case $r = 3$. $\bullet$ If a graph $G$ satisfies $\delta(G) =\Omega(n)$ and $\alpha_r^*(G) =o(n)$, that is, every induced $K_r$-free $r$-partite subgraph of $G$ has at least one vertex class of size $o(n)$, then it contains a $K_r$-factor. A similar statement is proven for a general graph $H$.

We show that if the second eigenvalue $\lambda$ of a $d$-regular graph $G$ on $n \in 3 \mathbb{Z}$ vertices is at most $\varepsilon d^2/(n \log n)$, for a small constant $\varepsilon > 0$, then $G$ contains a triangle-factor. The bound on $\lambda$ is at most an $O(\log n)$ factor away from the best possible one: Krivelevich, Sudakov and Szab\'o, extending a construction of Alon, showed that for every function $d = d(n)$ such that $\Omega(n^{2/3}) \le d \le n$ and infinitely many $n \in \mathbb{N}$ there exists a $d$-regular triangle-free graph $G$ with $\Theta(n)$ vertices and $\lambda = \Omega(d^2 / n)$.

A classic result of Erd\H{o}s, Gy\'arf\'as and Pyber states that for every coloring of the edges of $K_n$ with $r$ colors, there is a cover of its vertex set by at most $f(r) = O(r^2 \log r)$ vertex-disjoint monochromatic cycles. In particular, the minimum number of such covering cycles does not depend on the size of $K_n$ but only on the number of colors. We initiate the study of this phenomena in the case where $K_n$ is replaced by the random graph $\mathcal G(n,p)$. Given a fixed integer $r$ and $p =p(n) \ge n^{-1/r + \varepsilon}$, we show that with high probability the random graph $G \sim \mathcal G(n,p)$ has the property that for every $r$-coloring of the edges of $G$, there is a collection of $f'(r) = O(r^8 \log r)$ monochromatic cycles covering all the vertices of $G$. Our bound on $p$ is close to optimal in the following sense: if $p\ll (\log n/n)^{1/r}$, then with high probability there are colorings of $G\sim\mathcal G(n,p)$ such that the number of monochromatic cycles needed to cover all vertices of $G$ grows with $n$., Comment: 24 pages, 1 figure (minor changes, added figure)

Let $\{G_i\}$ be the random graph process: starting with an empty graph $G_0$ with $n$ vertices, in every step $i \geq 1$ the graph $G_i$ is formed by taking an edge chosen uniformly at random among the non-existing ones and adding it to the graph $G_{i - 1}$. The classical `hitting-time' result of Ajtai, Koml\'{o}s, and Szemer\'{e}di, and independently Bollob\'{a}s, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches $2$, that is if $\delta(G_i) \ge 2$ then $G_i$ is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for $m \geq (\tfrac{1}{6} + o(1))n\log n$ edges, the $2$-core of the graph $G_m$ remains Hamiltonian even after an adversary removes $(\tfrac{1}{2} - o(1))$-fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings., Comment: 23 pages; small updates to the paper after anonymous reviewers' reports

A graph is said to be $\mathcal{H}(n, \Delta)$-universal if it contains every graph on $n$ vertices with maximum degree at most $\Delta$. Using a `matching-based' embedding technique introduced by Alon and F\"uredi, Dellamonica, Kohayakawa, R\"odl and Ruci\'nski showed that the random graph $G_{n,p}$ is asymptotically almost surely $\mathcal{H}(n, \Delta)$-universal for $p = \tilde \Omega(n^{-1/\Delta})$ - a threshold for the property that every subset of $\Delta$ vertices has a common neighbour. This bound has become a benchmark in the field and many subsequent results on embedding spanning structures of maximum degree $\Delta$ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that $G_{n,p}$ is almost surely $\mathcal{H}(n, \Delta)$-universal for $p = \tilde \Omega(n^{- 1/(\Delta-1/2)})$.

Conlon, Gowers, Samotij, and Schacht showed that for a given graph $H$ and a constant $\gamma > 0$, there exists $C > 0$ such that if $p \ge Cn^{-1/m_2(H)}$ then asymptotically almost surely every spanning subgraph $G$ of the random graph $\mathcal{G}(n,p)$ with minimum degree at least $\delta(G) \ge (1 - 1/\chi_{\mathrm{cr}}(H) + \gamma )np$ contains an $H$-packing that covers all but at most $\gamma n$ vertices. Here, $\chi_{\mathrm{cr}}(H)$ denotes the critical chromatic threshold, a parameter introduced by Koml\'os. We show that this theorem can be bootstraped to obtain an $H$-packing covering all but at most $\gamma (C/p)^{m_2(H)}$ vertices, which is strictly smaller when $p > C n^{-1/m_2(H)}$. In the case where $H = K_3$ this answers the question of Balogh, Lee, and Samotij. Furthermore, we give an upper bound on the size of an $H$-packing for certain ranges of $p$.

We prove that every graph with sufficiently large minimum degree $d$ contains a spanning forest in which every component is a star of size at least $\sqrt{d} - \tilde O(d^{1/4})$. This improves the result of Alon and Wormald and is optimal up to the lower order term.

A celebrated result of R\"odl and Ruci\'nski states that for every graph $F$, which is not a forest of stars and paths of length $3$, and fixed number of colours $r\ge 2$ there exist positive constants $c, C$ such that for $p \leq cn^{-1/m_2(F)}$ the probability that every colouring of the edges of the random graph $G(n,p)$ contains a monochromatic copy of $F$ is $o(1)$ (the "0-statement"), while for $p \geq Cn^{-1/m_2(F)}$ it is $1-o(1)$ (the "1-statement"). Here $m_2(F)$ denotes the $2$-density of $F$. On the other hand, the case where $F$ is a forest of stars has a coarse threshold which is determined by the appearance of a certain small subgraph in $G(n, p)$. Recently, the natural extension of the 1-statement of this theorem to $k$-uniform hypergraphs was proved by Conlon and Gowers and, independently, by Friedgut, R\"odl and Schacht. In particular, they showed an upper bound of order $n^{-1/m_k(F)}$ for the $1$-statement, where $m_k(F)$ denotes the $k$-density of $F$. Similarly as in the graph case, it is known that the threshold for star-like hypergraphs is given by the appearance of small subgraphs. In this paper we show that another type of thresholds exists if $k \ge 4:$ there are $k$-uniform hypergraphs for which the threshold is determined by the asymmetric Ramsey problem in which a different hypergraph has to be avoided in each colour-class. Along the way we obtain a general bound on the $1$-statement for asymmetric Ramsey properties in random hypergraphs. This extends the work of Kohayakawa and Kreuter, and of Kohayakawa, Schacht and Sp\"ohel who showed a similar result in the graph case. We prove the corresponding 0-statement for hypergraphs satisfying certain balancedness conditions.

We show that for any constant $\Delta \ge 2$, there exists a graph $G$ with $O(n^{\Delta / 2})$ vertices which contains every $n$-vertex graph with maximum degree $\Delta$ as an induced subgraph. For odd $\Delta$ this significantly improves the best-known earlier bound of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least $\Omega(n^{\Delta/2})$ vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of $G$ is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph $H$ on $n$ vertices with maximum degree at most $\Delta$, an induced subgraph of $G$ isomorphic to $H$.

A random jigsaw puzzle is constructed by arranging $n^2$ square pieces into an $n \times n$ grid and assigning to each edge of a piece one of $q$ available colours uniformly at random, with the restriction that touching edges receive the same colour. We show that if $q = o(n)$ then with high probability such a puzzle does not have a unique solution, while if $q \ge n^{1 + \varepsilon}$ for any constant $\varepsilon > 0$ then the solution is unique. This solves a conjecture of Mossel and Ross (Shotgun assembly of labeled graphs, arXiv:1504.07682).

We show that for every $k \in \mathbb{N}$ there exists $C > 0$ such that if $p^k \ge C \log^8 n / n$ then asymptotically almost surely the random graph $G_{n,p}$ contains the $k$\textsuperscript{th} power of a Hamilton cycle. This determines the threshold for appearance of the square of a Hamilton cycle up to the logarithmic factor, improving a result of K\"uhn and Osthus. Moreover, our proof provides a randomized quasi-polynomial algorithm for finding such powers of cycles. Using similar ideas, we also give a randomized quasi-polynomial algorithm for finding a tight Hamilton cycle in the random $k$-uniform hypergraph $G_{n,p}^{(k)}$ for $p \ge C \log^8 n/ n$. The proofs are based on the absorbing method and follow the strategy of K\"uhn and Osthus, and Allen et al. The new ingredient is a general Connecting Lemma which allows us to connect tuples of vertices using arbitrary structures at a nearly optimal value of $p$. Both the Connecting Lemma and its proof, which is based on Janson's inequality and a greedy embedding strategy, might be of independent interest.

A graph $G$ is said to be $\mathcal H(n,\Delta)$-universal if it contains every graph on $n$ vertices with maximum degree at most $\Delta$. It is known that for any $\varepsilon > 0$ and any natural number $\Delta$ there exists $c > 0$ such that the random graph $G(n,p)$ is asymptotically almost surely $\mathcal H((1-\varepsilon)n,\Delta)$-universal for $p \geq c (\log n/n)^{1/\Delta}$. Bypassing this natural boundary, we show that for $\Delta \geq 3$ the same conclusion holds when $p = \omega\left(n^{-\frac{1}{\Delta-1}}\log^5 n\right)$.

In his seminal paper from 1952 Dirac showed that the complete graph on $n\geq 3$ vertices remains Hamiltonian even if we allow an adversary to remove $\lfloor n/2\rfloor$ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on $n\geq 3$ vertices with minimum in- and out-degree at least $n/2$ contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of \emph{local resilience}. The local resilience of a graph (digraph) $G$ with respect to a property $\mathcal{P}$ is the maximum number $r$ such that $G$ has the property $\mathcal{P}$ even if we allow an adversary to remove an $r$-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is $1/2$. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability $p=\omega(\log n /n)$ with respect to Hamiltonicity is $1/2\pm o(1)$. For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability $p=\omega(\log n/\sqrt{n})$. In this paper we significantly improve their result to $p=\omega(\log^8 n/ n)$, which is optimal up to the polylogarithmic factor.