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.

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.

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.

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

Akbari and Alipour [1] conjectured that any Latin array of order n with at least n2/2 symbols contains a transversal. For large n, we confirm this conjecture, and moreover, we show that n399/200 symbols suffice.

The Brownian separable permuton is a random probability measure on the unit square, which was introduced by Bassino, Bouvel, Féray, Gerin and Pierrot (2016) as the scaling limit of the diagram of the uniform separable permutation as size grows to infinity. We show that, almost surely, the permuton is the pushforward of the Lebesgue measure on the graph of a random measure-preserving function associated to a Brownian excursion whose strict local minima are decorated with independent and identically distributed signs. As a consequence, its support is almost surely totally disconnected, has Hausdorff dimension one, and enjoys self-similarity properties inherited from those of the Brownian excursion. The density function of the averaged permuton is computed and a connection with the shuffling of the Brownian continuum random tree is explored.

We show that a nearly square independent and identically distributed random integral matrix is surjective over the integral lattice with very high probability. This answers a question by Koplewitz [6]. Our result extends to sparse matrices as well as to matrices of dependent entries.

We study random composite structures considered up to symmetry that are sampled according to weights on the inner and outer structures. This model may be viewed as an unlabelled version of Gibbs partitions and encompasses multisets of weighted combinatorial objects. We describe a general setting characterized by the formation of a giant component. The collection of small fragments is shown to converge in total variation toward a limit object following a Pólya–Boltzmann distribution.

We prove that n plane algebraic curves determine O(n(k+2)/(k+1)) points of kth order tangency. This generalizes an earlier result of Ellenberg, Solymosi and Zahl on the number of (first order) tangencies determined by n plane algebraic curves.