Jonathan A. Noel

Elena Moss, Jonathan A. Noel

The Ramsey multiplicity problem asks for the minimum asymptotic density of monochromatic labelled copies of a graph $H$ in a red/blue colouring of the edges of $K_n$. We introduce an off-diagonal generalization in which the goal is to minimize a certain weighted sum of the densities of red copies of one graph and blue copies of another. We build up various properties of this new notion, including a useful "dual formulation," and use these results to solve the problem for several pairs of graphs.

Jonathan A. Noel

The $r$-neighbour bootstrap process on a graph $G$ begins with a set of infected vertices; subsequently, healthy vertices become infected once they have at least $r$ infected neighbours. The central extremal problem in bootstrap percolation is to determine the minimum cardinality of an initial infected set that eventually spreads to all vertices of $G$, denoted $m(G;r)$. Morrison and Noel established a general lower bound on $m(Q_d;r)$, where $Q_d$ is the $d$-dimensional hypercube, and asked whether it is tight whenever $d$ is sufficiently large with respect to $r$. This question was answered affirmatively for $r\leq 3$. In this paper, we show that $m(Q_d;4)=\frac{d(d^2+3d+14)}{24}+1$, matching the bound in of Morrison and Noel, for infinitely many $d$. We also obtain, for general $d$, an upper bound on $m(Q_d;4)$ that differs from the Morrison--Noel lower bound by an additive $O(d)$ term. Several key constructions in this paper were obtained with the assistance of AlphaEvolve.