Monochromatic paths in random tournaments

We prove that, with high probability, any 2‐edge‐coloring of a random tournament on n vertices contains a monochromatic path of length . This resolves a conjecture of Ben‐Eliezer, Krivelevich, and Sudakov and implies a nearly tight upper bound on the oriented size Ramsey number of a directed path.     

Self‐destructive percolation as a limit of forest‐fire models on regular rooted trees

Let T be a regular rooted tree. For every natural number n, let T_n be the finite subtree of vertices with graph distance at most n from the root. Consider the following forest‐fire model on T_n: Each vertex can be “vacant” or “occupied”. At time 0 all vertices are vacant. Then the process is governed by two opposing mechanisms: Vertices become occupied at rate 1, independently for all vertices. Independently thereof and independently for all vertices, “lightning” hits vertices at rate λ(n) > 0. When a vertex is hit by lightning, its occupied cluster becomes vacant instantaneously. Now suppose that λ(n) decays exponentially in n but much more slowly than 1/|T_n|, where |T_n| denotes the number of vertices of T_n. We show that then there exist such that between time 0 and time the forest‐fire model on T_n tends to the following process on T as n goes to infinity: At time 0 all vertices are vacant. Between time 0 and time τ vertices become occupied at rate 1, independently for all vertices. Immediately before time τ there are infinitely many infinite occupied clusters. At time τ all these clusters become vacant. Between time τ and time vertices again become occupied at rate 1, independently for all vertices. At time all occupied clusters are finite. This process is a dynamic version of self‐destructive percolation. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 86–113, 2017     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

On MAXCUT in strictly supercritical random graphs,and coloring of random graphs and random tournaments

We use a theorem by Ding, Lubetzky, and Peres describing the structure of the giant component of random graphs in the strictly supercritical regime, in order to determine the typical size of MAXCUT of in terms of ɛ. We then apply this result to prove the following conjecture by Frieze and Pegden. For every , there exists such that w.h.p. is not homomorphic to the cycle on vertices. We also consider the coloring properties of biased random tournaments. A p‐random tournament on n vertices is obtained from the transitive tournament by reversing each edge independently with probability p. We show that for the chromatic number of a p‐random tournament behaves similarly to that of a random graph with the same edge probability. To treat the case we use the aforementioned result on MAXCUT and show that in fact w.h.p. one needs to reverse edges to make it 2‐colorable.     

Cycle Transversals in Tournaments with Few Vertex Disjoint Cycles

We prove that every tournament T with no three disjoint cycles contains a set X of at most four vertices such that is acyclic.     

Spanning trees in randomly perturbed graphs

A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph G_α with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in G_α with high probability after adding O(n) randomly chosen edges to G_α. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ.     

Invariant Gaussian processes and independent sets on regular graphs of large girth

We prove that every 3‐regular, n‐vertex simple graph with sufficiently large girth contains an independent set of size at least 0.4361n. (The best known bound is 0.4352n.) In fact, computer simulation suggests that the bound our method provides is about 0.438n. Our method uses invariant Gaussian processes on the d‐regular tree that satisfy the eigenvector equation at each vertex for a certain eigenvalue . We show that such processes can be approximated by i.i.d. factors provided that . We then use these approximations for to produce factor of i.i.d. independent sets on regular trees. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 284–303, 2015     

An approximate version of Sumner?s universal tournament conjecture

Sumner?s universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.     

Almost all trees are almost graceful

The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labeled by using the numbers {1,2,…,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove the following relaxation of the conjecture for each γ>0 and for all n>n₀(γ). Suppose that (i) the maximum degree of T is bounded by ), and (ii) the vertex labels are chosen from the set {1,2,…,?(1+γ)n?}. Then there is an injective labeling of V(T) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on n vertices admit such a labeling. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labeling with high probability.     

Upper bounds on probability thresholds for asymmetric Ramsey properties

Given two graphs G and H, we investigate for which functions the random graph (the binomial random graph on n vertices with edge probability p) satisfies with probability that every red‐blue‐coloring of its edges contains a red copy of G or a blue copy of H. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which G and H are complete graphs of arbitrary size. In our proof we present an alternative to the so‐called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case G = H), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014     

Generating random graphs in biased Maker‐Breaker games

We present a general approach connecting biased Maker‐Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker‐Breaker games. In particular, we show that for , Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a game on . As another application, we show that for , playing a game on , Maker can build a graph which contains copies of all spanning trees having maximum degree with a bare path of linear length (a bare path in a tree T is a path with all interior vertices of degree exactly two in T). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 615–634, 2015     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

Random directed graphs are robustly Hamiltonian

A classical theorem of Ghouila‐Houri from 1960 asserts that every directed graph on n vertices with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph , that is, a directed graph in which every ordered pair (u, v) becomes an arc with probability p independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if , then a.a.s. every subdigraph of with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. The constant 1/2 is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 345–362, 2016     

On giant components and treewidth in the layers model

Given an undirected n‐vertex graph G(V, E) and an integer k, let T_k(G) denote the random vertex induced subgraph of G generated by ordering V according to a random permutation π and including in T_k(G) those vertices with at most k – 1 of their neighbors preceding them in this order. The distribution of subgraphs sampled in this manner is called the layers model with parameter k. The layers model has found applications in studying ?‐degenerate subgraphs, the design of algorithms for the maximum independent set problem, and in bootstrap percolation. In the current work we expand the study of structural properties of the layers model. We prove that there are 3‐regular graphs G for which with high probability T₃(G) has a connected component of size , and moreover, T₃(G) has treewidth . In contrast, T₂(G) is known to be a forest (hence of treewidth 1), and we prove that if G is of bounded degree then with high probability the largest connected component in T₂(G) is of size . We also consider the infinite grid , for which we prove that contains a unique infinite connected component with probability 1. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 524–545, 2016     

Stochastic domination in space‐time for the contact process

Liggett and Steif (2006) proved that, for the supercritical contact process on certain graphs, the upper invariant measure stochastically dominates an i.i.d. Bernoulli product measure. In particular, they proved this for and (for infection rate sufficiently large) d‐ary homogeneous trees T_d. In this paper, we prove some space‐time versions of their results. We do this by combining their methods with specific properties of the contact process and general correlation inequalities. One of our main results concerns the contact process on T_d with . We show that, for large infection rate, there exists a subset Δ of the vertices of T_d, containing a “positive fraction” of all the vertices of T_d, such that the following holds: The contact process on T_d observed on Δ stochastically dominates an independent spin‐flip process. (This is known to be false for the contact process on graphs having subexponential growth.) We further prove that the supercritical contact process on observed on certain d‐dimensional space‐time slabs stochastically dominates an i.i.d. Bernoulli product measure, from which we conclude strong mixing properties important in the study of certain random walks in random environment.     

An improved upper bound on the density of universal random graphs

We give a polynomial time randomized algorithm that, on receiving as input a pair (H, G) of n‐vertex graphs, searches for an embedding of H into G. If H has bounded maximum degree and G is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer and a large enough constant C = C_d, as , asymptotically almost all graphs with n vertices and at least edges contain as subgraphs all graphs with n vertices and maximum degree at most d. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014     

Graph limits of random graphs from a subset of connected k‐trees

For any set Ω of non‐negative integers such that , we consider a random Ω‐k‐tree G_n,k that is uniformly selected from all connected k‐trees of (n + k) vertices such that the number of (k + 1)‐cliques that contain any fixed k‐clique belongs to Ω. We prove that G_n,k, scaled by where H_k is the kth harmonic number and σ_Ω > 0, converges to the continuum random tree . Furthermore, we prove local convergence of the random Ω‐k‐tree to an infinite but locally finite random Ω‐k‐tree G_∞,k.     

Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

Two models of a random digraph on n vertices, and are studied. In 1990, Karp for D(n, p) and independently T. ?uczak for D(n,m = cn) proved that for c > 1, with probability tending to 1, there is an unique strong component of size of order n. Karp showed, in fact, that the giant component has likely size asymptotic to nθ², where θ = θ(c) is the unique positive root of . In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector , and two distinct 2 × 2 covariance matrices, and . To this end, we introduce and analyze a randomized deletion process which terminates at the directed (1, 1)‐core, the maximal digraph with minimum in‐degree and out‐degree at least 1. This (1, 1)‐core contains all non‐trivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the (1, 1)‐core, those outside the largest strong component, are of polylog order, thus dwarfed by anticipated fluctuations, on the scale of n^1/2, of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier‐based techniques. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 3–64, 2016     

Rainbow perfect matchings and Hamilton cycles in the random geometric graph

Given a graph on n vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colours on the edges. Similarly (for even n) a rainbow perfect matching is a collection of independent edges with pairwise different colours. In this note we show that if we randomly colour the edges of a random geometric graph with sufficiently many colours, then a.a.s. the graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and only if the minimum degree is at least 1 (respectively, at least 2). More precisely, consider n points (i.e. vertices) chosen independently and uniformly at random from the unit d‐dimensional cube for any fixed . Form a sequence of graphs on these n vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of lengths (measured with respect to the norm, for any fixed ). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of colours, where a sufficiently large fixed constant. Then, a.a.s. the first graph in the sequence with minimum degree at least 1 must contain a rainbow perfect matching (for even n), and the first graph with minimum degree at least 2 must contain a rainbow Hamilton cycle. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 587–606, 2017     

High degrees in random recursive trees

For , let T_n be a random recursive tree (RRT) on the vertex set . Let be the degree of vertex v in T_n, that is, the number of children of v in T_n. Devroye and Lu showed that the maximum degree Δ_n of T_n satisfies almost surely; Goh and Schmutz showed distributional convergence of along suitable subsequences. In this work we show how a version of Kingman's coalescent can be used to access much finer properties of the degree distribution in T_n. For any , let . Also, let be a Poisson point process on with rate function . We show that, up to lattice effects, the vectors converge weakly in distribution to . We also prove asymptotic normality of when slowly, and obtain precise asymptotics for when and is not too large. Our results recover and extends the previous distributional convergence results on maximal and near‐maximal degrees in RRT.