Meyniel's conjecture holds for random graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph , which improves upon existing results showing that asymptotically almost surely the cop number of is provided that for some . We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. This will also be used in a separate paper on random d‐regular graphs, where we show that the conjecture holds asymptotically almost surely when . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396–421, 2016     

Resilience of perfect matchings and Hamiltonicity in random graph processes

Let {G_i} be the random graph process: starting with an empty graph G₀ with n vertices, in every step i ≥ 1 the graph G_i is formed by taking an edge chosen uniformly at random among the nonexisting ones and adding it to the graph G_{i ? 1}. The classical “hitting‐time” result of Ajtai, Komlós, and Szemerédi, and independently Bollobás, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches 2, that is if δ(G_i) ≥ 2 then G_i is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for edges, the 2‐core of the graph G_m remains Hamiltonian even after an adversary removes ‐fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings.     

The size Ramsey number of short subdivisions of bounded degree graphs

For graphs G and F, write if any coloring of the edges of G with colors yields a monochromatic copy of the graph F. Suppose is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than edges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs.     

Random perfect graphs

We investigate the asymptotic structure of a random perfect graph P_n sampled uniformly from the set of perfect graphs on vertex set . Our approach is based on the result of Prömel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly. We show that the distribution of the maximum of the stability number and clique number is close to a concentrated distribution L(n) which plays an important role in our generation method. We also prove that the probability that P_n contains any given graph H as an induced subgraph is asymptotically 0 or or 1. Further we show that almost all perfect graphs are 2‐clique‐colorable, improving a result of Bacsó et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity equal to their minimum degree; they are almost all in class one (edge‐colorable using Δ colors, where Δ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphon .     

On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph

A uniform attachment graph (with parameter k), denoted G_n,k in the paper, is a random graph on the vertex set [n], where each vertex v makes k selections from [v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of G_n,k to show that the conductance of G_n,k is of order . We also study the bootstrap percolation on G_n,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.     

Fractional clique decompositions of dense graphs

For each , we show that any graph G with minimum degree at least has a fractional K_r‐decomposition. This improves the best previous bounds on the minimum degree required to guarantee a fractional K_r‐decomposition given by Dukes (for small r) and Barber, Kühn, Lo, Montgomery, and Osthus (for large r), giving the first bound that is tight up to the constant multiple of r (seen, for example, by considering Turán graphs). In combination with work by Glock, Kühn, Lo, Montgomery, and Osthus, this shows that, for any graph F with chromatic number , and any , any sufficiently large graph G with minimum degree at least has, subject to some further simple necessary divisibility conditions, an (exact) F‐decomposition.     

List colorings of multipartite hypergraphs

Let χ_l(G) denote the list chromatic number of the r‐uniform hypergraph G. Extending a result of Alon for graphs, Saxton and the second author used the method of containers to prove that, if G is simple and d‐regular, then . To see how close this inequality is to best possible, we examine χ_l(G) when G is a random r‐partite hypergraph with n vertices in each class. The value when r = 2 was determined by Alon and Krivelevich; here we show that almost surely, where d is the expected average degree of G and . The function g(r,α) is defined in terms of “preference orders” and can be determined fairly explicitly. This is enough to show that the container method gives an optimal lower bound on χ_l(G) for r = 2 and r = 3, but, perhaps surprisingly, apparently not for r ≥ 4.     

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     

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     

Long paths and cycles in random subgraphs of graphs with large minimum degree

For a given finite graph G of minimum degree at least k, let G_p be a random subgraph of G obtained by taking each edge independently with probability p. We prove that (i) if for a function that tends to infinity as k does, then G_p asymptotically almost surely contains a cycle (and thus a path) of length at least , and (ii) if , then G_p asymptotically almost surely contains a path of length at least k. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking G to be the complete graph on k + 1 vertices. © Wiley Periodicals, Inc. Random Struct. Alg., 46, 320–345, 2015     

Seeded graph matching via large neighborhood statistics

We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge‐correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is possible to achieve the information‐theoretic limit of graph sparsity in time polynomial in the number of vertices n. Moreover, we show the number of seeds needed for perfect recovery in polynomial‐time can be as low as in the sparse graph regime (with the average degree smaller than ) and in the dense graph regime, for a small positive constant . Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.     

Disproof of a packing conjecture of Alon and Spencer

A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graph G_n,1/2 typically admits a covering of a constant fraction of its edges by edge‐disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: for and A₁,…,A_t chosen uniformly and independently from the k‐subsets of {1,…,n}, what can one say about Our main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently.     

Diameter in ultra‐small scale‐free random graphs

It is well known that many random graphs with infinite variance degrees are ultra‐small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k^{?(τ ? 1)} with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to and , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order precisely when the minimal forward degree d_fwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.     

On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

Competition in growth and urns

We study survival among two competing types in two settings: a planar growth model related to two‐neighbor bootstrap percolation, and a system of urns with graph‐based interactions. In the planar growth model, uncolored sites are given a color at rate 0, 1 or , depending on whether they have zero, one, or at least two neighbors of that color. In the urn scheme, each vertex of a graph G has an associated urn containing some number of either blue or red balls (but not both). At each time step, a ball is chosen uniformly at random from all those currently present in the system, a ball of the same color is added to each neighboring urn, and balls in the same urn but of different colors annihilate on a one‐for‐one basis. We show that, for every connected graph G and every initial configuration, only one color survives almost surely. As a corollary, we deduce that in the two‐type growth model on , one of the colors only infects a finite number of sites with probability one. We also discuss generalizations to higher dimensions and multi‐type processes, and list a number of open problems and conjectures.     

For most graphs H,most H‐free graphs have a linear homogeneous set

Erd?s and Hajnal conjectured that for every graph H there is a constant such that every graph G that does not have H as an induced subgraph contains a clique or a stable set of order . The conjecture would be false if we set ; however, in an asymptotic setting, we obtain this strengthened form of Erd?s and Hajnal's conjecture for almost every graph H, and in particular for a large class of graphs H defined by variants of the colouring number. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 343–361, 2014     

Tree decompositions of graphs without large bipartite holes

A recent result of Condon, Kim, Kühn, and Osthus implies that for any , an n‐vertex almost r‐regular graph G has an approximate decomposition into any collections of n‐vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost αn‐regular graph G with any α>0 and a collection of bounded degree trees on at most (1?o(1))n vertices if G does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into n‐vertex trees. Moreover, this implies that for any α>0 and an n‐vertex almost αn‐regular graph G, with high probability, the randomly perturbed graph has an approximate decomposition into all collections of bounded degree trees of size at most (1?o(1))n simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey‐Turán theory and the randomly perturbed graph model.     

Finding a Hamilton cycle fast on average using rotations and extensions

We present an algorithm CRE, which either finds a Hamilton cycle in a graph G or determines that there is no such cycle in the graph. The algorithm's expected running time over input distribution G～G(n,p) is (1+o(1))n/p, the optimal possible expected time, for . This improves upon previous results on this problem due to Gurevich and Shelah, and to Thomason.     

Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number

An adjacent vertex distinguishing edge coloring of a graph G without isolated edges is its proper edge coloring such that no pair of adjacent vertices meets the same set of colors in G. We show that such coloring can be chosen from any set of lists associated to the edges of G as long as the size of every list is at least , where Δ is the maximum degree of G and C is a constant. The proof is probabilistic. The same is true in the environment of total colorings.