We prove an essentially sharp $\tilde \Omega (n/k)$ lower bound on the k-round distributional complexity of the k-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson’s $\tilde \Omega (n/{k^2})$ lower bound, and essentially matches the randomized lower bound proved by Klauck. The proof is information-theoretic, and a key part of it is using asymmetric triangular discrimination instead of total variation distance; this idea may be useful elsewhere.

We prove that, with high probability, in every 2-edge-colouring of the random tournament on n vertices there is a monochromatic copy of every oriented tree of order $O(n{\rm{/}}\sqrt {{\rm{log}} \ n} )$. This generalizes a result of the first, third and fourth authors, who proved the same statement for paths, and is tight up to a constant factor.

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(ɛ).

The inducibility of a graph H measures the maximum number of induced copies of H a large graph G can have. Generalizing this notion, we study how many induced subgraphs of fixed order k and size ℓ a large graph G on n vertices can have. Clearly, this number is $\left( {\matrix{n \cr k}}\right)$ for every n, k and $\ell \in \left\{ {0,\left( {\matrix{k \cr 2}} \right)}\right\}$. We conjecture that for every n, k and $0 \lt \ell \lt \left( {\matrix{k \cr 2}}\right)$ this number is at most $ (1/e + {o_k}(1)) {\left( {\matrix{n \cr k}} \right)}$. If true, this would be tight for ℓ ∈ {1, k − 1}.

In support of our ‘Edge-statistics Conjecture’, we prove that the corresponding density is bounded away from 1 by an absolute constant. Furthermore, for various ranges of the values of ℓ we establish stronger bounds. In particular, we prove that for ‘almost all’ pairs (k, ℓ) only a polynomially small fraction of the k-subsets of V(G) have exactly ℓ edges, and prove an upper bound of $ (1/2 + {o_k}(1)){\left( {\matrix{n \cr k}}\right)}$ for ℓ = 1.

Our proof methods involve probabilistic tools, such as anti-concentration results relying on fourth moment estimates and Brun’s sieve, as well as graph-theoretic and combinatorial arguments such as Zykov’s symmetrization, Sperner’s theorem and various counting techniques.

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.

In an earlier paper, the present authors (2015) introduced the altermatic number of graphs and used Tucker’s lemma, an equivalent combinatorial version of the Borsuk–Ulam theorem, to prove that the altermatic number is a lower bound for chromatic number. A matching Kneser graph is a graph whose vertex set consists of all matchings of a specified size in a host graph and two vertices are adjacent if their corresponding matchings are edge-disjoint. Some well-known families of graphs such as Kneser graphs, Schrijver graphs and permutation graphs can be represented by matching Kneser graphs. In this paper, unifying and generalizing some earlier works by Lovász (1978) and Schrijver (1978), we determine the chromatic number of a large family of matching Kneser graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching Kneser graphs in terms of the generalized Turán number of matchings.

Given graphs H1, H2, a graph G is (H1, H2) -Ramsey if, for every colouring of the edges of G with red and blue, there is a red copy of H1 or a blue copy of H2. In this paper we investigate Ramsey questions in the setting of randomly perturbed graphs. This is a random graph model introduced by Bohman, Frieze and Martin [8] in which one starts with a dense graph and then adds a given number of random edges to it. The study of Ramsey properties of randomly perturbed graphs was initiated by Krivelevich, Sudakov and Tetali [30] in 2006; they determined how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (K3, Kt) -Ramsey (for t ≽ 3). They also raised the question of generalizing this result to pairs of graphs other than (K3, Kt). We make significant progress on this question, giving a precise solution in the case when H1 = Ks and H2 = Kt where s, t ≽ 5. Although we again show that one requires polynomially fewer edges than in the purely random graph, our result shows that the problem in this case is quite different to the (K3, Kt) -Ramsey question. Moreover, we give bounds for the corresponding (K4, Kt) -Ramsey question; together with a construction of Powierski [37] this resolves the (K4, K4) -Ramsey problem.

We also give a precise solution to the analogous question in the case when both H1 = Cs and H2 = Ct are cycles. Additionally we consider the corresponding multicolour problem. Our final result gives another generalization of the Krivelevich, Sudakov and Tetali [30] result. Specifically, we determine how many random edges must be added to a dense graph to ensure the resulting graph is with high probability (Cs, Kt) -Ramsey (for odd s ≽ 5 and t ≽ 4).

To prove our results we combine a mixture of approaches, employing the container method, the regularity method as well as dependent random choice, and apply robust extensions of recent asymmetric random Ramsey results.

Given a graph G and a bijection f : E(G) → {1, 2,…,e(G)}, we say that a trail/path in G is f-increasing if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chvátal and Komlós raised the question of providing worst-case estimates of the length of the longest increasing trail/path over all edge orderings of Kn. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is n-1, and the case of a path is still wide open. Recently Lavrov and Loh proposed studying the average-case version of this problem, in which the edge ordering is chosen uniformly at random. They conjectured (and Martinsson later proved) that such an ordering with high probability (w.h.p.) contains an increasing Hamilton path.

In this paper we consider the random graph G = Gn,p with an edge ordering chosen uniformly at random. In this setting we determine w.h.p. the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average-case version of the result of Graham and Kleitman, showing that the random edge ordering of Kn has w.h.p. an increasing trail of length (1-o(1))en, and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erdős-Renyi graphs with p = o(1).

For a rumour spreading protocol, the spread time is defined as the first time everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O({n^{1/3}}{\log ^{2/3}}n)$. This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari and Woelfel (2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph. We also show that if, for a pair α, β of real numbers, there exist infinitely many graphs for which the two spread times are nα and nβ in expectation, then $0 \le \alpha \le 1$ and $\alpha \le \beta \le {1 \over 3} + {2 \over 3} \alpha $; and we show each such pair α, β is achievable.

Random constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark examples for algorithms, and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution (Krzakala et al. 2007, Proc. Nat. Acad. Sci.), physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications for Bayesian inference tasks, a subject that has received a great deal of interest recently (e.g. Banks et al. 2016, Proc. 29th COLT).

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.

The theta graph ${\Theta _{\ell ,t}}$ consists of two vertices joined by t vertex-disjoint paths, each of length $\ell $ . For fixed odd $\ell $ and large t, we show that the largest graph not containing ${\Theta _{\ell ,t}}$ has at most ${c_\ell }{t^{1 - 1/\ell }}{n^{1 + 1/\ell }}$ edges and that this is tight apart from the value of ${c_\ell }$ .

The maximum size of an r-uniform hypergraph without a Berge cycle of length at least k has been determined for all k ≥ r + 3 by Füredi, Kostochka and Luo and for k < r (and k = r, asymptotically) by Kostochka and Luo. In this paper we settle the remaining cases: k = r + 1 and k = r + 2, proving a conjecture of Füredi, Kostochka and Luo.

We prove that, for q odd, a set of q + 2 points in the projective plane over the field with q elements has at least 2q − c odd secants, where c is a constant and an odd secant is a line incident with an odd number of points of the set.

In this paper we develop an in-depth analysis of non-reversible Markov chains on denumerable state space from a similarity orbit perspective. In particular, we study the class of Markov chains whose transition kernel is in the similarity orbit of a normal transition kernel, such as that of birth–death chains or reversible Markov chains. We start by identifying a set of sufficient conditions for a Markov chain to belong to the similarity orbit of a birth–death chain. As by-products, we obtain a spectral representation in terms of non-self-adjoint resolutions of identity in the sense of Dunford [21] and offer a detailed analysis on the convergence rate, separation cutoff and L2-cutoff of this class of non-reversible Markov chains. We also look into the problem of estimating the integral functionals from discrete observations for this class. In the last part of this paper we investigate a particular similarity orbit of reversible Markov kernels, which we call the pure birth orbit, and analyse various possibly non-reversible variants of classical birth–death processes in this orbit.

A set of graphs are called cospectral if their adjacency matrices have the same characteristic polynomial. In this paper we introduce a simple method for constructing infinite families of cospectral regular graphs. The construction is valid for special cases of a property introduced by Schwenk. For the case of cubic (3-regular) graphs, computational results are given which show that the construction generates a large proportion of the cubic graphs, which are cospectral with another cubic graph.

The Friedgut–Kalai–Naor (FKN) theorem states that if ƒ is a Boolean function on the Boolean cube which is close to degree one, then ƒ is close to a dictator, a function depending on a single coordinate. The author has extended the theorem to the slice, the subset of the Boolean cube consisting of all vectors with fixed Hamming weight. We extend the theorem further, to the multislice, a multicoloured version of the slice.

As an application, we prove a stability version of the edge-isoperimetric inequality for settings of parameters in which the optimal set is a dictator.

A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect matching which is ‘pseudorandom’, meaning that, for instance, the matching contains as many edges from a given set of edges as predicted by a heuristic argument.

A diregular bipartite tournament is a balanced complete bipartite graph whose edges are oriented so that every vertex has the same in- and out-degree. In 1981 Jackson showed that a diregular bipartite tournament contains a Hamilton cycle, and conjectured that in fact its edge set can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: for every ε > 0 there exists n0 such that every diregular bipartite tournament on 2n ≥ n0 vertices contains a collection of (1/2–ε)n cycles of length at least (2–ε)n. Increasing the degree by a small proportion allows us to prove the existence of many Hamilton cycles: for every c > 1/2 and ε > 0 there exists n0 such that every cn-regular bipartite digraph on 2n ≥ n0 vertices contains (1−ε)cn edge-disjoint Hamilton cycles.

An equitable colouring of a graph G is a vertex colouring where no two adjacent vertices are coloured the same and, additionally, the colour class sizes differ by at most 1. The equitable chromatic number χ=(G) is the minimum number of colours required for this. We study the equitable chromatic number of the dense random graph ${\mathcal{G}(n,m)}$ where $m = \left\lfloor {p\left( \matrix{ n \cr 2 \cr} \right)} \right\rfloor $ and 0 < p < 0.86 is constant. It is a well-known question of Bollobás [3] whether for p = 1/2 there is a function f(n) → ∞ such that, for any sequence of intervals of length f(n), the normal chromatic number of ${\mathcal{G}(n,m)}$ lies outside the intervals with probability at least 1/2 if n is large enough. Bollobás proposes that this is likely to hold for f(n) = log n. We show that for the equitable chromatic number, the answer to the analogous question is negative. In fact, there is a subsequence ${({n_j})_j}_{ \in {\mathbb {N}}}$ of the integers where $\chi_=({\mathcal{G}(n_j,m_j)})$ is concentrated on exactly one explicitly known value. This constitutes surprisingly narrow concentration since in this range the equitable chromatic number, like the normal chromatic number, is rather large in absolute value, namely asymptotically equal to n/(2logbn) where b = 1/(1 − p).