We prove that triangular configurations are plentiful in large subsets of Cartesian squares of finite quasirandom groups from classes having the quasirandom ultraproduct property, for example the class of finite simple groups. This is deduced from a strong double recurrence theorem for two commuting measure-preserving actions of a minimally almost periodic (not necessarily amenable or locally compact) group on a (not necessarily separable) probability space.

We consider the Widom–Rowlinson model of two types of interacting particles on d-regular graphs. We prove a tight upper bound on the occupancy fraction, the expected fraction of vertices occupied by a particle under a random configuration from the model. The upper bound is achieved uniquely by unions of complete graphs on d + 1 vertices, Kd+1. As a corollary we find that Kd+1 also maximizes the normalized partition function of the Widom–Rowlinson model over the class of d-regular graphs. A special case of this shows that the normalized number of homomorphisms from any d-regular graph G to the graph HWR, a path on three vertices with a loop on each vertex, is maximized by Kd+1. This proves a conjecture of Galvin.

A construction of Alon yields a sequence of highly pseudorandom triangle-free graphs with edge density significantly higher than one might expect from comparison with random graphs. We give an alternative construction for such graphs.

A graph G is H-saturated if it contains no copy of H as a subgraph but the addition of any new edge to G creates a copy of H. In this paper we are interested in the function satt(n,p), defined to be the minimum number of edges that a Kp-saturated graph on n vertices can have if it has minimum degree at least t. We prove that satt(n,p) = tn − O(1), where the limit is taken as n tends to infinity. This confirms a conjecture of Bollobás when p = 3. We also present constructions for graphs that give new upper bounds for satt(n,p).

For a given graph G of minimum degree at least k, let Gp denote the random spanning subgraph of G obtained by retaining each edge independently with probability p = p(k). We prove that if p ⩾ (logk + loglogk + ωk(1))/k, where ωk(1) is any function tending to infinity with k, then Gp asymptotically almost surely contains a cycle of length at least k + 1. When we take G to be the complete graph on k + 1 vertices, our theorem coincides with the classic result on the threshold probability for the existence of a Hamilton cycle in the binomial random graph.

Let G be an abelian group of cardinality n, where hcf(n, 6) = 1, and let A be a random subset of G. Form a graph ΓA on vertex set G by joining x to y if and only if x + y ∈ A. Then, with high probability as n → ∞, the chromatic number χ(ΓA) is at most $(1 + o(1))\tfrac{n}{2\log_2 n}$. This is asymptotically sharp when G = ℤ/nℤ, n prime.

Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. Let k ≥ 2 be an integer and let G be a hypergraph with mi edges of size i for i=1,2. Bollobás and Scott conjectured that G has a partition into k classes, each of which contains at most $m_1/k+m_2/k^2+O(\sqrt{m_1+m_2})$ edges. In this paper, we confirm the conjecture affirmatively by showing that G has a partition into k classes, each of which contains at most

$$m_1/k+m_2/k^2+\ffrac{k-1}{2k^2}\sqrt{2(km_1+m_2)}+O(1)$$.

Classical ergodic theory for integer-group actions uses entropy as a complete invariant for isomorphism of IID (independent, identically distributed) processes (a.k.a. product measures). This theory holds for amenable groups as well. Despite recent spectacular progress of Bowen, the situation for non-amenable groups, including free groups, is still largely mysterious. We present some illustrative results and open questions on free groups, which are particularly interesting in combinatorics, statistical physics and probability. Our results include bounds on minimum and maximum bisection for random cubic graphs that improve on all past bounds.

We study the lower tail large deviation problem for subgraph counts in a random graph. Let XH denote the number of copies of H in an Erdős–Rényi random graph $\mathcal{G}(n,p)$. We are interested in estimating the lower tail probability $\mathbb{P}(X_H \le (1-\delta) \mathbb{E} X_H)$ for fixed 0 < δ < 1.

Thanks to the results of Chatterjee, Dembo and Varadhan, this large deviation problem has been reduced to a natural variational problem over graphons, at least for p ≥ n−αH (and conjecturally for a larger range of p). We study this variational problem and provide a partial characterization of the so-called ‘replica symmetric’ phase. Informally, our main result says that for every H, and 0 < δ < δH for some δH > 0, as p → 0 slowly, the main contribution to the lower tail probability comes from Erdős–Rényi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartite H and δ close to 1.