Pancyclic subgraphs of random graphs

An n‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≤t≤n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n^?1/2, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). © 2011 Wiley Periodicals, Inc.     

Extremal subgraphs of random graphs

We prove that there is a constant c > 0, such that whenever p ≥ n^‐c, with probability tending to 1 when n goes to infinity, every maximum triangle‐free subgraph of the random graph G_n,p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M ? n and M ≤ /2, is “nearly unique”. More precisely, given a maximum cut C of G_n,M, we can obtain all maximum cuts by moving at most \begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*} vertices between the parts of C. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Spanning subgraphs of random graphs

We propose a problem concerning the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random graphs. We prove some bounds and demonstrate them in the cases of ad-cube and a two dimensional lattice.     

Extremal subgraphs of random graphs

We shall prove that if L is a 3-chromatic (so called “forbidden”) graph, and —Rⁿ is a random graph on n vertices, whose edges are chosen independently, with probability p, and —Bⁿ is a bipartite subgraph of Rⁿ of maximum size, —Fⁿ is an L-free subgraph of Rⁿ of maximum size, then (in some sense) Fⁿ and Bⁿ are very near to each other: almost surely they have almost the same number of edges, and one can delete O_p(1) edges from Fⁿ to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, Fⁿ is almost surely bipartite.     

On random subgraphs of Kneser graphs and their generalizations

A series of results are obtained on the stability of the independence number of random subgraphs of distance graphs, which are natural generalizations of the classical Kneser graphs.     

Small subgraphs of random regular graphs

The main aim of this short paper is to answer the following question. Given a fixed graph H, for which values of the degree d does a random d-regular graph on n vertices contain a copy of H with probability close to one?     

On random k‐out subgraphs of large graphs

We consider random subgraphs of a fixed graph with large minimum degree. We fix a positive integer k and let G_k be the random subgraph where each independently chooses k random neighbors, making kn edges in all. When the minimum degree then G_k is k‐connected w.h.p. for ; Hamiltonian for k sufficiently large. When , then G_k has a cycle of length for . By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function (or ) where . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017     

Distribution of subgraphs of random regular graphs

We obtain the asymptotic distribution of the number of copies of a fixed subgraph H in a random d‐regular graph, provided H is strictly balanced and d = d(n) is chosen so that the expected number of copies of H tends to infinity (but not too quickly), and the expected number of copies sharing edges with two other copies is bounded. The proof of asymptotic normality of the distribution uses a method of factorial moments for variables with unbounded means that was recently derived by the authors. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Spanning maximal planar subgraphs of random graphs

We study the threshold for the existence of a spanning maximal planar subgraph in the random graph G_{n, p} . We show that it is very near p = 1/n^? We also discuss the threshold for the existence of a spanning maximal outerplanar subgraph. This is very near p = 1/n^½.     

OnK 4-free subgraphs of random graphs

For 0<1 and graphsG andH, writeGH if any -proportion of the edges ofG spans at least one copy ofH inG. As customary, writeK ^r for the complete graph onr vertices. We show that for every fixed real >0 there exists a constantC=C() such that almost every random graphG _n,p withp=p(n)Cn ^–2/5 satisfiesG _{n,p 2/3+} K ⁴. The proof makes use of a variant of Szemerédi's regularity lemma for sparse graphs and is based on a certain superexponential estimate for the number of pseudo-random tripartite graphs whose triangles are not too well distributed. Related results and a general conjecture concerningH-free subgraphs of random graphs in the spirit of the Erds-Stone theorem are discussed.The first author was partially supported by FAPESP (Proc. 93/0603-1) and by CNPq (Proc. 300334/93-1 and ProTeM-CC-II Project ProComb). Part of this work was done while the second author was visiting the University of São Paulo, supported by FAPESP (Proc. 94/4276-8). The third author was partially supported by the NSF grant DMS-9401559.     

Connectivity threshold for random chordal graphs

We introduce a model for random chordal graphs. We determine the thresholds for: the first edge, completeness, isolated vertices and connectivity. Like the Erdös-Rényi model, the thresholds for isolated vertices and connectivity are the same. Unlike the Erdös-Rényi model in which the threshold occurs at 1/2n logn edges, this threshold occurs atO(n ²) edges.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.     

Independence numbers of random subgraphs of distance graphs

We consider the distance graph G(n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erd?s–Ko–Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G(n, r, s) in the Erd?s–Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log₂n) times as large as that of the graph G(n, r, s) itself for r ≤ 2s + 1, while for r > 2s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide.     

Matchings in random spanning subgraphs of cubelike graphs

A question about the evolution of random spanning subgraphs G _p of bipartite regular so called cubelike graphs G is considered. It is shown that for G _p of any large enough cubelike graph G the threshold to have a 1-factor is the same as the threshold to have no isolated vertices. This generalizes a conjecture of K. Weber.     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

The threshold for combs in random graphs

For let denote the tree consisting of an ‐vertex path with disjoint ‐vertex paths beginning at each of its vertices. An old conjecture says that for any the threshold for the random graph to contain is at . Here we verify this for with any fixed . In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for (with ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 794–802, 2016     

Distribution of the number of spanning regular subgraphs in random graphs

In this paper, we examine the moments of the number of d ‐factors in begin{align*}mathcal{ G}(n,p)end{align*} for all p and d satisfying d³ = o(p²n). We also determine the limiting distribution of the number of d ‐factors inside this range with further restriction that begin{align*}(1-p)sqrt{dn}toinftyend{align*} as n →∞.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013