Consider the following one-player game. Starting with the empty graph on n vertices, in every step a new edge is drawn uniformly at random and inserted into the current graph. This edge has to be coloured immediately with one of r available colours. The player's goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. We prove a lower bound of nβ(F,r) on the typical duration of this game, where β(F,r) is a function that is strictly increasing in r and satisfies limr→∞ β(F,r) = 2 − 1/m2(F), where n2−1/m2(F) is the threshold of the corresponding offline colouring problem.

Consider a uniform random rooted labelled tree on n vertices. We imagine that each node of the tree has space for a single car to park. A number m ≤ n of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider m = ⌊α n⌋ and let An,α denote the event that all ⌊α n⌋ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if α ≤ 1/2, we have $\mathbb{P}({A_{n,\alpha}}) \to {\sqrt{1-2\alpha}}/{(1-\alpha})$, whereas if α > 1/2 we have $\mathbb{P}({A_{n,\alpha}}) \to 0$. We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we consider the following variant of the problem: take the tree to be the family tree of a Galton–Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson(α) number of cars arrive at each vertex. Let X be the number of cars which visit the root of the tree. We show that $\mathbb{E}{[X]}$ undergoes a discontinuous phase transition, which turns out to be a generic phenomenon for arbitrary offspring distributions of mean at least 1 for the tree and arbitrary arrival distributions.

A famous result of Freĭman describes the sets A, of integers, for which |A+A| ≤ K|A|. In this short note we address the analogous question for subsets of vector spaces over . Specifically we show that if A is a subset of a vector space over with |A+A| ≤ K|A| then A is contained in a coset of size at most 2O(K3/2 log K)|A|, which improves upon the previous best, due to Green and Ruzsa, of 2O(K2)|A|. A simple example shows that the size may need to be at least 2Ω(K)|A|.

We prove results about the Lp-almost-periodicity of convolutions. One of these follows from a simple but rather general lemma about approximating a sum of functions in Lp, and gives a very short proof of a theorem of Green that if A and B are subsets of {1,. . .,N} of sizes αN and βN then A+B contains an arithmetic progression of length at least

\begin{equation} \exp ( c (\alpha \beta \log N)^{1/2} - \log\log N). \end{equation}

\begin{equation} \exp\biggl( c \biggl(\frac{\alpha \log N}{\log^3 2\beta^{-1}} \biggr)^{1/2} - \log( \beta^{-1} \log N) \biggr). \end{equation}

We prove that a bipartite uniquely Hamiltonian graph has a vertex of degree 2 in each color class. As consequences, every bipartite Hamiltonian graph of minimum degree d has at least 21−dd! Hamiltonian cycles, and every bipartite Hamiltonian graph of minimum degree at least 4 and girth g has at least (3/2)g/8 Hamiltonian cycles. We indicate how the existence of more than one Hamiltonian cycle may lead to a general reduction method for Hamiltonian graphs.

A graph G is called an H-type graph for some graph H if there is a mapping from V(G) to V(H) preserving edges. In this paper, we shall prove that: (1) every triangle-free graph G of order n with χ(G)[les ]3 and δ(G)>n/3 is of Fd-type for some d[ges ]1, where Fd is a certain d-regular triangle-free Hamiltonian Cayley graph of order 3d−1, (2) every triangle-free graph G of order n with χ(G)[ges ]4 and δ(G)>n/3 contains the Mycielski graph (see Figure 2) as a subgraph.

A graph G is m-choosable with impropriety d, or simply (m, d)*-choosable, if, for every list assignment L, where [mid ]L(v)[mid ][ges ]m for every v∈V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We prove a Grötzsch-type theorem for list colourings with impropriety one, that is, the (3, 1)*-choosability for triangle-free planar graphs; in the proof the method of extending a precolouring of a 4- or 5-cycle is used.

It has been shown [2] that if n is odd and m1,…,mt are integers with mi[ges ]3 and [sum ]i=1tmi=|E(Kn)| then Kn can be decomposed as an edge-disjoint union of closed trails of lengths m1,…,mt. This result was later generalized [3] to all sufficiently dense Eulerian graphs G in place of Kn. In this article we consider the corresponding questions for directed graphs. We show that the complete directed graph <?TeX \displaystyle{\mathop{K}^{\raise-2pt\hbox{$\scriptstyle\leftrightarrow$}}}_{n}?> can be decomposed as an edge-disjoint union of directed closed trails of lengths m1,…,mt whenever mi[ges ]2 and <?TeX \sum_{i=1}^t m_{i}=\vert E({\leftrightarrow}_{n})\vert ?>, except for the single case when n=6 and all mi=3. We also show that sufficiently dense Eulerian digraphs can be decomposed in a similar manner, and we prove corresponding results for (undirected) complete multigraphs.

Let R = (r1, . . ., rm) and C = (c1, . . ., cn) be positive integer vectors such that r1 + ⋯ + rm = c1 + ⋯ + cn. We consider the set Σ(R, C) of non-negative m × n integer matrices (contingency tables) with row sums R and column sums C as a finite probability space with the uniform measure. We prove that a random table D ∈ Σ(R, C) is close with high probability to a particular matrix (‘typical table’) Z defined as follows. We let g(x) = (x + 1)ln(x + 1) − x ln x for x ≥ 0 and let g(X) = ∑i,jg(xij) for a non-negative matrix X = (xij). Then g(X) is strictly concave and attains its maximum on the polytope of non-negative m × n matrices X with row sums R and column sums C at a unique point, which we call the typical table Z.

We prove that there exists a constant c such that, for any integer Δ, the Ramsey number of a bipartite graph on n vertices with maximum degree Δ is less than 2cΔn. A probabilistic argument due to Graham, Rödl and Ruciński implies that this result is essentially sharp, up to the constant c in the exponent. Our proof hinges upon a quantitative form of a hypergraph packing result of Rödl, Ruciński and Taraz.

We provide an alternative, simpler and more general derivation of the Clarkson–Shor probabilistic technique [7] and use it to obtain several extensions and new combinatorial bounds.

Let r ≥ 3 and (c/rr)r log n ≥ 1. If G is a graph of order n and its largest eigenvalue μ(G) satisfies then G contains a complete r-partite subgraph with r − 1 parts of size ⌊(c/rr)r log n⌋ and one part of size greater than n1−cr−1.

This result implies the Erdős–Stone–Bollobás theorem, the essential quantitative form of the Erdős–Stone theorem. Another easy consequence is that if F1, F2, . . . are r-chromatic graphs satisfying v(Fn) = o(log n), then

The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovász and Vu [25] yielded a (log logn)2 polynomial time approximation. We refine the upper bound of [25], and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdős–Rényi random graph G(n, c/n) in the supercritical regime with c > 1 fixed, is asymptotic to ϕ(c)nlog2n, where ϕ(c) → 1 as c ↓ 1. However, our new bound implies that the cover time for the critical Erdős–Rényi random graph G(n, 1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0, 1}n, on high-girth expanders, and on tori ℤdn for fixed large d. This approach also gives a simpler proof of a result of Aldous [2] that the cover time of a uniform labelled tree on k vertices is of order k3/2. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman [45], is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.

For k prime and A a finite set of integers with |A| ≥ 3(k − 1)2(k − 1)! we prove that |A + k · A| ≥ (k + 1)|A| − ⌈k(k + 2)/4⌉ where k · A = {ka: a ∈ A}. We also describe the sets for which equality holds.

In this work we determine the expected number of vertices of degree k = k(n) in a graph with n vertices that is drawn uniformly at random from a subcritical graph class. Examples of such classes are outerplanar, series-parallel, cactus and clique graphs. Moreover, we provide exponentially small bounds for the probability that the quantities in question deviate from their expected values.

We prove an analogue of Alon’s spectral gap conjecture for random bipartite, biregular graphs. We use the Ihara–Bass formula to connect the non-backtracking spectrum to that of the adjacency matrix, employing the moment method to show there exists a spectral gap for the non-backtracking matrix. A by-product of our main theorem is that random rectangular zero-one matrices with fixed row and column sums are full rank with high probability. Finally, we illustrate applications to community detection, coding theory, and deterministic matrix completion.

For a graph G and an integer t we let mcct(G) be the smallest m such that there exists a colouring of the vertices of G by t colours with no monochromatic connected subgraph having more than m vertices. Let be any non-trivial minor-closed family of graphs. We show that mcc2(G) = O(n2/3) for any n-vertex graph G ∈ . This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such , and every fixed t we show that mcct(G)=O(n2/(t+1)). On the other hand, we have examples of graphs G with no Kt+3 minor and with mcct(G)=Ω(n2/(2t−1)).

It is also interesting to consider graphs of bounded degrees. Haxell, Szabó and Tardos proved mcc2(G) ≤ 20000 for every graph G of maximum degree 5. We show that there are n-vertex 7-regular graphs G with mcc2(G)=Ω(n), and more sharply, for every ϵ > 0 there exists cϵ > 0 and n-vertex graphs of maximum degree 7, average degree at most 6 + ϵ for all subgraphs, and with mcc2(G) ≥ cϵn. For 6-regular graphs it is known only that the maximum order of magnitude of mcc2 is between and n.

We also offer a Ramsey-theoretic perspective of the quantity mcct(G).

Inequalities for martingales with bounded differences have recently proved to be very useful in combinatorics and in the mathematics of operational research and computer science. We see here that these inequalities extend in a natural way to ‘centering sequences’ with bounded differences, and thus include, for example, better inequalities for sequences related to sampling without replacement.

Given an r-graph F, an r-graph G is called weakly F-saturated if the edges missing from G can be added, one at a time, in some order, each extra edge creating a new copy of F. Let w-sat(n, F) be the minimal size of a weakly F-saturated graph of order n. We compute the w-sat function for a wide class of r-graphs called pyramids: these include many examples for which the w-sat function was known, as well as many new examples, such as the computation of w-sat(n,Ks + Kt), and enable us to prove a conjecture of Tuza.

Our main technique, developed from ideas of Kalai, is based on matroids derived from exterior algebra. We prove that if it succeeds for some graphs then the same is true for the ‘cones’ and ‘joins’ of such graphs, so that the w-sat function can be computed for many graphs that are built up from certain elementary graphs by these operations.

The branching random walk on a regular graph turns out to be particularly easy to analyse using results for the corresponding simple random walk. In this way, one can show that there is an intermediate phase of weak survival if and only if the graph is nonamenable. No such simple analysis holds more generally, and it is known that the nonamenability equivalence does not extend to general connected graphs of bounded degree (although we observe that it does hold for such graphs if the branching random walk is modified in a certain natural way). The most important general class of (bounded degree, connected) graphs for which it is thought that the equivalence may hold is that of quasi-transitive graphs: we show that this is indeed the case.