Search

In this paper we show that the random degree constrained process (a time-evolving random graph model with degree constraints) has a local weak limit, provided that the underlying host graphs are high degree almost regular. We, moreover, identify the limit object as a multi-type branching process, by combining coupling arguments with the analysis of a certain recursive tree process. Using a spectral characterization, we also give an asymptotic expansion of the critical time when the giant component emerges in the so-called random $d$-process, resolving a problem of Warnke and Wormald for large $d$., Comment: 53 pages, 3 figures

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In this paper, we determine the order of magnitude of the clique chromatic number of the random graph G_{n,p} for most edge-probabilities p in the range n^{-2/5} \ll p \ll 1. This resolves open problems and questions of Lichev, Mitsche and Warnke as well as Alon and Krievelevich. One major proof difficulty stems from high-degree vertices, which prevent maximal cliques in their neighborhoods: we deal with these vertices by an intricate union bound argument, that combines the probabilistic method with new degree counting arguments in order to enable Janson's inequality. This way we determine the asymptotics of the clique chromatic number of G_{n,p} in some ranges, and discover a surprising new phenomenon that contradicts earlier predictions for edge-probabilities p close to n^{-2/5}., Comment: 24 pages; minor edits

We show that the domination number of the binomial random graph G_{n,p} with edge-probability p is concentrated on two values for p \ge n^{-2/3+\eps}, and not concentrated on two values for general p \le n^{-2/3}. This refutes a conjecture of Glebov, Liebenau and Szabo, who showed two-point concentration for p \ge n^{-1/2+\eps}, and conjectured that two-point concentration fails for p \ll n^{-1/2}. The proof of our main result requires a Poisson type approximation for the probability that a random bipartite graph has no isolated vertices, in a regime where standard tools are unavailable (as the expected number of isolated vertices is relatively large). We achieve this approximation by adapting the proof of Janson's inequality to this situation, and this adaptation may be of broader interest., Comment: 16 pages; references updated

We consider maximum rooted tree extension counts in random graphs, i.e., we consider M_n = \max_v X_v where X_v counts the number of copies of a given tree in G_{n,p} rooted at vertex v. We determine the asymptotics of M_n when the random graph is not too sparse, specifically when the edge probability p=p(n) satisfies p(1-p)n \gg \log n. The problem is more difficult in the sparser regime 1 \ll pn \ll \log n, where we determine the asymptotics of M_n for specific classes of trees. Interestingly, here our large deviation type optimization arguments reveal that the behavior of M_n changes as we vary p=p(n), due to different mechanisms that can make the maximum large., Comment: 38 pages; added Gumbel corollary

Gunby-He-Narayanan showed that the logarithmic gap predictions of Kahn-Kalai and Talagrand (proved by Park-Pham and Frankston-Kahn-Narayanan-Park) about thresholds of up-sets do not apply to down-sets. In particular, for the down-set of triangle-free graphs, they showed that there is a polynomial gap between the threshold and the factional expectation threshold. In this short note we give a simpler proof of this result, and extend the polynomial threshold gap to down-sets of F-free graphs., Comment: 5 pages; to appear in Random Structures and Algorithms (RSA)

We present a simple inductive proof of the Lagrange Inversion Formula., Comment: 5 pages; to appear in The American Mathematical Monthly

We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. We resolve several open problems of Chatterjee and Diaconis, and also confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble: (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has an unusual limiting distribution., Comment: 26 pages, 2 figures

The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1, \ldots, d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i. Wormald conjectured in 1999 that, for d-regular degree sequences D_n, the final graph of this process is similar to a uniform random d-regular graph. In this paper we show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n. The combinatorial proof technique is our main conceptual contribution: we adapt the switching method to the degree-restricted process, demonstrating that this enumeration technique can also be used to analyze stochastic processes (rather than just uniform random models, as before)., Comment: 32 pages, 3 figures

Shamir and Spencer proved in the 1980s that the chromatic number of the binomial random graph G(n,p) is concentrated in an interval of length at most \omega\sqrt{n}, and in the 1990s Alon showed that an interval of length \omega\sqrt{n}/\log n suffices for constant edge-probabilities p \in (0,1). We prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case p=p(n) \to 0, and uncover a surprising concentration `jump' of the chromatic number in the very dense case p=p(n) \to 1., Comment: 11 pages, 1 figure. Minor edits, to appear in The Electronic Journal of Combinatorics

This work studies the typical structure of sparse $H$-free graphs, that is, graphs that do not contain a subgraph isomorphic to a given graph $H$. Extending the seminal result of Osthus, Pr\"omel, and Taraz that addressed the case where $H$ is an odd cycle, Balogh, Morris, Samotij, and Warnke proved that, for every $r \ge 3$, the structure of a random $K_{r+1}$-free graph with $n$ vertices and $m$ edges undergoes a phase transition when $m$ crosses an explicit (sharp) threshold function $m_r(n)$. They conjectured that a similar threshold phenomenon occurs when $K_{r+1}$ is replaced by any strictly $2$-balanced, edge-critical graph $H$. In this paper, we resolve this conjecture. In fact, we prove that the structure of a typical $H$-free graph undergoes an analogous phase transition for every $H$ in a family of vertex-critical graphs that includes all edge-critical graphs., Comment: 54 pages; minor edits; to appear in Random Structures and Algorithms (RSA)

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 McDiarmid, Mitsche and Pralat noted that around p \approx n^{-1/2} the clique chromatic number of the random graph G_{n,p} changes by n^{\Omega(1)} when we increase the edge-probability p by n^{o(1)}, but left the details of this surprising phenomenon as an open problem. We settle this problem, i.e., resolve the nature of this polynomial `jump' of the clique chromatic number of the random graph G_{n,p} around edge-probability p \approx n^{-1/2}. Our proof uses a mix of approximation and concentration arguments, which enables us to (i) go beyond Janson's inequality used in previous work and (ii) determine the clique chromatic number of G_{n,p} up to logarithmic factors for any edge-probability p., Comment: 14 pages

In this paper we solve two problems of Esperet, Kang and Thomasse as well as Li concerning (i) induced bipartite subgraphs in triangle-free graphs and (ii) van der Waerden numbers. Each time random greedy algorithms allow us to go beyond the Lovasz Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method., Comment: 14 pages; minor edits; to appear in European Journal of Combinatorics

The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/log n for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n)., Comment: 20 pages

A sunflower with p petals consists of p sets whose pairwise intersections are identical. The goal of the sunflower problem is to find the smallest r=r(p,k) such that any family of r^k distinct k-element sets contains a sunflower with p petals. Building upon a breakthrough of Alweiss, Lovett, Wu and Zhang from 2019, Rao proved that r=O(p log(pk)) suffices; this bound was reproved by Tao in 2020. In this short note we record that r=O(p log k) suffices, by using a minor variant of the probabilistic part of these recent proofs., Comment: 3 pages; based on 2020 REU; minor edits; to appear in Discrete Mathematics

We consider rooted subgraphs in random graphs, i.e., extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. In 1989, Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices. For the important strictly balanced case, Spencer also raised the fundamental question as to whether these conditions are necessary. We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open., Comment: 22 pages, 2 figures. Minor edits, to appear in Random Structures and Algorithms (RSA)

We present a refinement of the classical alteration method for constructing $H$-free graphs: for suitable edge-probabilities $p$, we show that removing all edges in $H$-copies of the binomial random graph $G_{n,p}$ does not significantly change the independence number. This differs from earlier alteration approaches of Erd\H{o}s and Krivelevich, who obtained similar guarantees by removing one edge from each $H$-copy (instead of all of them). We demonstrate the usefulness of our refined alternation method via two applications to online graph Ramsey games, where it enables easier analysis., Comment: 10 pages; minor edits; to appear in the Journal of Graph Theory

This note contains a short and simple proof of Wormald's differential equation method (that yields slightly improved approximation guarantees and error probabilities). This powerful method uses differential equations to approximate the time-evolution/dynamics of random processes and algorithms., Comment: 7 pages; minor corrections

We study the following preferential attachment variant of the classical Erdos-Renyi random graph process. Starting with an empty graph on n vertices, new edges are added one-by-one, and each time an edge is chosen with probability roughly proportional to the product of the current degrees of its endpoints (note that the vertex set is fixed). We determine the asymptotic size of the giant component in the supercritical phase, confirming a conjecture of Pittel from 2010. Our proof uses a simple method: we condition on the vertex degrees (of a multigraph variant), and use known results for the configuration model., Comment: 20 pages

For r \ge 2, let X be the number of r-armed stars K_{1,r} in the binomial random graph G_{n,p}. We study the upper tail \Pr(X \ge (1+\epsilon)\E X), and establish exponential bounds which are best possible up to constant factors in the exponent (for the special case of stars K_{1,r} this solves a problem of Janson and Rucinski, and confirms a conjecture by DeMarco and Kahn). In contrast to the widely accepted standard for the upper tail problem, we do not restrict our attention to constant \epsilon, but also allow for \epsilon \ge n^{-\alpha} deviations., Comment: 14 pages

Given a fixed graph H, what is the (exponentially small) probability that the number X_H of copies of H in the binomial random graph G_{n,p} is at least twice its mean? Studied intensively since the mid 1990s, this so-called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of \Pr(X_H \ge (1+\epsilon) \E X_H) for fixed \epsilon>0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound., Comment: 15 pages; minor edits; to appear in Random Structures and Algorithms (RSA)

In 1973 Erdos asked whether there are n-vertex partial Steiner triple systems with arbitrary high girth and quadratically many triples. (Here girth is defined as the smallest integer g \ge 4 for which some g-element vertex-set contains at least g-2 triples.) We answer this question, by showing existence of approximate Steiner triple systems with arbitrary high girth. More concretely, for any fixed \ell \ge 4 we show that a natural constrained random process typically produces a partial Steiner triple system with (1/6-o(1))n^2 triples and girth larger than \ell. The process iteratively adds random triples subject to the constraint that the girth remains larger than \ell. Our result is best possible up to the o(1)-term, which is a negative power of n., Comment: 16 pages; minor edits; to appear in Journal of the London Mathematical Society (JLMS)

In 1995 Kim famously proved the Ramsey bound R(3,t) \ge c t^2/\log t by constructing an n-vertex graph that is triangle-free and has independence number at most C \sqrt{n \log n}. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph K_n into a packing of such nearly optimal Ramsey R(3,t) graphs. More precisely, for any \epsilon>0 we find an edge-disjoint collection (G_i)_i of n-vertex graphs G_i \subseteq K_n such that (a) each G_i is triangle-free and has independence number at most C_\epsilon \sqrt{n \log n}, and (b) the union of all the G_i contains at least (1-\epsilon)\binom{n}{2} edges. Our algorithmic proof proceeds by sequentially choosing the graphs G_i via a semi-random (i.e., Rodl nibble type) variation of the triangle-free process. As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabo (concerning a Ramsey-type parameter introduced by Burr, Erdos, Lovasz in 1976). Namely, denoting by s_r(H) the smallest minimum degree of r-Ramsey minimal graphs for H, we close the existing logarithmic gap for H=K_3 and establish that s_r(K_3) = \Theta(r^2 \log r)., Comment: 22 pages

We consider branching processes consisting of particles (individuals) of two types (type L and type S) in which only particles of type L have offspring, proving estimates for the survival probability and the (tail of) the distribution of the total number of particles. Such processes are in some sense closer to single- than to multi-type branching processes. Nonetheless, the second, barren, type complicates the analysis significantly. The results proved here (about point and survival probabilities) are a key ingredient in the analysis of bounded-size Achlioptas processes in a recent paper by the last two authors., Comment: 23 pages. References updated

Perhaps the best understood phase transition is that in the component structure of the uniform random graph process introduced by Erd\H{o}s and R\'enyi around 1960. Since the model is so fundamental, it is very interesting to know which features of this phase transition are specific to the model, and which are `universal', at least within some larger class of processes (a `universality class'). Achlioptas process, a class of variants of the Erd\H{o}s--R\'enyi process that are easy to define but difficult to analyze, have been extensively studied from this point of view. Here, settling a number of conjectures and open problems, we show that all `bounded-size' Achlioptas processes share (in a strong sense) all the key features of the Erd\H{o}s--R\'enyi phase transition. We do not expect this to hold for Achlioptas processes in general., Comment: 95 pages, 7 figures

We study the upper tail of the number of arithmetic progressions of a given length in a random subset of {1,...,n}, establishing exponential bounds which are best possible up to constant factors in the exponent. The proof also extends to Schur triples, and, more generally, to the number of edges in random induced subhypergraphs of `almost linear' k-uniform hypergraphs., Comment: 28 pages. To appear in Israel Journal of Mathematics

In the late 1990s, Kim and Vu pioneered an inductive method for showing concentration of certain random variables X. Shortly afterwards, Janson and Ruci{\'n}ski developed an alternative inductive approach, which often gives comparable results for the upper tail Pr(X \ge (1+\eps) E[X]). In some cases, both methods yield upper tail estimates which are best possible up to a logarithmic factor in the exponent, but closing this narrow gap has remained a technical challenge. In this paper we present a BK-inequality based combinatorial sparsification idea that can recover this missing logarithmic term in the upper tail. As an illustration, we consider random subsets of the integers {1,...,n}, and prove sharp upper tail estimates for various objects of interest in additive combinatorics. Examples include the number of arithmetic progressions, Schur triples, additive quadruples, and (r,s)-sums., Comment: 31 pages; minor edits; to appear in Journal of Combinatorial Theory, Series B (JCTB)

For percolation on finite transitive graphs, Nachmias and Peres suggested a characterization of the critical probability based on the logarithmic derivative of the susceptibility. As a first test-case, we study their suggestion for the Erd\H{o}s-R\'enyi random graph G_{n,p}, and confirm that the logarithmic derivative has the desired properties: (i) its maximizer lies inside the critical window p=1/n+\Theta(n^{-4/3}), and (ii) the inverse of its maximum value coincides with the \Theta(n^{-4/3})-width of the critical window. We also prove that the maximizer is not located at p=1/n or p=1/(n-1), refuting a speculation of Peres., Comment: 22 pages, 1 figure

The well-known "Janson's inequality" gives Poisson-like upper bounds for the lower tail probability \Pr(X \le (1-\eps)\E X) when X is the sum of dependent indicator random variables of a special form. We show that, for large deviations, this inequality is optimal whenever X is approximately Poisson, i.e., when the dependencies are weak. We also present correlation-based approaches that, in certain symmetric applications, yield related conclusions when X is no longer close to Poisson. As an illustration we, e.g., consider subgraph counts in random graphs, and obtain new lower tail estimates, extending earlier work (for the special case \eps=1) of Janson, Luczak and Rucinski., Comment: 21 pages

Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erd\H{o}s and R\'enyi, and the family of $H$-free graphs, that is, graphs which do not contain a subgraph isomorphic to a given (usually small) graph $H$. A widely studied problem that lies at the interface of these two areas is that of determining how the structure of a typical $H$-free graph with $n$ vertices and $m$ edges changes as $m$ grows from $0$ to $\text{ex}(n,H)$. In this paper, we resolve this problem in the case when $H$ is a clique, extending a classical result of Kolaitis, Pr\"omel, and Rothschild. In particular, we prove that for every $r \ge 2$, there is an explicit constant $\theta_r$ such that, letting $m_r = \theta_r n^{2-\frac{2}{r+2}} (\log n)^{1/\left[\binom{r+1}{2}-1\right]}$, the following holds for every positive constant $\varepsilon$. If $m \ge (1+\varepsilon) m_r$, then almost all $K_{r+1}$-free $n$-vertex graphs with $m$ edges are $r$-partite, whereas if $n \ll m \le (1-\varepsilon)m_r$, then almost all of them are not $r$-partite., Comment: 42 pages; minor edits

Concentration inequalities are fundamental tools in probabilistic combinatorics and theoretical computer science for proving that random functions are near their means. Of particular importance is the case where f(X) is a function of independent random variables X=(X_1, ..., X_n). Here the well known bounded differences inequality (also called McDiarmid's or Hoeffding-Azuma inequality) establishes sharp concentration if the function f does not depend too much on any of the variables. One attractive feature is that it relies on a very simple Lipschitz condition (L): it suffices to show that |f(X)-f(X')| \leq c_k whenever X,X' differ only in X_k. While this is easy to check, the main disadvantage is that it considers worst-case changes c_k, which often makes the resulting bounds too weak to be useful. In this paper we prove a variant of the bounded differences inequality which can be used to establish concentration of functions f(X) where (i) the typical changes are small although (ii) the worst case changes might be very large. One key aspect of this inequality is that it relies on a simple condition that (a) is easy to check and (b) coincides with heuristic considerations why concentration should hold. Indeed, given an event \Gamma that holds with very high probability, we essentially relax the Lipschitz condition (L) to situations where \Gamma occurs. The point is that the resulting typical changes c_k are often much smaller than the worst case ones. To illustrate its application we consider the reverse H-free process, where H is 2-balanced. We prove that the final number of edges in this process is concentrated, and also determine its likely value up to constant factors. This answers a question of Bollob\'as and Erd\H{o}s., Comment: 25 pages

In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. Although the evolution of such `local' modifications of the Erd{\H o}s--R\'enyi random graph process has received considerable attention during the last decade, so far only rather simple rules are well understood. Indeed, the main focus has been on `bounded-size' rules, where all component sizes larger than some constant $B$ are treated the same way, and for more complex rules very few rigorous results are known. In this paper we study Achlioptas processes given by (unbounded) size rules such as the sum and product rules. Using a variant of the neighbourhood exploration process and branching process arguments we show that certain key statistics are tightly concentrated at least until the susceptibility (the expected size of the component containing a randomly chosen vertex) diverges. Our convergence result is most likely best possible for certain rules: in the later evolution the number of vertices in small components may not be concentrated. Furthermore, we believe that for a large class of rules the critical time where the susceptibility `blows up' coincides with the percolation threshold., Comment: 33 pages, 2 figures

Janson and Janson, Luczak and Rucinski proved several inequalities for the lower tail of the distribution of the number of events that hold, when all the events are up-sets (increasing events) of a special form - each event is the intersection of some subset of a single set of independent events (i.e., a principal up-set). We show that these inequalities in fact hold for arbitrary up-sets, by modifying existing proofs to use only positive correlation, avoiding the need to assume positive correlation conditioned on one of the events., Comment: 5 pages. Added weighted variant

We consider a class of percolation models, called Achlioptas processes, discussed in [Science 323, 1453 (2009)] and [Science 333, 322 (2011)]. For these the evolution of the order parameter (the rescaled size of the largest connected component) has been the main focus of research in recent years. We show that, in striking contrast to `classical' models, self-averaging is not a universal feature of these new percolation models: there are natural Achlioptas processes whose order parameter has random fluctuations that do not disappear in the thermodynamic limit., Comment: 4 pages, 3 figures. Revised and expanded. Title changed

In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. The evolution of the rescaled size of the largest component in such variations of the Erd\H{o}s--R\'enyi random graph process has recently received considerable attention, in particular for for Bollob\'as's `product rule'. In this paper we establish the following result for rules such as the product rule: the limit of the rescaled size of the `giant' component exists and is continuous provided that a certain system of differential equations has a unique solution. In fact, our result applies to a very large class of Achlioptas-like processes. Our proof relies on a general idea which relates the evolution of stochastic processes to an associated system of differential equations. Provided that the latter has a unique solution, our approach shows that certain discrete quantities converge (after appropriate rescaling) to this solution., Comment: 18 pages. Revised and expanded version

It is widely believed that certain simple modifications of the random graph process lead to discontinuous phase transitions. In particular, starting with the empty graph on $n$ vertices, suppose that at each step two pairs of vertices are chosen uniformly at random, but only one pair is joined, namely, one minimizing the product of the sizes of the components to be joined. Making explicit an earlier belief of Achlioptas and others, in 2009, Achlioptas, D'Souza and Spencer [Science 323 (2009) 1453-1455] conjectured that there exists a $\delta>0$ (in fact, $\delta\ge1/2$) such that with high probability the order of the largest component "jumps" from $o(n)$ to at least $\delta n$ in $o(n)$ steps of the process, a phenomenon known as "explosive percolation." We give a simple proof that this is not the case. Our result applies to all "Achlioptas processes," and more generally to any process where a fixed number of independent random vertices are chosen at each step, and (at least) one edge between these vertices is added to the current graph, according to any (online) rule. We also prove the existence and continuity of the limit of the rescaled size of the giant component in a class of such processes, settling a number of conjectures. Intriguing questions remain, however, especially for the product rule described above., Comment: Published in at http://dx.doi.org/10.1214/11-AAP798 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

The C_\ell-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of C_\ell is created. For every $\ell \geq 4$ we show that, with high probability as $n \to \infty$, the maximum degree is $O((n \log n)^{1/(\ell-1)})$, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the C_\ell-free process typically terminates with $\Theta(n^{\ell/(\ell-1)}(\log n)^{1/(\ell-1)})$ edges, which answers a question of Erd\H{o}s, Suen and Winkler. This is the first result that determines the final number of edges of the more general H-free process for a non-trivial \emph{class} of graphs H. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to `transfer' certain decreasing properties from the binomial random graph to the H-free process., Comment: 34 pages, 5 figures. Minor revisions and additions

The K_4-free process starts with the empty graph on n vertices and at each step adds a new edge chosen uniformly at random from all remaining edges that do not complete a copy of K_4. Let G be the random maximal K_4-free graph obtained at the end of the process. We show that for some positive constant C, with high probability as $n \to \infty$, the maximum degree in G is at most $C n^{3/5}\sqrt[5]{\log n}$. This resolves a conjecture of Bohman and Keevash for the K_4-free process and improves on previous bounds obtained by Bollob\'as and Riordan and by Osthus and Taraz. Combined with results of Bohman and Keevash this shows that with high probability G has $\Theta(n^{8/5}\sqrt[5]{\log n})$ edges and is `nearly regular', i.e., every vertex has degree $\Theta(n^{3/5}\sqrt[5]{\log n})$. This answers a question of Erd\H{o}s, Suen and Winkler for the K_4-free process. We furthermore deduce an additional structural property: we show that whp the independence number of G is at least $\Omega(n^{2/5}(\log n)^{4/5}/\log \log n)$, which matches an upper bound obtained by Bohman up to a factor of $\Theta(\log \log n)$. Our analysis of the K_4-free process also yields a new result in Ramsey theory: for a special case of a well-studied function introduced by Erd\H{o}s and Rogers we slightly improve the best known upper bound., Comment: 39 pages, 3 figures. Minor edits. To appear in Random Structures and Algorithms

The H-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of H is created, where H is some fixed graph. When H is strictly 2-balanced, we show that for some c,d>0, with high probability as $n \to \infty$, the final graph of the H-free process contains no subgraphs F on $v_F \leq n^{d}$ vertices with maximum density $\max_{J \subseteq F}\{e_J/v_J\} \geq c$. This extends and generalizes results of Gerke and Makai for the C_3-free process., Comment: 7 pages, revised version