Search

A graph is said to be H(n,Δ) ‐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 Gn,p is asymptotically almost surely H(n,Δ) ‐universal for p=Ω((logn/n)1/Δ), 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 Gn,p is almost surely H(n,Δ) ‐universal for p=Ω(n−1/(Δ−0.5)log3n). [ABSTRACT FROM AUTHOR]

Let D(n,p) be the random directed graph on n vertices where each of the n(n−1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if p≥(logn+ω(1))/n then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically n!(p(1+o(1)))n. We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typically n!(logn/n(1+o(1)))n directed Hamilton cycles. [ABSTRACT FROM AUTHOR]

A subset C of edges in a k-uniform hypergraph H is a loose Hamilton cycle if C covers all the vertices of H and there exists a cyclic ordering of these vertices such that the edges in C are segments of that order and such that every two consecutive edges share exactly one vertex. The binomial random k-uniform hypergraph Hkn,p has vertex set [n] and an edge set E obtained by adding each k-tuple e ∈ ($\binom{[n]}{k}$) to E with probability p, independently at random.Here we consider the problem of finding edge-disjoint loose Hamilton cycles covering all but o(|E|) edges, referred to as the packing problem. While it is known that the threshold probability of the appearance of a loose Hamilton cycle in Hkn,p is $p=\Theta\biggl(\frac{\log n}{n^{k-1}}\biggr),$ the best known bounds for the packing problem are around p = polylog(n)/n. Here we make substantial progress and prove the following asymptotically (up to a polylog(n) factor) best possible result: for p ≥ logCn/nk−1, a random k-uniform hypergraph Hkn,p with high probability contains $N:=(1-o(1))\frac{\binom{n}{k}p}{n/(k-1)}$ edge-disjoint loose Hamilton cycles.Our proof utilizes and modifies the idea of ‘online sprinkling’ recently introduced by Vu and the first author. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let [ABSTRACT FROM AUTHOR]

In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of G(n, p). Let the maximum density of a graph H be the maximum average degree of all the subgraphs of H. First, we show that for p = ω(Δ12n-1/2d log³ n), a graph G ~ G(n, p) w.h.p. contains copies of all spanning graphs H with maximum degree at most Δ and maximum density at most d. For d < Δ/2, this improves a result of Dellamonica, Kohayakawa, Rödl and Ruci´ncki. Next, we show that if we additionally restrict the spanning graphs to have girth at least 7 then the random graph contains w.h.p. all such graphs for p = ω(Δ12n-1/2 log³n). In particular, if p = ω(ω12n-1/2 log³ n), the random graph therefore contains w.h.p. every spanning tree with maximum degree bounded by Δ. This improves a result of Johannsen, Krivelevich and Samotij. Finally, in the same spirit, we show that for any spanning graph H with constant maximum degree, and for suitable p, if we randomly color the edges of a graph G ~ G(n, p) with (1 + o(1))|E(H)| colors, then w.h.p. there exists a rainbow copy of H in G (that is, a copy of H with all edges colored with distinct colors). [ABSTRACT FROM AUTHOR]

We prove that every graph G on n vertices with no isolated vertices contains an induced subgraph of size at least n / 10000 with all degrees odd. This solves an old and well-known conjecture in graph theory. [ABSTRACT FROM AUTHOR]

For a tree T on n vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on n vertices, which Maker wins as soon as the graph she builds contains a copy of T. We prove that if T has bounded maximum degree and n is sufficiently large, then Maker can win this game within n + 1 moves. Moreover, we prove that Maker can build almost every tree on n vertices in n-1 moves and provide nontrivial examples of families of trees which Maker cannot build in n - 1 moves. [ABSTRACT FROM AUTHOR]

Abstract: For a positive integer , we consider the -vertex-connectivity game, played on the edge set of , the complete graph on vertices. We first study the Maker–Breaker version of this game and prove that, for any integer and sufficiently large , Maker has a strategy to win this game within moves, which is easily seen to be best possible. This answers a question from Hefetz et al. (2009) [6]. We then consider the strong -vertex-connectivity game. For every positive integer and sufficiently large , we describe an explicit first player’s winning strategy for this game. [Copyright &y& Elsevier]

Abstract: We analyze Avoider–Enforcer games played on edge disjoint hypergraphs, providing an analog of the classic and well known game Box, due to Chvátal and Erdős. We consider both strict and monotone versions of Avoider–Enforcer games, and for each version we give a sufficient condition to win for each player. We also present applications of our results to several general Avoider–Enforcer games. [Copyright &y& Elsevier]