Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of $O(m^{3/4}\sqrt{\log m})$ vertices, and they conjectured that the bound of $O(\sqrt m)$ actually holds. We obtain separators with $O(\sqrt m \,\log m)$ vertices.

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 forest ℱ(n, M) chosen uniformly from the family of all labelled unrooted forests with n vertices and M edges is studied. We show that, like the Érdős-Rényi random graph G(n, M), the random forest exhibits three modes of asymptotic behaviour: subcritical, nearcritical and supercritical, with the phase transition at the point M = n/2. For each of the phases, we determine the limit distribution of the size of the k-th largest component of ℱ(n, M). The similarity to the random graph is far from being complete. For instance, in the supercritical phase, the giant tree in ℱ(n, M) grows roughly two times slower than the largest component of G(n, M) and the second largest tree in ℱ(n, M) is of the order n⅔ for every M = n/2 +s, provided that s3n−2 → ∞ and s = o(n), while its counterpart in G(n, M) is of the order n2s−2 log(s3n−2) ≪ n⅔.

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.

R. H. Schelp conjectured that if G is a graph with |V(G)| = R(Pn, Pn) such that δ(G) > , then in every 2-colouring of the edges of G there is a monochromatic Pn. In other words, the Ramsey number of a path does not change if the graph to be coloured is not complete but has large minimum degree.

Here we prove Ramsey-type results that imply the conjecture in a weakened form, first replacing the path by a matching, showing that the star-matching–matching Ramsey number satisfying R(Sn, nK2, nK2) = 3n − 1. This extends R(nK2, nK2) = 3n − 1, an old result of Cockayne and Lorimer. Then we extend this further from matchings to connected matchings, and outline how this implies Schelp's conjecture in an asymptotic sense through a standard application of the Regularity Lemma.

It is sad that we are unable to hear Dick Schelp's reaction to our work generated by his conjecture.

Let it(G) be the number of independent sets of size t in a graph G. Engbers and Galvin asked how large it(G) could be in graphs with minimum degree at least δ. They further conjectured that when n ⩾ 2δ and t ⩾ 3, it(G) is maximized by the complete bipartite graph Kδ,n−δ. This conjecture has recently drawn the attention of many researchers. In this short note, we prove this conjecture.

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

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 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.

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.

Let C(3)n denote the 3-uniform tight cycle, that is, the hypergraph with vertices v1, .–.–., vn and edges v1v2v3, v2v3v4, .–.–., vn−1vnv1, vnv1v2. We prove that the smallest integer N = N(n) for which every red–blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C(3)n is asymptotically equal to 4n/3 if n is divisible by 3, and 2n otherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.

In this paper, we study a statistical property of classes of real-valued functions that we call approximation from interpolated examples. We derive a characterization of function classes that have this property, in terms of their ‘fat-shattering function’, a notion that has proved useful in computational learning theory. The property is central to a problem of learning real-valued functions from random examples in which we require satisfactory performance from every algorithm that returns a function which approximately interpolates the training examples.

We propose an approach to analysing the asymptotic behaviour of Pólya urns based on the contraction method. For this, a new combinatorial discrete-time embedding of the evolution of the urn into random rooted trees is developed. A decomposition of these trees leads to a system of recursive distributional equations which capture the distributions of the numbers of balls of each colour. Ideas from the contraction method are used to study such systems of recursive distributional equations asymptotically. We apply our approach to a couple of concrete Pólya urns that lead to limit laws with normal limit distributions, with non-normal limit distributions and with asymptotic periodic distributional behaviour.

Let 3 ≤ k < n/2. We prove the analogue of the Erdős–Ko–Rado theorem for the random k-uniform hypergraph Gk(n, p) when k < (n/2)1/3; that is, we show that with probability tending to 1 as n → ∞, the maximum size of an intersecting subfamily of Gk(n, p) is the size of a maximum trivial family. The analogue of the Erdős–Ko–Rado theorem does not hold for all p when k ≫ n1/3.

We give quite precise results for k < n1/2−ϵ. For larger k we show that the random Erdős–Ko–Rado theorem holds as long as p is not too small, and fails to hold for a wide range of smaller values of p. Along the way, we prove that every non-trivial intersecting k-uniform hypergraph can be covered by k2 − k + 1 pairs, which is sharp as evidenced by projective planes. This improves upon a result of Sanders [7]. Several open questions remain.

We study the number of comparisons in Hoare's Find algorithm. Using trivariate generating functions, we get an explicit expression for the variance of the number of comparisons, if we search for the jth element in a random permutation of n elements. The variance is also asymptotically evaluated under the assumption that j is proportional to n. Similar results for the number of passes (recursive calls) are given, too.

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.

We study the conflict-free chromatic number χCF of graphs from extremal and probabilistic points of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdős–Rényi random graph G(n,p) and give the asymptotics for p = ω(1/n). We also show that for p ≥ 1/2 the conflict-free chromatic number differs from the domination number by at most 3.

There is a close relationship between biased graph games and random graph processes. In this paper, we develop the analogy and give further interesting instances.

The adaption of combinatorial duality to infinite graphs has been hampered by the fact that while cuts (or cocycles) can be infinite, cycles are finite. We show that these obstructions fall away when duality is reinterpreted on the basis of a ‘singular’ approach to graph homology, whose cycles are defined topologically in a space formed by the graph together with its ends and can be infinite. Our approach enables us to complete Thomassen's results about ‘finitary’ duality for infinite graphs to full duality, including his extensions of Whitney's theorem.

We determine lower bounds for the number of random binary vectors, chosen uniformly from vectors of weight k, needed to obtain a dependent set.