Dellamonica, Kohayakawa, Rödl and Ruciński showed that for $p=C(\log n/n)^{1/d}$ the random graph $G(n,p)$ contains asymptotically almost surely all spanning graphs $H$ with maximum degree $d$ as subgraphs. In this talk I will discuss a resilience version of this result, which shows that for the same edge density, even if a $(1/k-\epsilon)$-fraction of the edges at every vertex is deleted adversarially from $G(n,p)$, the resulting graph continues to contain asymptotically almost surely all spanning $H$ with maximum degree $d$, with sublinear bandwidth and with at least $C \max\{p^{-2},p^{-1}\log n\}$ vertices not in triangles. Neither the restriction on the bandwidth, nor the condition that not all vertices are allowed to be in triangles can be removed. The proof uses a sparse version of the Blow-Up Lemma. Joint work with Peter Allen, Julia Ehrenmüller, Anusch Taraz.

# Past Combinatorial Theory Seminar

Suppose that we have a tile $T$ in say $\mathbb{Z}^2$, meaning a finite subset of $\mathbb{Z}^2$. It may or may not be the case that $T$ tiles $\mathbb{Z}^2$, in the sense that $\mathbb{Z}^2$ can be partitioned into copies of $T$. But is there always some higher dimension $\mathbb{Z}^d$ that can be tiled with copies of $T$? We prove that this is the case: for any tile in $\mathbb{Z}^2$ (or in $\mathbb{Z}^n$, any $n$) there is a $d$ such that $\mathbb{Z}^d$ can be tiled with copies of it. This proves a conjecture of Chalcraft.

Suppose we have a finite graph. We can view this as a resistor network where each edge has unit resistance. We can then calculate the resistance between any two vertices and ask questions like `which graph with $n$ vertices and $m$ edges minimises the average resistance between pairs of vertices?' There is a `obvious' solution; we show that this answer is not correct.

This problem was motivated by some questions about the design of statistical experiments (and has some surprising applications in chemistry) but this talk will not assume any statistical knowledge.

This is joint work with Robert Johnson.

Erdős asked the following question: given a positive integer $n$, what is the largest integer $k$ such that any set of $n$ points in a plane, with no $4$ on a line, contains $k$ points no $3$ of which are collinear? Füredi proved that $k = o(n)$. Cardinal, Toth and Wood extended this result to $\mathbb{R}^3$, finding sets of $n$ points with no $5$ on a plane whose subsets with no $4$ points on a plane have size $o(n)$, and asked the question for the higher dimensions. For given $n$, let $k$ be largest integer such that any set of $n$ points in $\mathbb{R}^d$ with no more than $d + 1$ cohyperplanar points, has $k$ points with no $d + 1$ on a hyperplane. Is $k = o(n)$? We prove that $k = o(n)$ for any fixed $d \geq 3$.

The Number Field Sieve is the current practical and theoretical state of the art algorithm for factoring. Unfortunately, there has been no rigorous analysis of this type of algorithm. We randomise key aspects of the number theory, and prove that in this variant congruences of squares are formed in expected time $L(1/3, 2.88)$. These results are tightly coupled to recent progress on the distribution of smooth numbers, and we provide additional tools to turn progress on these problems into improved bounds.

Given two probability distributions $P_R$ and $P_B$ on the positive reals with finite means, colour the real line alternately with red and blue intervals so that the lengths of the red intervals have distribution $P_R$, the lengths of the blue intervals have distribution $P_B$, and distinct intervals have independent lengths. Now iteratively update this colouring of the line by coalescing intervals: change the colour of any interval that is surrounded by longer intervals so that these three consecutive intervals subsequently form a single monochromatic interval. Say that a colour (either red or blue) `wins' if every point of the line is eventually of that colour. I will attempt to answer the following question: under what natural conditions on the distributions is one of the colours almost surely guaranteed to win?