We show that, for each fixed k, an n-vertex graph not containing a cycle of length 2k has at most $80\sqrt{k\log k}\cdot n^{1+1/k}+O(n)$ edges.

Answering a question by Angel, Holroyd, Martin, Wilson and Winkler [1], we show that the maximal number of non-colliding coupled simple random walks on the complete graph KN, which take turns, moving one at a time, is monotone in N. We use this fact to couple [N/4] such walks on KN, improving the previous Ω(N/log N) lower bound of Angel et al. We also introduce a new generalization of simple avoidance coupling which we call partially ordered simple avoidance coupling, and provide a monotonicity result for this extension as well.

We consider a random permutation drawn from the set of 132-avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by nλ(σ)/2, where λ(σ) is the length of σ plus the number of descents. The limit is not normal, and can be expressed as a functional of a Brownian excursion. Moments can be found by recursion.

We say a graph is (Qn,Qm)-saturated if it is a maximal Qm-free subgraph of the n-dimensional hypercube Qn. A graph is said to be (Qn,Qm)-semi-saturated if it is a subgraph of Qn and adding any edge forms a new copy of Qm. The minimum number of edges a (Qn,Qm)-saturated graph (respectively (Qn,Qm)-semi-saturated graph) can have is denoted by sat(Qn,Qm) (respectively s-sat(Qn,Qm)). We prove that

$$ \begin{linenomath} \lim_{n\to\infty}\ffrac{\sat(Q_n,Q_m)}{e(Q_n)}=0, \end{linenomath}$$

$$ \begin{linenomath} \ssat(Q_n,Q_m)\geq \ffrac{m+1}{2}\cdot 2^n, \end{linenomath}$$

Let Dk denote the tournament on 3k vertices consisting of three disjoint vertex classes V1, V2 and V3 of size k, each oriented as a transitive subtournament, and with edges directed from V1 to V2, from V2 to V3 and from V3 to V1. Fox and Sudakov proved that given a natural number k and ε > 0, there is n0(k, ε) such that every tournament of order n ⩾ n0(k,ε) which is ε-far from being transitive contains Dk as a subtournament. Their proof showed that $n_0(k,\epsilon ) \leq \epsilon ^{-O(k/\epsilon ^2)}$ and they conjectured that this could be reduced to n0(k, ε) ⩽ ε−O(k). Here we prove this conjecture.

Let Qd denote the hypercube of dimension d. Given d ⩾ m, a spanning subgraph G of Qd is said to be (Qd, Qm)-saturated if it does not contain Qm as a subgraph but adding any edge of E(Qd)\E(G) creates a copy of Qm in G. Answering a question of Johnson and Pinto [27], we show that for every fixed m ⩾ 2 the minimum number of edges in a (Qd, Qm)-saturated graph is Θ(2d).

We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of Qd is said to be weakly (Qd, Qm)-saturated if the edges of E(Qd)\E(G) can be added to G one at a time so that each added edge creates a new copy of Qm. Answering another question of Johnson and Pinto [27], we determine the minimum number of edges in a weakly (Qd, Qm)-saturated graph for all d ⩾ m ⩾ 1. More generally, we determine the minimum number of edges in a subgraph of the d-dimensional grid Pkd which is weakly saturated with respect to ‘axis aligned’ copies of a smaller grid Prm. We also study weak saturation of cycles in the grid.

Let S be a set of n points in ${\mathbb R}^{2}$ contained in an algebraic curve C of degree d. We prove that the number of distinct distances determined by S is at least cdn4/3, unless C contains a line or a circle.

We also prove the lower bound cd′ min{m2/3n2/3, m2, n2} for the number of distinct distances between m points on one irreducible plane algebraic curve and n points on another, unless the two curves are parallel lines, orthogonal lines, or concentric circles. This generalizes a result on distances between lines of Sharir, Sheffer and Solymosi in [19].

We show that certain topologically defined uniform spanning tree probabilities for graphs embedded in an annulus can be computed as linear combinations of Pfaffians of matrices involving the line-bundle Green's function, where the coefficients count cover-inclusive Dyck tilings of skew Young diagrams.

We consider the problem of minimizing the number of triangles in a graph of given order and size, and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.