We investigate decompositions of a graph into a small number of low-diameter subgraphs. Let P(n, ε, d) be the smallest k such that every graph G = (V, E) on n vertices has an edge partition E = E0 ∪ E1 ∪ ⋅⋅⋅ ∪ Ek such that |E0| ≤ εn2, and for all 1 ≤ i ≤ k the diameter of the subgraph spanned by Ei is at most d. Using Szemerédi's regularity lemma, Polcyn and Ruciński showed that P(n, ε, 4) is bounded above by a constant depending only on ε. This shows that every dense graph can be partitioned into a small number of ‘small worlds’ provided that a few edges can be ignored. Improving on their result, we determine P(n, ε, d) within an absolute constant factor, showing that P(n, ε, 2) = Θ(n) is unbounded for ε < 1/4, P(n, ε, 3) = Θ(1/ε2) for ε > n−1/2 and P(n, ε, 4) = Θ(1/ε) for ε > n−1. We also prove that if G has large minimum degree, all the edges of G can be covered by a small number of low-diameter subgraphs. Finally, we extend some of these results to hypergraphs, improving earlier work of Polcyn, Rödl, Ruciński and Szemerédi.

In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on [n] = {1,2,. . .,n} with m edges, whenever n and the nullity m−n+1 tend to infinity. Let Cr(n,t) be the number of connected r-uniform hypergraphs on [n] with nullity t = (r−1)m−n+1, where m is the number of edges. For r ≥ 3, asymptotic formulae for Cr(n,t) are known only for partial ranges of the parameters: in 1997 Karoński and Łuczak gave one for t = o(log n/log log n), and recently Behrisch, Coja-Oghlan and Kang gave one for t=Θ(n). Here we prove such a formula for any fixed r ≥ 3 and any t = t(n) satisfying t = o(n) and t→∞ as n→∞, complementing the last result. This leaves open only the case t/n→∞, which we expect to be much simpler, and will consider in future work. The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. We deduce this from the corresponding central limit theorem by smoothing techniques.

Denote by ${\mathcal H}_k$(n, p) the random k-graph in which each k-subset of {1,. . .,n} is present with probability p, independent of other choices. More or less answering a question of Balogh, Bohman and Mubayi, we show: there is a fixed ε > 0 such that if n = 2k + 1 and p > 1 - ε, then w.h.p. (that is, with probability tending to 1 as k → ∞), ${\mathcal H}_k$(n, p) has the ‘Erdős–Ko–Rado property’. We also mention a similar random version of Sperner's theorem.

Let $P=(X,\le)$ be a finite partially ordered set. That is, $X$ is a finite ground set and $\le$ is a partial ordering on $X$ (a reflexive, transitive, and weakly antisymmetric relation). An $x\in X$ is an immediate predecessor of a $y\in X$ if $x<y$ and there is no $z\in X$ with $x<z<y$ (where $x<y$ means that $x\le y$ and $x\ne y$). The Hasse diagram$H(P)$ is the undirected graph with vertex set $X$ and with $\{x,y\}$ forming an edge if $x$ is an immediate predecessor of $y$ or if $y$ is an immediate predecessor of $x$. We denote bya $\alpha(H(P))$ the independence number of the Hasse diagram, that is, the maximum possible size of a subset $I\subseteq X$ such that no element of $I$ is an immediate predecessor (in $P$) of another element of $I$. This quantity should not be confused with the maximum size of an antichain in $P$, which is sometimes denoted by $\alpha(P)$.

Magnant and Martin conjectured that the vertex set of any d-regular graph G on n vertices can be partitioned into $n / (d+1)$ paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when $d = \Omega(n)$ , improving a result of Han, who showed that in this range almost all vertices of G can be covered by $n / (d+1) + 1$ vertex-disjoint paths. In fact our proof gives a partition of V(G) into cycles. We also show that, if $d = \Omega(n)$ and G is bipartite, then V(G) can be partitioned into n/(2d) paths (this bound is tight for bipartite graphs).

Assume that the edges of the complete graph Kn are given independent uniform [0, 1] weights. We consider the expected minimum total weight μk of k ⩽ 2 edge-disjoint spanning trees. When k is large we show that μk ≈ k2. Most of the paper is concerned with the case k = 2. We show that m2 tends to an explicitly defined constant and that μ2 ≈ 4.1704288. . . .

We study structural properties of graphs with bounded clique number and high minimum degree. In particular, we show that there exists a function L = L(r,ɛ) such that every Kr-free graph G on n vertices with minimum degree at least ((2r–5)/(2r–3)+ɛ)n is homomorphic to a Kr-free graph on at most L vertices. It is known that the required minimum degree condition is approximately best possible for this result.

For r = 3 this result was obtained by Łuczak (2006) and, more recently, Goddard and Lyle (2011) deduced the general case from Łuczak’s result. Łuczak’s proof was based on an application of Szemerédi’s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on L(3, ɛ). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for L(r, ɛ) that is doubly exponential in poly(ɛ).

We show that recognizing the K3-freeness and K4-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols using exponentially many partitions and for nondeterministic syntactic read-r times branching programs.

The key ingredient is a generalization of a colouring lemma, due to Papadimitriou and Sipser, which says that for every balanced red—blue colouring of the edges of the complete n-vertex graph there is a set of εn2 triangles, none of which is monochromatic, such that no triangle can be formed by picking edges from different triangles. We extend this lemma to exponentially many colourings and to partial colourings.

We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical circuits: it uses clique embeddings to produce lower bounds on λ2 and star embeddings to produce lower bounds on the smallest Rayleigh quotient when there is a zero Dirichlet boundary condition. The method assigns priorities to the paths in the embedding; we show that, for an unweighted tree T, using uniform priorities for a clique embedding produces a lower bound on λ2 that is off by at most an O(log diameter(T)) factor. We show that the best bounds this method can produce for clique embeddings are the same as for a related method that uses clique embeddings and edge lengths to produce bounds.

There was an incorrect argument in the proof of the main theorem in ‘On percolation and the bunkbed conjecture’, in Combin. Probab. Comput. (2011) 20 103–117 doi: 10.1017/S0963548309990666. I thus no longer claim to have a proof for the bunkbed conjecture for outerplanar graphs.

We present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $\hat{R}_{\mathrm{ind}}(P_n)\leq 5 \cdot 10^7n$ , thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and Łuczak. We also provide a bound for the k-colour version, showing that $\hat{R}_{\mathrm{ind}}^k(P_n)=O(k^3\log^4k)n$ . Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,\frac{1+\varepsilon}{n})$ , contains typically an induced path of length $\Theta(\varepsilon^2) n$ .

A set of points in d-dimensional Euclidean space is almost equidistant if, among any three points of the set, some two are at distance 1. We show that an almost-equidistant set in ℝd has cardinality O(d4/3).

We prove Bogolyubov–Ruzsa-type results for finite subsets of groups with small tripling, |A3| ≤ O(|A|), or small alternation, |AA−1A| ≤ O(|A|). As applications, we obtain a qualitative analogue of Bogolyubov’s lemma for dense sets in arbitrary finite groups, as well as a quantitative arithmetic regularity lemma for sets of bounded VC-dimension in finite groups of bounded exponent. The latter result generalizes the abelian case, due to Alon, Fox and Zhao, and gives a quantitative version of previous work of the author, Pillay and Terry.

The core of a graph G is the subgraph GΔ induced by the vertices of maximum degree. We define the deleted core D(G) of G. We extend an earlier sufficient condition due to Hoffman [7] for a graph H to be the core of a Class 2 graph, and thereby provide a stronger sufficient condition. The new sufficient condition is in terms of D(H). We show that in some circumstances our condition is necessary; but it is not necessary in general.

We show that, for a constant-degree algebraic curve γ in ℝD, every set of n points on γ spans at least Ω(n4/3) distinct distances, unless γ is an algebraic helix, in the sense of Charalambides [2]. This improves the earlier bound Ω(n5/4) of Charalambides [2].

We also show that, for every set P of n points that lie on a d-dimensional constant-degree algebraic variety V in ℝD, there exists a subset S ⊂ P of size at least Ω(n4/(9+12(d−1))), such that S spans $\left({\begin{array}{*{20}{c}} {|S|} \\ 2 \\\end{array}} \right)$ distinct distances. This improves the earlier bound of Ω(n1/(3d)) of Conlon, Fox, Gasarch, Harris, Ulrich and Zbarsky [4].

Both results are consequences of a common technical tool.

Let [Mscr ]n,k(S) be the set of n-edge k-vertex rooted maps in some class on the surface S. Let P be a planar map in the class. We develop a method for showing that almost all maps in [Mscr ]n,k(S) contain many copies of P. One consequence of this is that almost all maps in [Mscr ]n,k(S) have no symmetries. The classes considered include c-connected maps (c [les ] 3) and certain families of degree restricted maps.

Given a finite set $A \subseteq \mathbb{R}^d$, points $a_1,a_2,\dotsc,a_{\ell} \in A$ form an $\ell$-hole in A if they are the vertices of a convex polytope, which contains no points of A in its interior. We construct arbitrarily large point sets in general position in $\mathbb{R}^d$ having no holes of size $O(4^dd\log d)$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. The basic version of our construction uses a certain type of equidistributed point sets, originating from numerical analysis, known as (t,m,s)-nets or (t,s)-sequences, yielding a bound of $2^{7d}$. The better bound is obtained using a variant of (t,m,s)-nets, obeying a relaxed equidistribution condition.

Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M(c, n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M(c, n) makes the transition from o(n) to Ω(n) around some critical value c(0), which can be specified in terms of a fixed point of a mapping on probability distributions.

In this paper we introduce some Christoffel–Darboux type identities for independence polynomials. As an application, we give a new proof of a theorem of Chudnovsky and Seymour, which states that the independence polynomial of a claw-free graph has only real roots. Another application is related to a conjecture of Merrifield and Simmons.

We prove a number of results related to a problem of Po-Shen Loh [9], which is equivalent to a problem in Ramsey theory. Let a = (a1, a2, a3) and b = (b1, b2, b3) be two triples of integers. Define a to be 2-less than b if ai < bi for at least two values of i, and define a sequence a1, …, am of triples to be 2-increasing if ar is 2-less than as whenever r < s. Loh asks how long a 2-increasing sequence can be if all the triples take values in {1, 2, …, n}, and gives a log* improvement over the trivial upper bound of n2 by using the triangle removal lemma. In the other direction, a simple construction gives a lower bound of n3/2. We look at this problem and a collection of generalizations, improving some of the known bounds, pointing out connections to other well-known problems in extremal combinatorics, and asking a number of further questions.