We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More âŠ
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G α on n vertices with ÎŽ ( G α ) ℠αn for α > 0 and we add to it the binomial random graph G ( n , C / n ), then with high probability the graph G α âȘ G ( n , C / n ) contains copies of all spanning trees with maximum degree at most Î simultaneously, where C depends only on α and Î.
We study the model G α âȘ G ( n , p ) of randomly perturbed dense graphs, where G α is any n-vertex graph with minimum degree at least âŠ
We study the model G α âȘ G ( n , p ) of randomly perturbed dense graphs, where G α is any n-vertex graph with minimum degree at least α n and G ( n , p ) is the binomial random graph. We introduce a general approach for studying the appearance of spanning subgraphs in this model using absorption. This approach yields simpler proofs of several known results. We also use it to derive the following two new results. For every α > 0 and Î â„ 5 , and every n-vertex graph F with maximum degree at most Î, we show that if p = Ï ( n â 2 / ( Î + 1 ) ) , then G α âȘ G ( n , p ) with high probability contains a copy of F. The bound used for p here is lower by a log -factor in comparison to the conjectured threshold for the general appearance of such subgraphs in G ( n , p ) alone, a typical feature of previous results concerning randomly perturbed dense graphs. We also give the first example of graphs where the appearance threshold in G α âȘ G ( n , p ) is lower than the appearance threshold in G ( n , p ) by substantially more than a log -factor. We prove that, for every k â„ 2 and α > 0 , there is some η > 0 for which the kth power of a Hamilton cycle with high probability appears in G α âȘ G ( n , p ) when p = Ï ( n â 1 / k â η ) . The appearance threshold of the kth power of a Hamilton cycle in G ( n , p ) alone is known to be n â 1 / k , up to a log -term when k = 2 , and exactly for k > 2 .
We introduce and study a novel semiârandom multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex âŠ
We introduce and study a novel semiârandom multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v . For various natural monotone increasing graph properties , we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies . Along the way, we show that the process is general enough to approximate (using suitable strategies) several wellâstudied random graph models.
Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges with the âŠ
Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges with the property that, in any colouring of E ( G ) with s colours, there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex bounded degree tree is linear in n. As a corollary, we obtain that the s-colour size-Ramsey number of n-vertex graphs with bounded treewidth and bounded degree is linear in n, which answers a question raised by KamÄev, Liebenau, Wood and Yepremyan.
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was âŠ
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by PĂłsa and Korshunov on the threshold in $\mathbb{G}(n,p)$. In this note we extend this result in $\mathcal{G}_\alpha\cup\mathbb{G}(n,p)$ to sparser graphs with $\alpha=o(1)$. More precisely, for any $\varepsilon>0$ and $\alpha \colon \mathbb{N} \mapsto (0,1)$ we show that a.a.s. $\mathcal{G}_\alpha\cup \mathbb{G}(n,\beta /n)$ is Hamiltonian, where $\beta = -(6 + \varepsilon) \log(\alpha)$. If $\alpha>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $\alpha=O(1/n)$ the random part $\mathbb{G}(n,p)$ is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into $\mathbb{G}(n,p)$.
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> âŠ
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k = n^{\theta }$ </tex-math></inline-formula> (with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\theta \in (0,1)$ </tex-math></inline-formula> ), with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> individuals among which <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula> of tests an individual can be placed in, or the maximum number <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Gamma $ </tex-math></inline-formula> of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula> -divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Gamma $ </tex-math></inline-formula> -sized tests, we provide a comprehensive analysis of the regime <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Gamma = \Theta (1)$ </tex-math></inline-formula> , and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.
Abstract We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum âŠ
Abstract We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$ . We prove that asymptotically almost surely $G \cup G(n,p)$ contains at least $\min \{\delta (G), \lfloor n/3 \rfloor \}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$ , where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac. Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480â516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480â516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159â176], this fully resolves the existence of triangle factors in randomly perturbed graphs. We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and $2$ -universality.
We solve a problem of Krivelevich, Kwan and Sudakov [SIAM Journal on Discrete Mathematics 31 (2017), 155-171] concerning the threshold for the containment of all bounded degree spanning trees in âŠ
We solve a problem of Krivelevich, Kwan and Sudakov [SIAM Journal on Discrete Mathematics 31 (2017), 155-171] concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph $G_\alpha$ on $n$ vertices with $\delta(G_\alpha)\ge \alpha n$ for $\alpha>0$ and we add to it the binomial random graph $G(n,C/n)$, then with high probability the graph $G_\alpha\cup G(n,C/n)$ contains copies of all spanning trees with maximum degree at most $\Delta$ simultaneously, where $C$ depends only on $\alpha$ and $\Delta$.
We study the problem of finding pairwise vertex-disjoint copies of the â-vertex cycle Câ in the randomly perturbed graph model, which is the union of a deterministic n-vertex graph G âŠ
We study the problem of finding pairwise vertex-disjoint copies of the â-vertex cycle Câ in the randomly perturbed graph model, which is the union of a deterministic n-vertex graph G and the binomial random graph G(n, p). For â â„ 3 we prove that asymptotically almost surely G U G(n, p) contains min{ÎŽ(G), min{ÎŽ(G), [n/l]} pairwise vertex-disjoint cycles Câ, provided p â„ C log n/n for C sufficiently large. Moreover, when ÎŽ(G) ℠αn with 0 †α/l and G and is not 'close' to the complete bipartite graph Kαn,(1 - α)n, then p â„ C/n suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that p â„ C/n suffices when α > n/l for finding [n/l] cycles Câ. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson-Kahn-Vu Theorem for Câ-factors and the resolution of the El-Zahar Conjecture for Câ-factors by Abbasi.
Abstract Given a collection of hypergraphs with the same vertex set, an âedge graph is a transversal if there is a bijection such that for each . How large does âŠ
Abstract Given a collection of hypergraphs with the same vertex set, an âedge graph is a transversal if there is a bijection such that for each . How large does the minimum degree of each need to be so that necessarily contains a copy of that is a transversal? Each in the collection could be the same hypergraph, hence the minimum degree of each needs to be large enough to ensure that . Since its general introduction by Joos and Kim ( Bull. Lond. Math. Soc . 52 (2020) 498â504), a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Diracâtype results for (powers of) Hamilton cycles. For example, we derive that any collection of graphs on an âvertex set, each with minimum degree at least , contains a transversal copy of the th power of a Hamilton cycle. This can be viewed as a rainbow version of the PĂłsaâSeymour conjecture.
Given a hypergraph $H$, the size-Ramsey number $\hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring âŠ
Given a hypergraph $H$, the size-Ramsey number $\hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $H$. We prove that the size-Ramsey number of the $3$-uniform tight path on $n$ vertices $P^{(3)}_n$ is linear in $n$, i.e., $\hat{r}_2(P^{(3)}_n) = O(n)$. This answers a question by Dudek, Fleur, Mubayi, and R\"odl for $3$-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved $\hat{r}_2(P^{(3)}_n) = O(n^{3/2} \log^{3/2} n)$.
We study the model $G_\alpha\cup G(n,p)$ of randomly perturbed dense graphs, where $G_\alpha$ is any $n$-vertex graph with minimum degree at least $\alpha n$ and $G(n,p)$ is the binomial random âŠ
We study the model $G_\alpha\cup G(n,p)$ of randomly perturbed dense graphs, where $G_\alpha$ is any $n$-vertex graph with minimum degree at least $\alpha n$ and $G(n,p)$ is the binomial random graph. We introduce a general approach for studying the appearance of spanning subgraphs in this model, which we call assisted absorption. This approach yields simpler proofs of several known results. We also use it to derive the following two new results.
For every $\alpha>0$ and $\Delta\ge 5$, and every $n$-vertex graph $F$ with maximum degree at most $\Delta$, we show that if $p=\omega(n^{-2/(\Delta+1)})$ then $G_\alpha \cup G(n,p)$ with high probability contains a copy of $F$. The bound used for $p$ here is lower by a $\log$-factor in comparison to the conjectured threshold for the general appearance of such subgraphs in $G(n,p)$ alone, a typical feature of previous results concerning randomly perturbed dense graphs.
We also give the first example of graphs where the appearance threshold in $G_\alpha \cup G(n,p)$ is lower than the appearance threshold in $G(n,p)$ by substantially more than a $\log$-factor. We prove that, for every $k\geq 2$ and $\alpha >0$, there is some $\eta>0$ for which the $k$th power of a Hamilton cycle with high probability appears in $G_\alpha \cup G(n,p)$ when $p=\omega(n^{-1/k-\eta})$. The appearance threshold of the $k$th power of a Hamilton cycle in $G(n,p)$ alone is known to be $n^{-1/k}$, up to a $\log$-term when $k=2$, and exactly for $k>2$.
For graphs G and H, let Gâ¶prbH denote the property that for every proper edge colouring of G there is a rainbow copy of H in G. Extending a result âŠ
For graphs G and H, let Gâ¶prbH denote the property that for every proper edge colouring of G there is a rainbow copy of H in G. Extending a result of Nenadov, Person, Ć koriÄ and Steger (2017), we prove that nâ1/m2(Câ) is the threshold for G(n,p)â¶prbCâ when â â„ 5. Thus our result together with a result of the third author which says that the threshold for Gâ¶prbC4 is nâ3/4 settles the problem of determining the threshold for Gâ¶prbCâ for all values of â.
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was âŠ
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by Posa and Korsunov on the threshold in $\mathbb{G}(n,p)$. In this note we extend this result in $\mathcal{G}_\alpha \cup \mathbb{G}(n,p)$ to sparser graphs with $\alpha=o(1)$. More precisely, for any $\varepsilon>0$ and $\alpha \colon \mathbb{N} \mapsto (0,1)$ we show that a.a.s. $\mathcal{G}_\alpha \cup \mathbb{G}(n,\beta /n)$ is Hamiltonian, where $\beta = -(6 + \varepsilon) \log(\alpha)$. If $\alpha>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $\alpha=O(1/n)$ the random part $\mathbb{G}(n,p)$ is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into $\mathbb{G}(n,p)$.
Given a collection of hypergraphs $\fH=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such âŠ
Given a collection of hypergraphs $\fH=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\fH$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $F\subseteq H_i$. Since its general introduction by Joos and Kim~[Bull. Lond. Math. Soc., 2020, 52(3): 498â504], a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. For example, we derive that any collection of $rn$ graphs on an $n$-vertex set, each with minimum degree at least $(r/(r+1)+o(1))n$, contains a transversal copy of the $r$-th power of a Hamilton cycle. This can be viewed as a rainbow version of the P\'osa-Seymour conjecture.
In the group testing problem one aims to infer a small set of $k$ infected individuals out of a large population of size $n$. At our disposal we have a âŠ
In the group testing problem one aims to infer a small set of $k$ infected individuals out of a large population of size $n$. At our disposal we have a testing scheme which allows us to test a group of individuals, such that the outcome of the test is positive, if and only if at least one infected individual is part of the test. All tests are carried out in parallel. The overall goal is to find a test design and an inference algorithm requiring as few tests as possible, such that the infected individuals can be identified with high probability. As most relevant during the outbreak of pandemic diseases (Wang et al., 2011), our analysis focusses on the so-called sublinear regime of group testing, where $k \sim n^\theta$. The optimal group testing schemes require a test-size of $\sim n/k$ and each individual has to take part in $\sim \log n$ tests (Coja-Oghlan et. al, 2019). In real world applications, like testing many individuals in a short period of time during the outbreak of epidemics, pooling in such a way is not possible due to dilution effects. Evidence of those effects is known for important applications like HIV (Wein, 1996) or COVID-19 (Seifried and Ciesek, 2020). Our main contribution is the analysis of a group testing model, where we restrict the individuals-per-test to be finite. We present an easy to implement scheme to pool individuals into tests under these natural restrictions coming with the efficient decoding algorithm DD and present simulations which suggest that the decoding procedure succeeds for moderate population sizes. Furthermore, we show that our pooling scheme requires the fewest tests as possible under all pooling schemes. Finally, we apply our methods to the finitely many tests-per-individuals setting, where we provide a full understanding of the random regular test-design in this model by building up on work of (Gandikota et al., 2016).
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta}$ âŠ
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta}$ (with $\theta \in (0,1)$), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $\Delta$ of tests an individual can be placed in, or the maximum number $\Gamma$ of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $\Delta$-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of $\eul$ more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of $\Gamma$-sized tests, we provide a comprehensive analysis of the regime $\Gamma = \Theta(1)$, and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.
In this paper the problem of finding various spanning structures in random hypergraphs is studied. We notice that a general result of Riordan [Spanning subgraphs of random graphs, Combinatorics, Probability âŠ
In this paper the problem of finding various spanning structures in random hypergraphs is studied. We notice that a general result of Riordan [Spanning subgraphs of random graphs, Combinatorics, Probability & Computing 9 (2000), no. 2, 125-148] can be adapted from random graphs to random $r$-uniform hypergaphs and provide sufficient conditions when a random $r$-uniform hypergraph $\mathcal{H}^{(r)}(n,p)$ contains a given spanning structure a.a.s. We also discuss several spanning structures such as cube-hypergraphs, lattices, spheres and Hamilton cycles in hypergraphs.
Moreover, we study universality, i.e. when does an $r$-uniform hypergraph contain any hypergraph on $n$ vertices and with maximum vertex degree bounded by $\Delta$? For $\mathcal{H}^{(r)}(n,p)$ it is shown that this holds for $p= \omega \left((\ln n/n)^{1/\Delta}\right)$ a.a.s. by combining approaches taken by Dellamonica, Kohayakawa, Rodl and Rucinski [An improved upper bound on the density of universal random graphs, Random Structures Algorithms 46 (2015), no. 2, 274-299] and of Ferber, Nenadov and Peter [Universality of random graphs and rainbow embedding, Random Structures Algorithms, to appear]. Furthermore it is shown that the random graph $G(n,p)$ for appropriate $p$ and explicit constructions of universal graphs due to Alon, Capalbo, Kohayakawa, Rodl, Rucinski and Szemeredi and Alon and Capalbo yield constructions of universal hypergraphs that are sparser than the random hypergraph $\mathcal{H}^{(r)}(n,p)$ with $p= \omega \left((\ln n/n)^{1/\Delta}\right)$.
A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$-uniform hypergraphs with âŠ
A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$-uniform hypergraphs with maximum vertex degree bounded by $\Delta$ and at most $n$ vertices any universal hypergraph has to contain $\Omega(n^{r-r/\Delta})$ many edges. We exploit constructions of Alon and Capalbo to obtain universal $r$-uniform hypergraphs with the optimal number of edges $O(n^{r-r/\Delta})$ when $r$ is even, $r \mid \Delta$ or $\Delta=2$. Further we generalize the result of Alon and Asodi about optimal universal graphs for the family of graphs with at most $m$ edges and no isolated vertices to hypergraphs.
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ âŠ
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ and the binomial random graph $G(n,p)$. For $\ell \ge 3$ we prove that asymptotically almost surely $G \cup G(n,p)$ contains $\min \{\delta(G), \lfloor n/\ell \rfloor \}$ pairwise vertex-disjoint cycles $C_\ell$, provided $p \ge C \log n/n$ for $C$ sufficiently large. Moreover, when $\delta(G) \ge\alpha n$ with $0 1/\ell$ for finding $\lfloor n/\ell \rfloor$ cycles $C_\ell$.
Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson--Kahn--Vu Theorem for $C_\ell$-factors and the resolution of the El-Zahar Conjecture for $C_\ell$-factors by Abbasi.
We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$-vertex graph $G$ with linear minimum degree and the âŠ
We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$-vertex graph $G$ with linear minimum degree and the binomial random graph $G(n,p)$. We prove that asymptotically almost surely $G \cup G(n,p)$ contains $\min \{\delta(G), \lfloor n/3 \rfloor \}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$, where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac. Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, to appear] in the case of triangle-factors. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159-176] this fully resolves the existence of triangle-factors in randomly perturbed graphs. We also prove a stability version of our result. Finally, we discuss further generalisations to larger clique-factors, larger cycle-factors, and $2$-universality.
For graphs $G$ and $H$, let $G {\displaystyle\smash{\begin{subarray}{c} \hbox{$\tiny\rm rb$} \\ \longrightarrow \\ \hbox{$\tiny\rm p$} \end{subarray}}}H$ denote the property that for every proper edge-colouring of $G$ there is a rainbow âŠ
For graphs $G$ and $H$, let $G {\displaystyle\smash{\begin{subarray}{c} \hbox{$\tiny\rm rb$} \\ \longrightarrow \\ \hbox{$\tiny\rm p$} \end{subarray}}}H$ denote the property that for every proper edge-colouring of $G$ there is a rainbow $H$ in $G$. It is known that, for every graph $H$, an asymptotic upper bound for the threshold function $p^{\rm rb}_H=p^{\rm rb}_H(n)$ of this property for the random graph $G(n,p)$ is $n^{-1/m^{(2)}(H)}$, where $m^{(2)}(H)$ denotes the so-called maximum $2$-density of $H$. Extending a result of Nenadov, Person, \v{S}kori\'c, and Steger [J. Combin. Theory Ser. B 124 (2017),1-38] we prove a matching lower bound for $p^{\rm rb}_{K_k}$ for $k\geq 5$. Furthermore, we show that $p^{\rm rb}_{K_4} = n^{-7/15}$.
Abstract In an r -uniform hypergraph on n vertices, a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges âŠ
Abstract In an r -uniform hypergraph on n vertices, a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of r vertices. We provide a first deterministic polynomial-time algorithm, which finds a.a.s. tight Hamilton cycles in random r -uniform hypergraphs with edge probability at least C log 3 n / n . Our result partially answers a question of Dudek and Frieze, who proved that tight Hamilton cycles exist already for p = Ï (1/ n ) for r = 3 and p = ( e + o (1))/ n for $r \ge 4$ using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Böttcher, Kohayakawa and Person, and Nenadov and Ć koriÄ, in various ways: the algorithm of Allen et al. is a randomized polynomial-time algorithm working for edge probabilities $p \ge {n^{ - 1 + \varepsilon}}$ , while the algorithm of Nenadov and Ć koriÄ is a randomized quasipolynomial-time algorithm working for edge probabilities $p \ge C\mathop {\log }\nolimits^8 n/n$ .
We introduce and study a novel semi-random multigraph process, described as follows. The process starts with an empty graph on $n$ vertices. In every round of the process, one vertex âŠ
We introduce and study a novel semi-random multigraph process, described as follows. The process starts with an empty graph on $n$ vertices. In every round of the process, one vertex $v$ of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to $v$.
For various natural monotone increasing graph properties $P$, we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies $P$. Along the way, we show that the process is general enough to approximate (using suitable strategies) several well-studied random graph models.
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{\longrightarrow} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending âŠ
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{\longrightarrow} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending a result of Nenadov, Person, Skoric and Steger [J. Combin. Theory Ser. B 124 (2017),1-38], we determine the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} C_\ell$ for cycles $C_\ell$ of any given length $\ell \geq 4$.
Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from âŠ
Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game if she is able to occupy any winning set $F \in \mathcal{F}$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_\alpha$ with minimum degree at least $\alpha n$ and a binomial random graph $G_{n,p}$. Depending on $\alpha$ and Breaker's bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_{\alpha}\cup G_{n,p}$, and we discuss the $H$-game when $b=1$. Furthermore, we give optimal results for the Waiter-Client versions of all mentioned games.
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any $Îł>0$ and $k\ge3$, we show that asymptotically almost surely, every subgraph of the binomial random $k$-uniform âŠ
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any $Îł>0$ and $k\ge3$, we show that asymptotically almost surely, every subgraph of the binomial random $k$-uniform hypergraph $G^{(k)}\big(n,n^{Îł-1}\big)$ in which all $(k-1)$-sets are contained in at least $\big(\tfrac12+2Îł\big)pn$ edges has a tight Hamilton cycle. This is a cyclic ordering of the $n$ vertices such that each consecutive $k$ vertices forms an edge.
We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of Erd\H{o}s. Most notably, we improve the upper bounds âŠ
We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of Erd\H{o}s. Most notably, we improve the upper bounds on the Ramsey multiplicity of $K_4$ and $K_5$ and settle the minimum number of independent sets of size $4$ in graphs with clique number at most $4$. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic $K_4$ or $K_5$ in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a graph of constant size and were found through search heuristics. They are complemented by lower bounds established using flag algebras, resulting in a fully computer-assisted approach. For some of our theorems we can also derive that the extremal construction is stable in a very strong sense. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gammaâș0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform âŠ
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gammaâș0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform hypergraph \(G^{(k)}\big(n,n^{\gamma-1}\big)\) in which all \((k-1)\)-sets are contained in at least \(\big(\tfrac12+2\gamma\big)pn\) edges has a tight Hamilton cycle. This is a cyclic ordering of the \(n\) vertices such that each consecutive \(k\) vertices forms an edge.Mathematics Subject Classifications: 05C80, 05C35Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience
A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$-uniform hypergraphs with âŠ
A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$-uniform hypergraphs with maximum vertex degree bounded by $\Delta$ and at most $n$ vertices every universal hypergraph has to contain $\Omega(n^{r-r/\Delta})$ many edges. We exploit constructions of Alon and Capalbo [Sparse universal graphs for bounded-degree graphs, Random Structures Algorithms 31 (2007), no. 2, 123-133; Optimal universal graphs with deterministic embedding, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2008, pp. 373-378] to obtain universal $r$-uniform hypergraphs with $O (n^{r-2/ \lceil 2\Delta/r \rceil})$ edges, in particularly matching the lower bound in the case $r \mid 2\Delta$.
A graph $G$ is called universal for a family of graphs $\mathcal{F}$ if it contains every element $F \in \mathcal{F}$ as a subgraph. Let $\mathcal{F}(n,2)$ be the family of all âŠ
A graph $G$ is called universal for a family of graphs $\mathcal{F}$ if it contains every element $F \in \mathcal{F}$ as a subgraph. Let $\mathcal{F}(n,2)$ be the family of all graphs with maximum degree $2$. Ferber, Kronenberg, and Luh [Optimal Threshold for a Random Graph to be 2-Universal, to appear in Transactions of the American Mathematical Society] proved that there exists a $C$ such that for $p \ge C (n^{-2/3} \log^{1/3} n )$ the random graph $G(n,p)$ a.a.s is $\mathcal{F}(n,2)$-universal, which is asymptotically optimal. For any $n$-vertex graph $G_\alpha$ with minimum degree $\delta(G_\alpha) \ge \alpha n$ Aigner and Brandt [Embedding arbitrary graphs of maximum degree two, Journal of the London Mathematical Society 48 (1993), 39-51] proved that $G_\alpha$ is $\mathcal{F}(n,2)$-universal for an optimal $\alpha \ge 2/3$.
In this note, we consider the model of randomly perturbed graphs, which is the union $G_\alpha \cup G(n,p)$. We prove that $G_\alpha \cup G(n,p)$ is a.a.s. $\mathcal{F}(n,2)$-universal provided that $\alpha>0$ and $p=\omega(n^{-2/3})$. This is asymptotically optimal and improves on both results from above in the respective parameter. Furthermore, this extends a result of Bottcher, Montgomery, Parczyk, and Person [Embedding spanning bounded degree subgraphs in randomly perturbed graphs, arXiv:1802.04603 (2018)], who embed a given $F \in \mathcal{F}(n,2)$ at these values. We also prove variants with universality for the family $\mathcal{F}^\ell(n,2)$, all graphs from $\mathcal{F}(n,2)$ with girth at least $\ell$. For example, there exists an $\ell_0$ depending only on $\alpha$ such that for all $\ell \ge \ell_0$ already $p=\omega(1/n)$ is sufficient for $\mathcal{F}^\ell(n,2)$-universality.
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is âŠ
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is quasirandom; such pairs (H_1,H_2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), 1-38]: they showed that (K_t,F) is forcing where F is the graph that arises from K_t by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma 7, 2019] strengthened this result for t=3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t>3. We show that (t+2)/2 doublings always suffice.
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is âŠ
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is quasirandom; such pairs (H_1,H_2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), 1-38]: they showed that (K_t,F) is forcing where F is the graph that arises from K_t by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma 7, 2019] strengthened this result for t=3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t>3. We show that (t+2)/2 doublings always suffice.
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge âŠ
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge \frac{n+r-2}{2}$ when $nr \equiv 0 \pmod 2$. This answers a question of M.~Kriesell.
We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $\alpha \in (0,1)$, the union of any âŠ
We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $\alpha \in (0,1)$, the union of any $n$-vertex graph with minimum degree $\alpha n$ and the binomial random graph $G(n,p)$. This is known when $\alpha > 1/2$, and we determine the exact perturbed threshold probability in all the remaining cases, i.e., for each $\alpha \le 1/2$. We demonstrate that, as $\alpha$ ranges over the interval $(0,1)$, the threshold performs a countably infinite number of `jumps'. Our result has implications on the perturbed threshold for $2$-universality, where we also fully address all open cases.
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge âŠ
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge \frac{n+r-2}{2}$ when $nr \equiv 0 \pmod 2$. This answers a question of M.~Kriesell.
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ âŠ
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ and the binomial random graph $G(n,p)$. For $\ell \ge 3$ we prove that asymptotically almost surely $G \cup G(n,p)$ contains $\min \{\delta(G), \lfloor n/\ell \rfloor \}$ pairwise vertex-disjoint cycles $C_\ell$, provided $p \ge C \log n/n$ for $C$ sufficiently large. Moreover, when $\delta(G) \ge\alpha n$ with $0<\alpha \le 1/\ell$ and $G$ is not `close' to the complete bipartite graph $K_{\alpha n,(1-\alpha) n}$, then $p \ge C/n$ suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that $p \ge C/n$ suffices when $\alpha>1/\ell$ for finding $\lfloor n/\ell \rfloor$ cycles $C_\ell$. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson--Kahn--Vu Theorem for $C_\ell$-factors and the resolution of the El-Zahar Conjecture for $C_\ell$-factors by Abbasi.
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{{\longrightarrow}} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending âŠ
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{{\longrightarrow}} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending a result of Nenadov, Person, \v{S}kori\'{c} and Steger [J. Combin. Theory Ser. B 124 (2017),1-38], we determine the threshold for $G(n,p) \overset{\mathrm{rb}}{{\longrightarrow}} C_\ell$ for cycles $C_\ell$ of any given length $\ell \geq 4$.
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was âŠ
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by Pos\'{a} and Kor\v{s}unov on the threshold in $\mathbb{G}(n,p)$. In this note we extend this result in $\mathcal{G}_\alpha \cup \mathbb{G}(n,p)$ to sparser graphs with $\alpha=o(1)$. More precisely, for any $\varepsilon>0$ and $\alpha \colon \mathbb{N} \mapsto (0,1)$ we show that a.a.s. $\mathcal{G}_\alpha \cup \mathbb{G}(n,\beta /n)$ is Hamiltonian, where $\beta = -(6 + \varepsilon) \log(\alpha)$. If $\alpha>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $\alpha=O(1/n)$ the random part $\mathbb{G}(n,p)$ is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into $\mathbb{G}(n,p)$.
Sidorenko's conjecture states that the number of copies of any given bipartite graph in another graph of given density is asymptotically minimized by a random graph. The forcing conjecture further âŠ
Sidorenko's conjecture states that the number of copies of any given bipartite graph in another graph of given density is asymptotically minimized by a random graph. The forcing conjecture further strengthens this, claiming that any minimizer in fact needs to be quasi-random. Here we extend the family of bipartite graphs for which the forcing conjecture is known to hold to include balanced blow-ups of Sidorenko graphs and subdivisions of Sidorenko graphs by a forcing graph. This partially generalizes results by Conlon et al. (2018) and Conlon and Lee (2021). We also show that the box product of a Sidorenko graph with an edge is forcing, partially generalizing results of Kim, Lee, and Lee (2016) and, in particular, showing that cubes are forcing. We achieve these results through algebraic arguments building on Razborov's flag algebra framework (2007). This approach additionally allows us to construct Sidorenko hypergraphs from known 2-uniform Sidorenko graphs and to study forcing pairs.
Graham, R\"odl, and Ruci\'nski originally posed the problem of determining the minimum number of monochromatic Schur triples that must appear in any 2-coloring of the first $n$ integers. This question âŠ
Graham, R\"odl, and Ruci\'nski originally posed the problem of determining the minimum number of monochromatic Schur triples that must appear in any 2-coloring of the first $n$ integers. This question was subsequently resolved independently by Datskovsky, Schoen, and Robertson and Zeilberger. Here we suggest studying a natural anti-Ramsey variant of this question and establish the first non-trivial bounds by proving that the maximum fraction of Schur triples that can be rainbow in a given $3$-coloring of the first $n$ integers is at least $0.4$ and at most $0.66656$. We conjecture the lower bound to be tight. This question is also motivated by a famous analogous problem in graph theory due to Erd\H{o}s and S\'os regarding the maximum number of rainbow triangles in any $3$-coloring of $K_n$, which was settled by Balogh et al.
Abstract We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of ErdĆs. Most notably, we improve the upper âŠ
Abstract We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of ErdĆs. Most notably, we improve the upper bounds on the Ramsey multiplicity of $$K_4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>4</mml:mn> </mml:msub> </mml:math> and $$K_5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>5</mml:mn> </mml:msub> </mml:math> and settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic $$K_4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>4</mml:mn> </mml:msub> </mml:math> or $$K_5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mn>5</mml:mn> </mml:msub> </mml:math> in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a graph of constant size and were found through search heuristics. They are complemented by lower bounds established using flag algebras, resulting in a fully computer-assisted approach. For some of our theorems we can also derive that the extremal construction is stable in a very strong sense. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.
We provide an optimal sufficient condition, relating minimum degree and bandwidth, for a graph to contain a spanning subdivision of the complete bipartite graph $K_{2,\ell}$. This includes the containment of âŠ
We provide an optimal sufficient condition, relating minimum degree and bandwidth, for a graph to contain a spanning subdivision of the complete bipartite graph $K_{2,\ell}$. This includes the containment of Hamilton paths and cycles, and has applications in the random geometric graph model. Our proof provides a greedy algorithm for constructing such structures.
We show that a $k$-uniform hypergraph on $n$ vertices has a spanning subgraph homeomorphic to the $(k - 1)$-dimensional sphere provided that $H$ has no isolated vertices and each set âŠ
We show that a $k$-uniform hypergraph on $n$ vertices has a spanning subgraph homeomorphic to the $(k - 1)$-dimensional sphere provided that $H$ has no isolated vertices and each set of $k - 1$ vertices supported by an edge is contained in at least $n/2 + o(n)$ edges. This gives a topological extension of Dirac's theorem and asymptotically confirms a conjecture of Georgakopoulos, Haslegrave, Montgomery, and Narayanan. Unlike typical results in the area, our proof does not rely on the Absorption Method, the Regularity Lemma or the Blow-up Lemma. Instead, we use a recently introduced framework that is based on covering the vertex set of the host graph with a family of complete blow-ups.
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gammaâș0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform âŠ
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gammaâș0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform hypergraph \(G^{(k)}\big(n,n^{\gamma-1}\big)\) in which all \((k-1)\)-sets are contained in at least \(\big(\tfrac12+2\gamma\big)pn\) edges has a tight Hamilton cycle. This is a cyclic ordering of the \(n\) vertices such that each consecutive \(k\) vertices forms an edge.Mathematics Subject Classifications: 05C80, 05C35Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience
Abstract We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given , the union of any âvertex âŠ
Abstract We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given , the union of any âvertex graph with minimum degree and the binomial random graph . This is known when and we determine the exact perturbed threshold probability in all the remaining cases, that is, for each . We demonstrate that, as ranges over the interval , the threshold performs a countably infinite number of âjumpsâ. Our result has implications on the perturbed threshold for twoâuniversality, where we also fully address all open cases.
We study optimal minimum degree conditions when an n-vertex graph G contains an r-regular r-connected spanning subgraph. We prove for r fixed and n large the condition to be ÎŽ(G)â„n+râ22 âŠ
We study optimal minimum degree conditions when an n-vertex graph G contains an r-regular r-connected spanning subgraph. We prove for r fixed and n large the condition to be ÎŽ(G)â„n+râ22 when nrâĄ0(mod2). This answers a question of M. Kriesell.
Abstract Given a collection of hypergraphs with the same vertex set, an âedge graph is a transversal if there is a bijection such that for each . How large does âŠ
Abstract Given a collection of hypergraphs with the same vertex set, an âedge graph is a transversal if there is a bijection such that for each . How large does the minimum degree of each need to be so that necessarily contains a copy of that is a transversal? Each in the collection could be the same hypergraph, hence the minimum degree of each needs to be large enough to ensure that . Since its general introduction by Joos and Kim ( Bull. Lond. Math. Soc . 52 (2020) 498â504), a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Diracâtype results for (powers of) Hamilton cycles. For example, we derive that any collection of graphs on an âvertex set, each with minimum degree at least , contains a transversal copy of the th power of a Hamilton cycle. This can be viewed as a rainbow version of the PĂłsaâSeymour conjecture.
We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have âŠ
We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have so far lacked a computational counterpart to derive matching constructive bounds. We demonstrate that common search heuristics are capable of finding constructions far beyond the reach of human intuition. Additionally, the most obvious downside of such heuristics, namely a missing guarantee of global optimality, can often be fully eliminated in this case through lower bounds and stability results coming from the Flag Algebra approach. To illustrate the potential of this approach, we study two related and well-known problems in Extremal Graph Theory that go back to questions of ErdĆs from the 60s. Most notably, we present the first major improvement in the upper bound of the Ramsey multiplicity of K_4 in 25 years, precisely determine the first off-diagonal Ramsey multiplicity number, and settle the minimum number of independent sets of size four in graphs with clique number strictly less than five.
Given a collection of hypergraphs $\fH=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such âŠ
Given a collection of hypergraphs $\fH=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\fH$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $F\subseteq H_i$. Since its general introduction by Joos and Kim~[Bull. Lond. Math. Soc., 2020, 52(3): 498â504], a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. For example, we derive that any collection of $rn$ graphs on an $n$-vertex set, each with minimum degree at least $(r/(r+1)+o(1))n$, contains a transversal copy of the $r$-th power of a Hamilton cycle. This can be viewed as a rainbow version of the P\'osa-Seymour conjecture.
Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the âŠ
Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the size of the largest subset of $[n]$ such that there is a $k$-colouring avoiding a monochromatic $a+b=c$. In other directions, the minimum number of $a+b=c$ in $k$-colourings of $[n]$ and the probability threshold in random subsets of $[n]$ for the property of having a monochromatic $a+b=c$ in any $k$-colouring were investigated. In this paper, we study natural generalisations of these streams to products $ab=c$, in a deterministic, random, and randomly perturbed environments.
Abstract We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum âŠ
Abstract We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$ . We prove that asymptotically almost surely $G \cup G(n,p)$ contains at least $\min \{\delta (G), \lfloor n/3 \rfloor \}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$ , where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac. Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480â516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480â516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159â176], this fully resolves the existence of triangle factors in randomly perturbed graphs. We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and $2$ -universality.
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> âŠ
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k = n^{\theta }$ </tex-math></inline-formula> (with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\theta \in (0,1)$ </tex-math></inline-formula> ), with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> individuals among which <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula> of tests an individual can be placed in, or the maximum number <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Gamma $ </tex-math></inline-formula> of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula> -divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Gamma $ </tex-math></inline-formula> -sized tests, we provide a comprehensive analysis of the regime <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Gamma = \Theta (1)$ </tex-math></inline-formula> , and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.
We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $\alpha \in (0,1)$, the union of any âŠ
We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $\alpha \in (0,1)$, the union of any $n$-vertex graph with minimum degree $\alpha n$ and the binomial random graph $G(n,p)$. This is known when $\alpha > 1/2$, and we determine the exact perturbed threshold probability in all the remaining cases, i.e., for each $\alpha \le 1/2$. We demonstrate that, as $\alpha$ ranges over the interval $(0,1)$, the threshold performs a countably infinite number of `jumps'. Our result has implications on the perturbed threshold for $2$-universality, where we also fully address all open cases.
We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of Erd\H{o}s. Most notably, we improve the upper bounds âŠ
We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of Erd\H{o}s. Most notably, we improve the upper bounds on the Ramsey multiplicity of $K_4$ and $K_5$ and settle the minimum number of independent sets of size $4$ in graphs with clique number at most $4$. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic $K_4$ or $K_5$ in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a graph of constant size and were found through search heuristics. They are complemented by lower bounds established using flag algebras, resulting in a fully computer-assisted approach. For some of our theorems we can also derive that the extremal construction is stable in a very strong sense. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.
Given a collection of hypergraphs $\textbf{H}=(H_1,\ldots,H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in âŠ
Given a collection of hypergraphs $\textbf{H}=(H_1,\ldots,H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\textbf{H}$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $F\subseteq H_i$. Since its general introduction by Joos and Kim [Bull. Lond. Math. Soc., 2020, 52(3):498-504], a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. For example, we derive that any collection of $rn$ graphs on an $n$-vertex set, each with minimum degree at least $(r/(r+1)+o(1))n$, contains a transversal copy of the $r$-th power of a Hamilton cycle. This can be viewed as a rainbow version of the P\'osa-Seymour conjecture.
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge âŠ
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge \frac{n+r-2}{2}$ when $nr \equiv 0 \pmod 2$. This answers a question of M.~Kriesell.
Given a hypergraph $H$, the size-Ramsey number $\hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring âŠ
Given a hypergraph $H$, the size-Ramsey number $\hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $H$. We prove that the size-Ramsey number of the $3$-uniform tight path on $n$ vertices $P^{(3)}_n$ is linear in $n$, i.e., $\hat{r}_2(P^{(3)}_n) = O(n)$. This answers a question by Dudek, Fleur, Mubayi, and R\"odl for $3$-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved $\hat{r}_2(P^{(3)}_n) = O(n^{3/2} \log^{3/2} n)$.
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was âŠ
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by PĂłsa and Korshunov on the threshold in $\mathbb{G}(n,p)$. In this note we extend this result in $\mathcal{G}_\alpha\cup\mathbb{G}(n,p)$ to sparser graphs with $\alpha=o(1)$. More precisely, for any $\varepsilon>0$ and $\alpha \colon \mathbb{N} \mapsto (0,1)$ we show that a.a.s. $\mathcal{G}_\alpha\cup \mathbb{G}(n,\beta /n)$ is Hamiltonian, where $\beta = -(6 + \varepsilon) \log(\alpha)$. If $\alpha>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $\alpha=O(1/n)$ the random part $\mathbb{G}(n,p)$ is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into $\mathbb{G}(n,p)$.
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ âŠ
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ and the binomial random graph $G(n,p)$. For $\ell \ge 3$ we prove that asymptotically almost surely $G \cup G(n,p)$ contains $\min \{\delta(G), \lfloor n/\ell \rfloor \}$ pairwise vertex-disjoint cycles $C_\ell$, provided $p \ge C \log n/n$ for $C$ sufficiently large. Moreover, when $\delta(G) \ge\alpha n$ with $0 1/\ell$ for finding $\lfloor n/\ell \rfloor$ cycles $C_\ell$.
Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson--Kahn--Vu Theorem for $C_\ell$-factors and the resolution of the El-Zahar Conjecture for $C_\ell$-factors by Abbasi.
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any $Îł>0$ and $k\ge3$, we show that asymptotically almost surely, every subgraph of the binomial random $k$-uniform âŠ
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any $Îł>0$ and $k\ge3$, we show that asymptotically almost surely, every subgraph of the binomial random $k$-uniform hypergraph $G^{(k)}\big(n,n^{Îł-1}\big)$ in which all $(k-1)$-sets are contained in at least $\big(\tfrac12+2Îł\big)pn$ edges has a tight Hamilton cycle. This is a cyclic ordering of the $n$ vertices such that each consecutive $k$ vertices forms an edge.
We study the problem of finding pairwise vertex-disjoint copies of the â-vertex cycle Câ in the randomly perturbed graph model, which is the union of a deterministic n-vertex graph G âŠ
We study the problem of finding pairwise vertex-disjoint copies of the â-vertex cycle Câ in the randomly perturbed graph model, which is the union of a deterministic n-vertex graph G and the binomial random graph G(n, p). For â â„ 3 we prove that asymptotically almost surely G U G(n, p) contains min{ÎŽ(G), min{ÎŽ(G), [n/l]} pairwise vertex-disjoint cycles Câ, provided p â„ C log n/n for C sufficiently large. Moreover, when ÎŽ(G) ℠αn with 0 †α/l and G and is not 'close' to the complete bipartite graph Kαn,(1 - α)n, then p â„ C/n suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that p â„ C/n suffices when α > n/l for finding [n/l] cycles Câ. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson-Kahn-Vu Theorem for Câ-factors and the resolution of the El-Zahar Conjecture for Câ-factors by Abbasi.
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge âŠ
We study optimal minimum degree conditions when an $n$-vertex graph $G$ contains an $r$-regular $r$-connected subgraph. We prove for $r$ fixed and $n$ large the condition to be $\delta(G) \ge \frac{n+r-2}{2}$ when $nr \equiv 0 \pmod 2$. This answers a question of M.~Kriesell.
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ âŠ
We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_\ell$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ and the binomial random graph $G(n,p)$. For $\ell \ge 3$ we prove that asymptotically almost surely $G \cup G(n,p)$ contains $\min \{\delta(G), \lfloor n/\ell \rfloor \}$ pairwise vertex-disjoint cycles $C_\ell$, provided $p \ge C \log n/n$ for $C$ sufficiently large. Moreover, when $\delta(G) \ge\alpha n$ with $0<\alpha \le 1/\ell$ and $G$ is not `close' to the complete bipartite graph $K_{\alpha n,(1-\alpha) n}$, then $p \ge C/n$ suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that $p \ge C/n$ suffices when $\alpha>1/\ell$ for finding $\lfloor n/\ell \rfloor$ cycles $C_\ell$. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson--Kahn--Vu Theorem for $C_\ell$-factors and the resolution of the El-Zahar Conjecture for $C_\ell$-factors by Abbasi.
Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges with the âŠ
Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges with the property that, in any colouring of E ( G ) with s colours, there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex bounded degree tree is linear in n. As a corollary, we obtain that the s-colour size-Ramsey number of n-vertex graphs with bounded treewidth and bounded degree is linear in n, which answers a question raised by KamÄev, Liebenau, Wood and Yepremyan.
We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$-vertex graph $G$ with linear minimum degree and the âŠ
We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$-vertex graph $G$ with linear minimum degree and the binomial random graph $G(n,p)$. We prove that asymptotically almost surely $G \cup G(n,p)$ contains $\min \{\delta(G), \lfloor n/3 \rfloor \}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$, where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac. Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, to appear] in the case of triangle-factors. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159-176] this fully resolves the existence of triangle-factors in randomly perturbed graphs. We also prove a stability version of our result. Finally, we discuss further generalisations to larger clique-factors, larger cycle-factors, and $2$-universality.
Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from âŠ
Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game if she is able to occupy any winning set $F \in \mathcal{F}$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_\alpha$ with minimum degree at least $\alpha n$ and a binomial random graph $G_{n,p}$. Depending on $\alpha$ and Breaker's bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_{\alpha}\cup G_{n,p}$, and we discuss the $H$-game when $b=1$. Furthermore, we give optimal results for the Waiter-Client versions of all mentioned games.
Abstract In an r -uniform hypergraph on n vertices, a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges âŠ
Abstract In an r -uniform hypergraph on n vertices, a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of r vertices. We provide a first deterministic polynomial-time algorithm, which finds a.a.s. tight Hamilton cycles in random r -uniform hypergraphs with edge probability at least C log 3 n / n . Our result partially answers a question of Dudek and Frieze, who proved that tight Hamilton cycles exist already for p = Ï (1/ n ) for r = 3 and p = ( e + o (1))/ n for $r \ge 4$ using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Böttcher, Kohayakawa and Person, and Nenadov and Ć koriÄ, in various ways: the algorithm of Allen et al. is a randomized polynomial-time algorithm working for edge probabilities $p \ge {n^{ - 1 + \varepsilon}}$ , while the algorithm of Nenadov and Ć koriÄ is a randomized quasipolynomial-time algorithm working for edge probabilities $p \ge C\mathop {\log }\nolimits^8 n/n$ .
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{\longrightarrow} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending âŠ
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{\longrightarrow} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending a result of Nenadov, Person, Skoric and Steger [J. Combin. Theory Ser. B 124 (2017),1-38], we determine the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} C_\ell$ for cycles $C_\ell$ of any given length $\ell \geq 4$.
In the group testing problem one aims to infer a small set of $k$ infected individuals out of a large population of size $n$. At our disposal we have a âŠ
In the group testing problem one aims to infer a small set of $k$ infected individuals out of a large population of size $n$. At our disposal we have a testing scheme which allows us to test a group of individuals, such that the outcome of the test is positive, if and only if at least one infected individual is part of the test. All tests are carried out in parallel. The overall goal is to find a test design and an inference algorithm requiring as few tests as possible, such that the infected individuals can be identified with high probability. As most relevant during the outbreak of pandemic diseases (Wang et al., 2011), our analysis focusses on the so-called sublinear regime of group testing, where $k \sim n^\theta$. The optimal group testing schemes require a test-size of $\sim n/k$ and each individual has to take part in $\sim \log n$ tests (Coja-Oghlan et. al, 2019). In real world applications, like testing many individuals in a short period of time during the outbreak of epidemics, pooling in such a way is not possible due to dilution effects. Evidence of those effects is known for important applications like HIV (Wein, 1996) or COVID-19 (Seifried and Ciesek, 2020). Our main contribution is the analysis of a group testing model, where we restrict the individuals-per-test to be finite. We present an easy to implement scheme to pool individuals into tests under these natural restrictions coming with the efficient decoding algorithm DD and present simulations which suggest that the decoding procedure succeeds for moderate population sizes. Furthermore, we show that our pooling scheme requires the fewest tests as possible under all pooling schemes. Finally, we apply our methods to the finitely many tests-per-individuals setting, where we provide a full understanding of the random regular test-design in this model by building up on work of (Gandikota et al., 2016).
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was âŠ
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by Posa and Korsunov on the threshold in $\mathbb{G}(n,p)$. In this note we extend this result in $\mathcal{G}_\alpha \cup \mathbb{G}(n,p)$ to sparser graphs with $\alpha=o(1)$. More precisely, for any $\varepsilon>0$ and $\alpha \colon \mathbb{N} \mapsto (0,1)$ we show that a.a.s. $\mathcal{G}_\alpha \cup \mathbb{G}(n,\beta /n)$ is Hamiltonian, where $\beta = -(6 + \varepsilon) \log(\alpha)$. If $\alpha>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $\alpha=O(1/n)$ the random part $\mathbb{G}(n,p)$ is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into $\mathbb{G}(n,p)$.
We study the model G α âȘ G ( n , p ) of randomly perturbed dense graphs, where G α is any n-vertex graph with minimum degree at least âŠ
We study the model G α âȘ G ( n , p ) of randomly perturbed dense graphs, where G α is any n-vertex graph with minimum degree at least α n and G ( n , p ) is the binomial random graph. We introduce a general approach for studying the appearance of spanning subgraphs in this model using absorption. This approach yields simpler proofs of several known results. We also use it to derive the following two new results. For every α > 0 and Î â„ 5 , and every n-vertex graph F with maximum degree at most Î, we show that if p = Ï ( n â 2 / ( Î + 1 ) ) , then G α âȘ G ( n , p ) with high probability contains a copy of F. The bound used for p here is lower by a log -factor in comparison to the conjectured threshold for the general appearance of such subgraphs in G ( n , p ) alone, a typical feature of previous results concerning randomly perturbed dense graphs. We also give the first example of graphs where the appearance threshold in G α âȘ G ( n , p ) is lower than the appearance threshold in G ( n , p ) by substantially more than a log -factor. We prove that, for every k â„ 2 and α > 0 , there is some η > 0 for which the kth power of a Hamilton cycle with high probability appears in G α âȘ G ( n , p ) when p = Ï ( n â 1 / k â η ) . The appearance threshold of the kth power of a Hamilton cycle in G ( n , p ) alone is known to be n â 1 / k , up to a log -term when k = 2 , and exactly for k > 2 .
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta}$ âŠ
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta}$ (with $\theta \in (0,1)$), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $\Delta$ of tests an individual can be placed in, or the maximum number $\Gamma$ of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $\Delta$-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of $\eul$ more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of $\Gamma$-sized tests, we provide a comprehensive analysis of the regime $\Gamma = \Theta(1)$, and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{{\longrightarrow}} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending âŠ
For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{{\longrightarrow}} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending a result of Nenadov, Person, \v{S}kori\'{c} and Steger [J. Combin. Theory Ser. B 124 (2017),1-38], we determine the threshold for $G(n,p) \overset{\mathrm{rb}}{{\longrightarrow}} C_\ell$ for cycles $C_\ell$ of any given length $\ell \geq 4$.
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was âŠ
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by Pos\'{a} and Kor\v{s}unov on the threshold in $\mathbb{G}(n,p)$. In this note we extend this result in $\mathcal{G}_\alpha \cup \mathbb{G}(n,p)$ to sparser graphs with $\alpha=o(1)$. More precisely, for any $\varepsilon>0$ and $\alpha \colon \mathbb{N} \mapsto (0,1)$ we show that a.a.s. $\mathcal{G}_\alpha \cup \mathbb{G}(n,\beta /n)$ is Hamiltonian, where $\beta = -(6 + \varepsilon) \log(\alpha)$. If $\alpha>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $\alpha=O(1/n)$ the random part $\mathbb{G}(n,p)$ is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into $\mathbb{G}(n,p)$.
Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from âŠ
Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game if she is able to occupy any winning set $F \in \mathcal{F}$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_\alpha$ with minimum degree at least $\alpha n$ and a binomial random graph $G_{n,p}$. Depending on $\alpha$ and Breaker's bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_{\alpha}\cup G_{n,p}$, and we discuss the $H$-game when $b=1$. Furthermore, we give optimal results for the Waiter-Client versions of all mentioned games.
We introduce and study a novel semiârandom multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex âŠ
We introduce and study a novel semiârandom multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v . For various natural monotone increasing graph properties , we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies . Along the way, we show that the process is general enough to approximate (using suitable strategies) several wellâstudied random graph models.
For graphs G and H, let Gâ¶prbH denote the property that for every proper edge colouring of G there is a rainbow copy of H in G. Extending a result âŠ
For graphs G and H, let Gâ¶prbH denote the property that for every proper edge colouring of G there is a rainbow copy of H in G. Extending a result of Nenadov, Person, Ć koriÄ and Steger (2017), we prove that nâ1/m2(Câ) is the threshold for G(n,p)â¶prbCâ when â â„ 5. Thus our result together with a result of the third author which says that the threshold for Gâ¶prbC4 is nâ3/4 settles the problem of determining the threshold for Gâ¶prbCâ for all values of â.
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is âŠ
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is quasirandom; such pairs (H_1,H_2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), 1-38]: they showed that (K_t,F) is forcing where F is the graph that arises from K_t by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma 7, 2019] strengthened this result for t=3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t>3. We show that (t+2)/2 doublings always suffice.
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is âŠ
We study pairs of graphs (H_1,H_2) such that every graph with the densities of H_1 and H_2 close to the densities of H_1 and H_2 in a random graph is quasirandom; such pairs (H_1,H_2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40 (2012), 1-38]: they showed that (K_t,F) is forcing where F is the graph that arises from K_t by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma 7, 2019] strengthened this result for t=3 by proving that two doublings suffice and asked for the minimum number of doublings needed for t>3. We show that (t+2)/2 doublings always suffice.
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More âŠ
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G α on n vertices with ÎŽ ( G α ) ℠αn for α > 0 and we add to it the binomial random graph G ( n , C / n ), then with high probability the graph G α âȘ G ( n , C / n ) contains copies of all spanning trees with maximum degree at most Î simultaneously, where C depends only on α and Î.
A graph $G$ is called universal for a family of graphs $\mathcal{F}$ if it contains every element $F \in \mathcal{F}$ as a subgraph. Let $\mathcal{F}(n,2)$ be the family of all âŠ
A graph $G$ is called universal for a family of graphs $\mathcal{F}$ if it contains every element $F \in \mathcal{F}$ as a subgraph. Let $\mathcal{F}(n,2)$ be the family of all graphs with maximum degree $2$. Ferber, Kronenberg, and Luh [Optimal Threshold for a Random Graph to be 2-Universal, to appear in Transactions of the American Mathematical Society] proved that there exists a $C$ such that for $p \ge C (n^{-2/3} \log^{1/3} n )$ the random graph $G(n,p)$ a.a.s is $\mathcal{F}(n,2)$-universal, which is asymptotically optimal. For any $n$-vertex graph $G_\alpha$ with minimum degree $\delta(G_\alpha) \ge \alpha n$ Aigner and Brandt [Embedding arbitrary graphs of maximum degree two, Journal of the London Mathematical Society 48 (1993), 39-51] proved that $G_\alpha$ is $\mathcal{F}(n,2)$-universal for an optimal $\alpha \ge 2/3$.
In this note, we consider the model of randomly perturbed graphs, which is the union $G_\alpha \cup G(n,p)$. We prove that $G_\alpha \cup G(n,p)$ is a.a.s. $\mathcal{F}(n,2)$-universal provided that $\alpha>0$ and $p=\omega(n^{-2/3})$. This is asymptotically optimal and improves on both results from above in the respective parameter. Furthermore, this extends a result of Bottcher, Montgomery, Parczyk, and Person [Embedding spanning bounded degree subgraphs in randomly perturbed graphs, arXiv:1802.04603 (2018)], who embed a given $F \in \mathcal{F}(n,2)$ at these values. We also prove variants with universality for the family $\mathcal{F}^\ell(n,2)$, all graphs from $\mathcal{F}(n,2)$ with girth at least $\ell$. For example, there exists an $\ell_0$ depending only on $\alpha$ such that for all $\ell \ge \ell_0$ already $p=\omega(1/n)$ is sufficient for $\mathcal{F}^\ell(n,2)$-universality.
Let G p be a random graph on 2 d vertices where edges are selected independently with a fixed probability p > ÂŒ, and let H be the d -dimensional âŠ
Let G p be a random graph on 2 d vertices where edges are selected independently with a fixed probability p > ÂŒ, and let H be the d -dimensional hypercube Q d . We answer a question of BollobĂĄs by showing that, as d â â, G p almost surely has a spanning subgraph isomorphic to H . In fact we prove a stronger result which implies that the number of d -cubes in G â [Gscr ]( n , M ) is asymptotically normally distributed for M in a certain range. The result proved can be applied to many other graphs, also improving previous results for the lattice, that is, the 2-dimensional square grid. The proof uses the second moment method â writing X for the number of subgraphs of G isomorphic to H , where G is a suitable random graph, we expand the variance of X as a sum over all subgraphs of H itself. As the subgraphs of H may be quite complicated, most of the work is in estimating the various terms of this sum.
We show that for any fixed dense graph $G$ and bounded-degree tree $T$ on the same number of vertices, a modest random perturbation of $G$ will typically contain a copy âŠ
We show that for any fixed dense graph $G$ and bounded-degree tree $T$ on the same number of vertices, a modest random perturbation of $G$ will typically contain a copy of $T$. This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizable body of existing research on randomly perturbed graphs. Specifically, we show that there is $c=c(\alpha,\Delta)$ such that if $G$ is an $n$-vertex graph with minimum degree at least $\alpha n$, and $T$ is an $n$-vertex tree with maximum degree at most $\Delta$, then if we add $cn$ uniformly random edges to $G$, the resulting graph will contain $T$ asymptotically almost surely (as $n\to\infty$). Our proof uses a lemma concerning the decomposition of a dense graph into superregular pairs of comparable sizes, which may be of independent interest.
We prove that if a tree $T$ has $n$ vertices and maximum degree at most $Î$, then a copy of $T$ can almost surely be found in the random graph âŠ
We prove that if a tree $T$ has $n$ vertices and maximum degree at most $Î$, then a copy of $T$ can almost surely be found in the random graph $\mathcal{G}(n,Î\log^5 n/n)$.
In the random hypergraph $H=H_{n,p;3}$ each possible triple appears independently with probability $p$. A loose Hamilton cycle can be described as a sequence of edges $\{x_i,y_i,x_{i+1}\}$ for $i=1,2,\ldots,n/2$ where $x_1,x_2,\ldots,x_{n/2},y_1,y_2,\ldots,y_{n/2}$ âŠ
In the random hypergraph $H=H_{n,p;3}$ each possible triple appears independently with probability $p$. A loose Hamilton cycle can be described as a sequence of edges $\{x_i,y_i,x_{i+1}\}$ for $i=1,2,\ldots,n/2$ where $x_1,x_2,\ldots,x_{n/2},y_1,y_2,\ldots,y_{n/2}$ are all distinct. We prove that there exists an absolute constant $K>0$ such that if $p\geq {K\log n\over n^2}$ then $$\lim_{\textstyle{n\to \infty\atop 4|n}}\Pr(H_{n,p;3}\ contains\ a\ loose\ Hamilton\ cycle)=1.$$
In the random $k$-uniform hypergraph $H_{n,p;k}$ of order $n$ each possible $k$-tuple appears independently with probability $p$. A loose Hamilton cycle is a cycle of order $n$ in which every âŠ
In the random $k$-uniform hypergraph $H_{n,p;k}$ of order $n$ each possible $k$-tuple appears independently with probability $p$. A loose Hamilton cycle is a cycle of order $n$ in which every pair of adjacent edges intersects in a single vertex. We prove that if $p n^{k-1}/\log n$ tends to infinity with $n$ then $$\lim_{\substack{n\to \infty\\ 2(k-1) |n}}\Pr(H_{n,p;k}\text{ contains a loose Hamilton cycle})=1.$$ This is asymptotically best possible.
We prove that for integers $2 \leqslant \ell < k$ and a small constant $c$, if a $k$-uniform hypergraph with linear minimum codegree is randomly 'perturbed' by changing non-edges to âŠ
We prove that for integers $2 \leqslant \ell < k$ and a small constant $c$, if a $k$-uniform hypergraph with linear minimum codegree is randomly 'perturbed' by changing non-edges to edges independently at random with probability $p \geqslant O(n^{-(k-\ell)-c})$, then with high probability the resulting $k$-uniform hypergraph contains a Hamilton $\ell$-cycle. This complements a recent analogous result for Hamilton $1$-cycles due to Krivelevich, Kwan and Sudakov, and a comparable theorem in the graph case due to Bohman, Frieze and Martin.
In this paper we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $\Delta\geq 5$, $\varepsilon > 0$ and let $H$ be a âŠ
In this paper we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $\Delta\geq 5$, $\varepsilon > 0$ and let $H$ be a graph on $(1-\varepsilon)n$ vertices and with maximum degree $\Delta$. We show that a random graph $G_{n,p}$ with high probability contains a copy of $H$, provided that $p\gg (n^{-1}\log^{1/\Delta}n)^{2/(\Delta+1)}$. Our assumption on $p$ is optimal up to the $polylog$ factor. We note that this $polylog$ term matches the conjectured threshold for the spanning case.
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has âŠ
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics. We prove sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs. Our main results are the following three sparse versions of the blow-up lemma: one for embedding spanning graphs with maximum degree $Î$ in subgraphs of $G(n,p)$ with $p=C(\log n/n)^{1/Î}$; one for embedding spanning graphs with maximum degree $Î$ and degeneracy $D$ in subgraphs of $G(n,p)$ with $p=C_Î\big(\log n/n\big)^{1/(2D+1)}$; and one for embedding spanning graphs with maximum degree $Î$ in $(p,cp^{\max(4,(3Î+1)/2)}n)$-bijumbled graphs. We also consider various applications of these lemmas.
For k â„ 2 and r â„ 1 such that k + r â„ 4, we prove that, for any α > 0, there exists Δ > 0 such that âŠ
For k â„ 2 and r â„ 1 such that k + r â„ 4, we prove that, for any α > 0, there exists Δ > 0 such that the union of an n âvertex k âgraph with minimum codegree and a binomial random k âgraph with on the same vertex set contains the r th power of a tight Hamilton cycle with high probability. This result for r = 1 was first proved by McDowell and Mycroft.
Abstract We show that for every there exists C > 0 such that if then asymptotically almost surely the random graph contains the k th power of a Hamilton cycle. âŠ
Abstract We show that for every there exists C > 0 such that if then asymptotically almost surely the random graph contains the k 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ĂŒhn 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 for . The proofs are based on the absorbing method and follow the strategy of KĂŒhn 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.
We study the model G α âȘ G ( n , p ) of randomly perturbed dense graphs, where G α is any n-vertex graph with minimum degree at least âŠ
We study the model G α âȘ G ( n , p ) of randomly perturbed dense graphs, where G α is any n-vertex graph with minimum degree at least α n and G ( n , p ) is the binomial random graph. We introduce a general approach for studying the appearance of spanning subgraphs in this model using absorption. This approach yields simpler proofs of several known results. We also use it to derive the following two new results. For every α > 0 and Î â„ 5 , and every n-vertex graph F with maximum degree at most Î, we show that if p = Ï ( n â 2 / ( Î + 1 ) ) , then G α âȘ G ( n , p ) with high probability contains a copy of F. The bound used for p here is lower by a log -factor in comparison to the conjectured threshold for the general appearance of such subgraphs in G ( n , p ) alone, a typical feature of previous results concerning randomly perturbed dense graphs. We also give the first example of graphs where the appearance threshold in G α âȘ G ( n , p ) is lower than the appearance threshold in G ( n , p ) by substantially more than a log -factor. We prove that, for every k â„ 2 and α > 0 , there is some η > 0 for which the kth power of a Hamilton cycle with high probability appears in G α âȘ G ( n , p ) when p = Ï ( n â 1 / k â η ) . The appearance threshold of the kth power of a Hamilton cycle in G ( n , p ) alone is known to be n â 1 / k , up to a log -term when k = 2 , and exactly for k > 2 .
For integers $k\ge 3$ and $1\le \ell\le k-1$, we prove that for any $\alpha>0$, there exist $\epsilon>0$ and $C>0$ such that for sufficiently large $n\in (k-\ell)\mathbb{N}$, the union of a âŠ
For integers $k\ge 3$ and $1\le \ell\le k-1$, we prove that for any $\alpha>0$, there exist $\epsilon>0$ and $C>0$ such that for sufficiently large $n\in (k-\ell)\mathbb{N}$, the union of a $k$-uniform hypergraph with minimum vertex degree $\alpha n^{k-1}$ and a binomial random $k$-uniform hypergraph $\mathbb{G}^{(k)}(n,p)$ with $p\ge n^{-(k-\ell)-\epsilon}$ for $\ell\ge 2$ and $p\ge C n^{-(k-1)}$ for $\ell=1$ on the same vertex set contains a Hamiltonian $\ell$-cycle with high probability. Our result is best possible up to the values of $\epsilon$ and $C$ and answers a question of Krivelevich, Kwan and Sudakov.
Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 3 April 2019Accepted: 16 October 2020Published online: 17 May 2021Keywordsextremal graph theory, random âŠ
Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 3 April 2019Accepted: 16 October 2020Published online: 17 May 2021Keywordsextremal graph theory, random graphs, HamiltonicityAMS Subject Headings05C35, 05C80Publication DataISSN (print): 0895-4801ISSN (online): 1095-7146Publisher: Society for Industrial and Applied MathematicsCODEN: sjdmec
Abstract We prove that there exist graphs G with arbitrarily large girth such that every proper edge coloring of G contains a rainbow cycle (i.e., a cycle having no pair âŠ
Abstract We prove that there exist graphs G with arbitrarily large girth such that every proper edge coloring of G contains a rainbow cycle (i.e., a cycle having no pair of monochromatic edges). This answers a problem raised by J. Spencer more than 10 years ago.
Given graphs $H_1,H_2$, a graph $G$ is $(H_1,H_2)$-Ramsey if for every colouring of the edges of $G$ with red and blue, there is a red copy of $H_1$ or a âŠ
Given graphs $H_1,H_2$, a graph $G$ is $(H_1,H_2)$-Ramsey if for every colouring of the edges of $G$ with red and blue, there is a red copy of $H_1$ or a blue copy of $H_2$. In this paper we investigate Ramsey questions in the setting of randomly perturbed graphs: this is a random graph model introduced by Bohman, Frieze and Martin in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali in 2006; they determined how many random edges must be added to a dense graph to ensure the resulting graph is with high probability $(K_3,K_t)$-Ramsey (for $t\ge 3$). They also raised the question of generalising this result to pairs of graphs other than $(K_3,K_t)$. We make significant progress on this question, giving a precise solution in the case when $H_1=K_s$ and $H_2=K_t$ where $s,t \ge 5$. Although we again show that one requires polynomially fewer edges than in the purely random graph, our result shows that the problem in this case is quite different to the $(K_3,K_t)$-Ramsey question. Moreover, we give bounds for the corresponding $(K_4,K_t)$-Ramsey question; together with a construction of Powierski this resolves the $(K_4,K_4)$-Ramsey problem. We also give a precise solution to the analogous question in the case when both $H_1=C_s$ and $H_2=C_t$ are cycles. Additionally we consider the corresponding multicolour problem. Our final result gives another generalisation of the Krivelevich, Sudakov and Tetali result. Specifically, we determine how many random edges must be added to a dense graph to ensure the resulting graph is with high probability $(C_s,K_t)$-Ramsey (for odd $s\ge 5$ and $t\ge 4$).
A {\it weak (Berge) cycle} is an alternating sequence of vertices and (hyper)edges $C=(v_0, e_1, v_1, ..., v_{\ell-1}, e_\ell, v_{\ell}=v_0)$ such that the vertices $v_0, ..., v_{\ell-1}$ are distinct with âŠ
A {\it weak (Berge) cycle} is an alternating sequence of vertices and (hyper)edges $C=(v_0, e_1, v_1, ..., v_{\ell-1}, e_\ell, v_{\ell}=v_0)$ such that the vertices $v_0, ..., v_{\ell-1}$ are distinct with $v_k, v_{k+1} \in e_{k}$ for each $k$, but the edges $e_1, ..., e_\ell$ are not necessarily distinct. We prove that the main barrier to the random $d$-uniform hypergraph $H_d(n,p),$ where each of the potential edges of cardinality $d$ is present with probability $p$, developing a weak Hamilton cycle is the presence of isolated vertices. In particular, for $d \geq 3$ fixed and $p=(d-1)! \frac{\ln n + c}{n^{d-1}}$, the probability that $H_d(n, p)$ has a weak Hamilton cycle tends to $e^{-e^{-c}}$, which is also the limiting probability that $H_d(n,p)$ has no isolated vertices. As a consequence, the probability that the random hypergraph $H_d(n, m=\frac{n(\ln n + c)}{d}),$ where $m$ potential edges are chosen uniformly at random to be present, is weak Hamiltonian also tends to $e^{-e^{-c}}$.
From social networks such as Facebook, the World Wide Web and the Internet, to the complex interactions between proteins in the cells of our bodies, we constantly face the challenge âŠ
From social networks such as Facebook, the World Wide Web and the Internet, to the complex interactions between proteins in the cells of our bodies, we constantly face the challenge of understanding the structure and development of networks. The theory of random graphs provides a framework for this understanding, and in this book the authors give a gentle introduction to the basic tools for understanding and applying the theory. Part I includes sufficient material, including exercises, for a one semester course at the advanced undergraduate or beginning graduate level. The reader is then well prepared for the more advanced topics in Parts II and III. A final part provides a quick introduction to the background material needed. All those interested in discrete mathematics, computer science or applied probability and their applications will find this an ideal introduction to the subject.
For graphs G and H, let Gâ¶prbH denote the property that, for every proper edge-colouring of G (with an arbitrary number of colours) there is a totally multicoloured, or rainbow, âŠ
For graphs G and H, let Gâ¶prbH denote the property that, for every proper edge-colouring of G (with an arbitrary number of colours) there is a totally multicoloured, or rainbow, copy of H in G, that is, a copy of H with no two edges of the same colour. We consider the problem of establishing the threshold pHrb=pHrb(n) of this property for the binomial random graph G(n,p). More specifically, we give an upper bound for pHrb and we extend our result to certain locally bounded colourings that generalize proper colourings. Our method is heavily based on a characterization of sparse quasi-randomness given by Chung and Graham (2008).
Abstract A graph is said to be âuniversal if it contains every graph with n vertices and maximum degree at most Î as a subgraph. Dellamonica, Kohayakawa, Rödl and RuciĆski âŠ
Abstract A graph is said to be âuniversal if it contains every graph with n vertices and maximum degree at most Î as a subgraph. Dellamonica, Kohayakawa, Rödl and RuciĆski used a âmatchingâbasedâ embedding technique introduced by Alon and FĂŒredi to show that the random graph is asymptotically almost surely âuniversal for , a threshold for the property that every subset of Î vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Î in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that is almost surely âuniversal for .
Abstract For graphs G and H , let denote the property that for every proper edgeâcoloring of G (with an arbitrary number of colors) there is a rainbow copy of âŠ
Abstract For graphs G and H , let denote the property that for every proper edgeâcoloring of G (with an arbitrary number of colors) there is a rainbow copy of H in G , that is, a copy of H with no two edges of the same color. The authors (2014) proved that, for every graph H , the threshold function of this property for the binomial random graph is asymptotically at most , where denotes the soâcalled maximum 2âdensity of H . Nenadov et al. (2014) proved that if H is a cycle with at least seven vertices or a complete graph with at least 19 vertices, then . We show that there exists a fairly rich, infinite family of graphs F containing a triangle such that if for suitable constants and , where , then almost surely. In particular, for any such graph F .
What conditions ensure that a graph G contains some given spanning subgraph H? The most famous examples of results of this kind are probably Dirac's theorem on Hamilton cycles and âŠ
What conditions ensure that a graph G contains some given spanning subgraph H? The most famous examples of results of this kind are probably Dirac's theorem on Hamilton cycles and Tutte's theorem on perfect matchings. Perfect matchings are generalized by perfect F-packings, where instead of covering all the vertices of G by disjoint edges, we want to cover G by disjoint copies of a (small) graph F. It is unlikely that there is a characterization of all graphs G which contain a perfect F-packing, so as in the case of Dirac's theorem it makes sense to study conditions on the minimum degree of G which guarantee a perfect F-packing.
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More âŠ
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G α on n vertices with ÎŽ ( G α ) ℠αn for α > 0 and we add to it the binomial random graph G ( n , C / n ), then with high probability the graph G α âȘ G ( n , C / n ) contains copies of all spanning trees with maximum degree at most Î simultaneously, where C depends only on α and Î.
For $k\ge 2$ and $r\ge 1$ such that $k+r\ge 4$, we prove that, for any $\alpha>0$, there exists $\epsilon>0$ such that the union of an $n$-vertex $k$-graph with minimum codegree âŠ
For $k\ge 2$ and $r\ge 1$ such that $k+r\ge 4$, we prove that, for any $\alpha>0$, there exists $\epsilon>0$ such that the union of an $n$-vertex $k$-graph with minimum codegree $\left(1-\binom{k+r-2}{k-1}^{-1}+\alpha\right)n$ and a binomial random $k$-graph $\mathbb{G}^{(k)}(n,p)$ with $p\ge n^{-\binom{k+r-2}{k-1}^{-1}-\epsilon}$ on the same vertex set contains the $r^{\text{th}}$ power of a tight Hamilton cycle with high probability. This result for $r=1$ was first proved by McDowell and Mycroft.
For each $\Delta>0$, we prove that there exists some $C=C(\Delta)$ for which the binomial random graph $G(n,C\log n/n)$ almost surely contains a copy of every tree with $n$ vertices and âŠ
For each $\Delta>0$, we prove that there exists some $C=C(\Delta)$ for which the binomial random graph $G(n,C\log n/n)$ almost surely contains a copy of every tree with $n$ vertices and maximum degree at most $\Delta$. In doing so, we confirm a conjecture by Kahn.