We provide a framework for online conflict-free colouring of any hypergraph. We introduce the notion of a degenerate hypergraph, which characterizes hypergraphs that arise in geometry. We use our framework to obtain an efficient randomized online algorithm for conflict-free colouring of any k-degenerate hypergraph with n vertices. Our algorithm uses O(k log n) colours with high probability and this bound is asymptotically optimal. Moreover, our algorithm uses O(k log k log n) random bits with high probability. We introduce algorithms that are allowed to perform a few recolourings of already coloured points. We provide deterministic online conflict-free colouring algorithms for points on the line with respect to intervals and for points on the plane with respect to half-planes (or unit disks) that use O(log n) colours and perform a total of at most O(n) recolourings.

The aim of this paper is to prove a Turán-type theorem for random graphs. For $\gamma >0$ and graphs $G$ and $H$, write $G\to_\gamma H$ if any $\gamma$-proportion of the edges of $G$ spans at least one copy of $H$ in $G$. We show that for every graph $H$ and every fixed real $\delta>0$, almost every graph $G$ in the binomial random graph model $\cG(n,q)$, with $q=q(n)\gg((\log n)^4/n)^{1/d(H)}$, satisfies $G\to_{(\chi(H)-2)/(\chi(H)-1)+\delta}H$, where as usual $\chi(H)$ denotes the chromatic number of $H$ and $d(H)$ is the ‘degeneracy number’ of $H$.

Since $K_l$, the complete graph on $l$ vertices, is $l$-chromatic and $(l-1)$-degenerate, we infer that for every $l\geq2$ and every fixed real $\delta>0$, almost every graph $G$ in the binomial random graph model $\cG(n,q)$, with $q=q(n)\gg((\log n)^4/n)^{1/(l-1)}$, satisfies $G\to_{(l-2)/(l-1)+\delta}K_l$.

We define ${\mathcal B}_n$ to be the set of $n$-tuples of the form $(a_0, {\ldots}\,, a_{n-1})$ where $a_j = \pm 1$. If $A \in {\mathcal B}_n$, then we call $A$ a binary sequence and define the autocorrelations of $A$ by $c_k := \sum_{j=0}^{n-k-1} a_j a_{j+k}$ for $0 \leq k \leq n-1$. The problem of finding binary sequences with autocorrelations ‘near zero’ has arisen in communications engineering and is also relevant to conjectures of Littlewood and Erdős on ‘flat’ polynomials with $\pm 1$ coefficients. Following Turyn, we define \[ b(n) := \min_{A \in {\mathcal B}_n} \max_{1 \leq k \leq n-1} |c_k|.\] The purpose of this article is to show that, using some known techniques from discrete probability, we can improve upon the best upper bound on $b(n)$ appearing in the previous literature, and we can obtain both asymptotic and exact expressions for the expected value of $c_k^m$ if the $a_j$ are independent $\pm 1$ random variables with mean 0. We also include some brief heuristic remarks in support of the unproved conjecture that $b(n) = O(\sqrt{n})$.

We model a problem about networks built from wireless devices using identifying and locating–dominating codes in unit disk graphs. It is known that minimizing the size of an identifying code is -complete even for bipartite graphs. First, we improve this result by showing that the problem remains -complete for bipartite planar unit disk graphs. Then, we address the question of the existence of an identifying code for random unit disk graphs. We derive the probability that there exists an identifying code as a function of the radius of the disks, and we find that for all interesting ranges of r this probability is bounded away from one. The results obtained are in sharp contrast to those concerning random graphs in the Erdős–Rényi model. Another well-studied class of codes is that of locating–dominating codes, which are less demanding than identifying codes. A locating–dominating code always exists, but minimizing its size is still -complete in general. We extend this result to our setting by showing that this question remains -complete for arbitrary planar unit disk graphs. Finally, we study the minimum size of such a code in random unit disk graphs, and we prove that with probability tending to one, it is of size (n/r)2/3+o(1) if r ≤ /2−ϵ is chosen such that nr2 → ∞, and of size n1+o(1) if nr2 ≪ lnn.

We consider random graphs with a fixed degree sequence. Molloy and Reed [11, 12] studied how the size of the giant component changes according to degree conditions. They showed that there is a phase transition and investigated the order of components before and after the critical phase. In this paper we study more closely the order of components at the critical phase, using singularity analysis of a generating function for a branching process which models the random graph with a given degree sequence.

There are several known results asserting that undirected graphs can be partitioned in a way that satisfies various constraints imposed on the degrees. The corresponding results for directed graphs, where degrees are replaced by outdegrees, often fail, and when they do hold, they are usually much harder, and lead to fascinating open problems. In this note we list three problems of this type, and mention the undirected analogues. All graphs and digraphs considered here are simple, that is, they have no loops and no multiple edges.

The game colouring number gcol(G) of a graph G is the least k such that, if two players take turns choosing the vertices of a graph, then either of them can ensure that every vertex has fewer than k neighbours chosen before it, regardless of what choices the other player makes. Clearly gcol(G) ≤ Δ(G)+1. Sauer and Spencer [20] proved that if two graphs G1 and G2 on n vertices satisfy 2Δ(G1)Δ(G2) < n then they pack, i.e., there is an embedding of G1 into the complement of G2. We improve this by showing that if (gcol(G1)−1)Δ(G2)+(gcol(G2)−1)Δ(G1) < n then G1 and G2 pack. To our knowledge this is the first application of colouring games to a non-game problem.

For every integer N, we explicitly construct a subset of residues mod N of size(log N)o(1) which is nearly uniformly distributed in every arithmetic progression modulo N.

Building on the methods developed in joint work with Béla Bollobás and Svante Janson, we study the phase transition in four ‘scale-free’ random graph models, obtaining upper and lower bounds on the size of the giant component when there is one. In particular, we determine the extremely slow rate of growth of the giant component just above the phase transition. We greatly reduce the significant gaps between the existing upper and lower bounds, giving bounds that match to within a factor $1+o(1)$ in the exponent.

In all cases the method used is to couple the neighbourhood expansion process in the graph on n vertices with a continuous-type branching process that is independent of n. It can be shown (requiring some separate argument for each case) that with probability tending to 1 as $n\to\infty$ the size of the giant component divided by n is within $o(1)$ of the survival probability $\sigma$ of the branching process. This survival probability is given in terms of the maximal solution $\phi$ to certain non-linear integral equations, which can be written in the form $\phi={\bf F}(\phi)$ for a certain operator ${\bf F}$. Upper and lower bounds are found by constructing trial functions $\phi_0$, $\phi_1$ with ${\bf F}(\phi_0)\leq \phi_0$ and ${\bf F}(\phi_1)\geq \phi_1$ holding pointwise; basic properties of branching processes then imply that $\phi_1\leq \phi\leq \phi_0$, giving upper and lower bounds on $\sigma$.

Let d = (d1, d2, . . ., dn) be a vector of non-negative integers with even sum. We prove some basic facts about the structure of a random graph with degree sequence d, including the probability of a given subgraph or induced subgraph.

Although there are many results of this kind, they are restricted to the sparse case with only a few exceptions. Our focus is instead on the case where the average degree is approximately a constant fraction of n.

Our approach is the multidimensional saddle-point method. This extends the enumerative work of McKay and Wormald (1990) and is analogous to the theory developed for bipartite graphs by Greenhill and McKay (2009).

Let [n]r be the complete r-partite hypergraph with vertex classes of size n. It is an easy exercise to show that every set of more than (k−1)nr−1 edges in [n]r contains a matching of size k. We conjecture the following rainbow version of this observation: if F1,F2,. . .,Fk ⊆ [n]r are of size larger than (k−1)nr−1 then there exists a rainbow matching, that is, a choice of disjoint edges fi ∈ Fi. We prove this conjecture for r=2 and r=3.

Let $p_c({\mathbb Q}_n)$ and $p_c({\mathbb Z}^n)$ denote the critical values for nearest-neighbour bond percolation on the $n$-cube ${\mathbb Q}_n = \{0,1\}^n$ and on ${\mathbb Z}^n$, respectively. Let $\Omega = n$ for ${\mathbb G} = {\mathbb Q}_n$ and $\Omega = 2n$ for ${\mathbb G} = {\mathbb Z}^n$ denote the degree of ${\mathbb G}$. We use the lace expansion to prove that for both ${\mathbb G} = {\mathbb Q}_n$ and ${\mathbb G} = {\mathbb Z}^n$, \[p_c({\mathbb G}) = \Omega^{-1} + \Omega^{-2} + \frac{7}{2} \Omega^{-3} + O(\Omega^{-4}).\] This extends by two terms the result $p_c({\mathbb Q}_n) = \Omega^{-1} + O(\Omega^{-2})$ of Borgs, Chayes, van der Hofstad, Slade and Spencer, and provides a simplified proof of a previous result of Hara and Slade for ${\mathbb Z}^n$.

A graph on n vertices is ε-far from a property $\mathcal{P}$ if one has to add or delete from it at least εn2 edges to get a graph satisfying $\mathcal{P}$. A graph property $\mathcal{P}$ is strongly testable if for every fixed ε > 0 it is possible to distinguish, with one-sided error, between graphs satisfying $\mathcal{P}$ and ones that are ε-far from $\mathcal{P}$ by inspecting the induced subgraph on a random subset of at most f(ε) vertices. A property is easily testable if it is strongly testable and the function f is polynomial in 1/ε, otherwise it is hard. We consider the problem of characterizing the easily testable graph properties, which is wide open, and obtain several results in its study. One of our main results shows that testing perfectness is hard. The proof shows that testing perfectness is at least as hard as testing triangle-freeness, which is hard. On the other hand, we show that being a cograph, or equivalently, induced P3-freeness where P3 is a path with 3 edges, is easily testable. This settles one of the two exceptional graphs, the other being C4 (and its complement), left open in the characterization by the first author and Shapira of graphs H for which induced H-freeness is easily testable. Our techniques yield a few additional related results, but the problem of characterizing all easily testable graph properties, or even that of formulating a plausible conjectured characterization, remains open.

Using various results from extremal set theory (interpreted in the language of additive combinatorics), we prove an asymptotically sharp version of Freiman's theorem in : if is a set for which |A + A| ≤ K|A| then A is contained in a subspace of size ; except for the error, this is best possible. If in addition we assume that A is a downset, then we can also cover A by O(K46) translates of a coordinate subspace of size at most |A|, thereby verifying the so-called polynomial Freiman–Ruzsa conjecture in this case. A common theme in the arguments is the use of compression techniques. These have long been familiar in extremal set theory, but have been used only rarely in the additive combinatorics literature.

It is shown that an oriented graph of order n whose every indegree and outdegree is at least cn is hamiltonian if c ≥ ½ − 2−15 but need not be if c < ⅜.

We present a method for obtaining upper bounds for the connective constant of self-avoiding walks. The method works for a large class of lattices, including all that have been studied in connection with self-avoiding walks. The bound is obtained as the largest eigenvalue of a certain matrix. Numerical application of the method has given improved bounds for all lattices studied, e.g. μ < 2.696 for the square lattice, μ < 4.278 for the triangular lattice and μ < 4.756 for the simple cubic lattice.

A rainbow subgraph of an edge-coloured graph is a subgraph whose edges have distinct colours. The colour degree of a vertex v is the number of different colours on edges incident with v. Wang and Li conjectured that for k ≥ 4, every edge-coloured graph with minimum colour degree k contains a rainbow matching of size at least ⌈k/2⌉. A properly edge-coloured K4 has no such matching, which motivates the restriction k ≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full.

We show that all maximum length paths in a connected circular arc graph have non-empty intersection.

We elucidate the close connection between the repulsive lattice gas in equilibrium statistical mechanics and the Lovász Local Lemma in probabilistic combinatorics. We show that the conclusion of the Lovász Local Lemma holds for dependency graph $G$ and probabilities $\{p_x\}$ if and only if the independent-set polynomial for $G$ is nonvanishing in the polydisc of radii $\{p_x\}$. Furthermore, we show that the usual proof of the Lovász Local Lemma – which provides a sufficient condition for this to occur – corresponds to a simple inductive argument for the nonvanishing of the independent-set polynomial in a polydisc, which was discovered implicitly by Shearer [28] and explicitly by Dobrushin [12, 13]. We also present a generalization of the Lovász Local Lemma that allows for ‘soft’ dependencies. The paper aims to provide an accessible discussion of these results, which are drawn from a longer paper [26] that has appeared elsewhere.

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.