Peter Allen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Peter Allen has a total of 42 co-authors. Here are the top co-authors by number of shared publications:
- Julia Böttcher
Department of Mathematics The London School of Economics London UK
19 shared publications - Yoshiharu Kohayakawa
Instituto de Matemática e Estatística Universidade de Sao Paulo Sao Paulo Brazil
10 shared publications - Jan Hladký
Institute of Computer Science Czech Academy of Sciences Prague Czechia
7 shared publications - Yury Person
Technische Universität Ilmenau
5 shared publications - Anusch Taraz
Tech Univ Hamburg, Inst Math, Hamburg, Germany
3 shared publications - Dennis Clemens
Tech Univ Hamburg, Inst Math, Schwarzenberg Campus 3, D-21073 Hamburg, Germany
3 shared publications
Latest Publications
- Open Access
- 13 October 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (3)
Robustness of the Sauer–Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define to be a random subgraph of obtained by retaining each edge of independently with probability , and let be the maximum 1‐density of a graph . We show that for any constant and , if is an ‐vertex host graph with minimum degree and is an ‐vertex graph with maximum degree , then for , the random subgraph contains a copy of with high probability. Our value for is optimal up to a log‐factor. In fact, we prove this result for a more general minimum degree condition on , by introducing an extension threshold , such that the above result holds for graphs with . We show that , and further conjecture that equals , which matches the minimum degree condition on in the Bollobás–Eldridge–Catlin Conjecture. A main tool in our proof is a vertex‐spread version of the blow‐up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest.
- 13 October 2026
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (3)
Open AccessRobustness of the Sauer–Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define to be a random subgraph of obtained by retaining each edge of independently with probability , and let be the maximum 1‐density of a graph . We show that for any constant and , if is an ‐vertex host graph with minimum degree and is an ‐vertex graph with maximum degree , then for , the random subgraph contains a copy of with high probability. Our value for is optimal up to a log‐factor. In fact, we prove this result for a more general minimum degree condition on , by introducing an extension threshold , such that the above result holds for graphs with . We show that , and further conjecture that equals , which matches the minimum degree condition on in the Bollobás–Eldridge–Catlin Conjecture. A main tool in our proof is a vertex‐spread version of the blow‐up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest.
- Open Access
Ramsey numbers for 1-degenerate 3-graphs
We construct a 3-uniform 1-degenerate hypergraph on $n$ vertices whose 2-colour Ramsey number is $Ω\big(n^{3/2}/\log n\big)$. This shows that all remaining open cases of the hypergraph Burr-Erdős conjecture are false. Our graph is a variant of the celebrated hedgehog graph. We additionally show near-sharp upper bounds, proving that all 3-uniform generalised hedgehogs have 2-colour Ramsey number $O\big(n^{3/2}\big)$.Open AccessRamsey numbers for 1-degenerate 3-graphs
We construct a 3-uniform 1-degenerate hypergraph on $n$ vertices whose 2-colour Ramsey number is $Ω\big(n^{3/2}/\log n\big)$. This shows that all remaining open cases of the hypergraph Burr-Erdős conjecture are false. Our graph is a variant of the celebrated hedgehog graph. We additionally show near-sharp upper bounds, proving that all 3-uniform generalised hedgehogs have 2-colour Ramsey number $O\big(n^{3/2}\big)$. - Open Access
Robustness of the Sauer-Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define $G(p)$ to be a random subgraph of $G$ obtained by retaining each edge of $G$ independently with probability $p \in [0,1]$, and let $m_1(H)$ be the maximum $1$-density of a graph $H$. We show that for any constant $Δ$ and $γ> 0$, if $G$ is an $n$-vertex host graph with minimum degree $δ(G) \geq (1 - 1/2Δ+ γ)n$ and $H$ is an $n$-vertex graph with maximum degree $Δ(H) \leq Δ$, then for $p \geq Cn^{-1/m_1(H)}\log n$, the random subgraph $G(p)$ contains a copy of $H$ with high probability. Our value for $p$ is optimal up to a log-factor. In fact, we prove this result for a more general minimum degree condition on $G$, by introducing an \emph{extension threshold} $δ_{\rm e}(Δ)$, such that the above result holds for graphs $G$ with ${δ(G) \geq (δ_{\rm e}(Δ) + γ)n}$. We show that $δ_{\rm e}(Δ) \leq (2Δ-1)/2Δ$, and further conjecture that $δ_{\rm e}(Δ)$ equals $Δ/(Δ+1)$, which matches the minimum degree condition on $G$ in the Bollobás-Eldridge-Catlin Conjecture. A main tool in our proof is a vertex-spread version of the blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest.Open AccessRobustness of the Sauer-Spencer Theorem
We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define $G(p)$ to be a random subgraph of $G$ obtained by retaining each edge of $G$ independently with probability $p \in [0,1]$, and let $m_1(H)$ be the maximum $1$-density of a graph $H$. We show that for any constant $Δ$ and $γ> 0$, if $G$ is an $n$-vertex host graph with minimum degree $δ(G) \geq (1 - 1/2Δ+ γ)n$ and $H$ is an $n$-vertex graph with maximum degree $Δ(H) \leq Δ$, then for $p \geq Cn^{-1/m_1(H)}\log n$, the random subgraph $G(p)$ contains a copy of $H$ with high probability. Our value for $p$ is optimal up to a log-factor. In fact, we prove this result for a more general minimum degree condition on $G$, by introducing an \emph{extension threshold} $δ_{\rm e}(Δ)$, such that the above result holds for graphs $G$ with ${δ(G) \geq (δ_{\rm e}(Δ) + γ)n}$. We show that $δ_{\rm e}(Δ) \leq (2Δ-1)/2Δ$, and further conjecture that $δ_{\rm e}(Δ)$ equals $Δ/(Δ+1)$, which matches the minimum degree condition on $G$ in the Bollobás-Eldridge-Catlin Conjecture. A main tool in our proof is a vertex-spread version of the blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest. - Open Access
- 1 July 2024
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 4 (1)
Resilience for tight Hamiltonicity
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gamma›0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform hypergraph \(G^{(k)}\big(n,n^{\gamma-1}\big)\) in which all \((k-1)\)-sets are contained in at least \(\big(\tfrac12+2\gamma\big)pn\) edges has a tight Hamilton cycle. This is a cyclic ordering of the \(n\) vertices such that each consecutive \(k\) vertices forms an edge.Mathematics Subject Classifications: 05C80, 05C35Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience- 1 July 2024
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 4 (1)
Open AccessResilience for tight Hamiltonicity
We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gamma›0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform hypergraph \(G^{(k)}\big(n,n^{\gamma-1}\big)\) in which all \((k-1)\)-sets are contained in at least \(\big(\tfrac12+2\gamma\big)pn\) edges has a tight Hamilton cycle. This is a cyclic ordering of the \(n\) vertices such that each consecutive \(k\) vertices forms an edge.Mathematics Subject Classifications: 05C80, 05C35Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience - Open Access
- 5 April 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (2) , P2.11
The Ramsey Numbers of Squares of Paths and Cycles
The square $G^2$ of a graph $G$ is the graph on $V(G)$ with a pair of vertices $uv$ an edge whenever $u$ and $v$ have distance $1$ or $2$ in $G$. Given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum $N$ such that whenever the edges of the complete graph $K_N$ are coloured with red and blue, there exists either a red copy of $G$ or a blue copy of $H$. We prove that for all sufficiently large $n$ we have$$ R(P_{3n}^2,P_{3n}^2)=R(P_{3n+1}^2,P_{3n+1}^2)=R(C_{3n}^2,C_{3n}^2)=9n-3\mbox{ and } R(P_{3n+2}^2,P_{3n+2}^2)=9n+1.$$ We also show that for any $\gamma>0$ and $\Delta$ there exists $\beta>0$ such that the following holds: If $G$ can be coloured with three colours such that all colour classes have size at most $n$, the maximum degree $\Delta(G)$ of $G$ is at most $\Delta$, and $G$ has bandwidth at most $\beta n$, then $R(G,G)\le (3+\gamma)n$.- 5 April 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (2) , P2.11
Open AccessThe Ramsey Numbers of Squares of Paths and Cycles
The square $G^2$ of a graph $G$ is the graph on $V(G)$ with a pair of vertices $uv$ an edge whenever $u$ and $v$ have distance $1$ or $2$ in $G$. Given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum $N$ such that whenever the edges of the complete graph $K_N$ are coloured with red and blue, there exists either a red copy of $G$ or a blue copy of $H$. We prove that for all sufficiently large $n$ we have$$ R(P_{3n}^2,P_{3n}^2)=R(P_{3n+1}^2,P_{3n+1}^2)=R(C_{3n}^2,C_{3n}^2)=9n-3\mbox{ and } R(P_{3n+2}^2,P_{3n+2}^2)=9n+1.$$ We also show that for any $\gamma>0$ and $\Delta$ there exists $\beta>0$ such that the following holds: If $G$ can be coloured with three colours such that all colour classes have size at most $n$, the maximum degree $\Delta(G)$ of $G$ is at most $\Delta$, and $G$ has bandwidth at most $\beta n$, then $R(G,G)\le (3+\gamma)n$. - Open Access
- 1 January 2023
- Published by Masaryk University Press
- p. 12-18
Partition Universality for Hypergraphs of Bounded Degeneracy and Degree
We consider the following question. When is the random $k$-uniform hypergraph $\Gamma=G^{(k)}(N,p)$ likely to be $r$-partition universal for $k$-uniform hypergraphs of bounded degree and degeneracy? That is, for which~$p$ can we guarantee asymptotically almost surely that in any $r$-colouring of $E(\Gamma)$ there exists a colour $\chi$ such that in $\Gamma$ there are $\chi$-monochromatic copies of all $k$-uniform hypergraphs of maximum vertex degree $\Delta$, degeneracy at most $D$, and $cN$ vertices for some constant $c=c(D,\Delta)>0$. We show that if $\mu>0$ is fixed, then $p\ge N^{-1/D+\mu}$ suffices for a positive answer if $N$ is large. On the other hand, for $p=o(N^{-1/D})$ we show that $G^{(k)}(N,p)$ is likely not to contain some graphs of maximum degree $\Delta$ and degeneracy $D$ on $cN$ vertices at all. This improves the best upper bounds on the minimum number of edges required for a $k$-uniform hypergraph to be partition universal (even for $k=2$) and also for the size-Ramsey problem for most $k$-uniform hypergraphs of bounded degree and degeneracy.- 1 January 2023
- Published by Masaryk University Press
- p. 12-18
Open AccessPartition Universality for Hypergraphs of Bounded Degeneracy and Degree
We consider the following question. When is the random $k$-uniform hypergraph $\Gamma=G^{(k)}(N,p)$ likely to be $r$-partition universal for $k$-uniform hypergraphs of bounded degree and degeneracy? That is, for which~$p$ can we guarantee asymptotically almost surely that in any $r$-colouring of $E(\Gamma)$ there exists a colour $\chi$ such that in $\Gamma$ there are $\chi$-monochromatic copies of all $k$-uniform hypergraphs of maximum vertex degree $\Delta$, degeneracy at most $D$, and $cN$ vertices for some constant $c=c(D,\Delta)>0$. We show that if $\mu>0$ is fixed, then $p\ge N^{-1/D+\mu}$ suffices for a positive answer if $N$ is large. On the other hand, for $p=o(N^{-1/D})$ we show that $G^{(k)}(N,p)$ is likely not to contain some graphs of maximum degree $\Delta$ and degeneracy $D$ on $cN$ vertices at all. This improves the best upper bounds on the minimum number of edges required for a $k$-uniform hypergraph to be partition universal (even for $k=2$) and also for the size-Ramsey problem for most $k$-uniform hypergraphs of bounded degree and degeneracy. - 27 December 2022
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 255 (2) , 501-579
Perfectly packing graphs with bounded degeneracy and many leaves
- 27 December 2022
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 255 (2) , 501-579
Perfectly packing graphs with bounded degeneracy and many leaves
- Open Access
Partition universality for graphs of bounded degeneracy and degree
We prove asymptotically optimal bounds on the number of edges a graph $G$ must have in order that any $r$-colouring of $E(G)$ has a colour class which contains every $D$-degenerate graph on $n$ vertices with bounded maximum degree. We also improve the upper bounds on the number of edges $G$ must have in order that any $r$-colouring of $E(G)$ has a colour class which contains every $n$-vertex graph with maximum degree $\Delta$, for each $\Delta\ge 4$. In both cases, we show that a binomial random graph with $Cn$ vertices and a suitable edge probability is likely to provide the desired $G$.Open AccessPartition universality for graphs of bounded degeneracy and degree
We prove asymptotically optimal bounds on the number of edges a graph $G$ must have in order that any $r$-colouring of $E(G)$ has a colour class which contains every $D$-degenerate graph on $n$ vertices with bounded maximum degree. We also improve the upper bounds on the number of edges $G$ must have in order that any $r$-colouring of $E(G)$ has a colour class which contains every $n$-vertex graph with maximum degree $\Delta$, for each $\Delta\ge 4$. In both cases, we show that a binomial random graph with $Cn$ vertices and a suitable edge probability is likely to provide the desired $G$. - Open Access
The tree packing conjecture for trees of almost linear maximum degree
We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,\dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/\log n$, then $\{T_1,\dots,T_n\}$ packs into $K_n$. Our main result actually allows to replace the host graph $K_n$ by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices.Open AccessThe tree packing conjecture for trees of almost linear maximum degree
We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,\dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/\log n$, then $\{T_1,\dots,T_n\}$ packs into $K_n$. Our main result actually allows to replace the host graph $K_n$ by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices. - Open Access
Almost all trees are almost graceful
The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labelled by using the numbers {1,2,...,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove the following relaxation of the conjecture for each c>0 and for all n>n_0(c). Suppose that (i) the maximum degree of T is bounded by O(n/log n), and (ii) the vertex labels are chosen from the set {1,2,..., (1+c)n}. Then there is an injective labelling of V(T) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on n vertices admit such a labelling. As a consequence, for any such tree T we can pack (2+2c)n-1 copies of T into the complete graph of order (2+2c)n-1 cyclically. This proves an approximate version of the Ringel-Kotzig conjecture (which asserts the existence of a cyclic packing of 2n-1 copies of any T into the complete graph of order 2n-1) for these trees. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labelling with high probability.
Open AccessAlmost all trees are almost graceful
The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labelled by using the numbers {1,2,...,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove the following relaxation of the conjecture for each c>0 and for all n>n_0(c). Suppose that (i) the maximum degree of T is bounded by O(n/log n), and (ii) the vertex labels are chosen from the set {1,2,..., (1+c)n}. Then there is an injective labelling of V(T) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on n vertices admit such a labelling. As a consequence, for any such tree T we can pack (2+2c)n-1 copies of T into the complete graph of order (2+2c)n-1 cyclically. This proves an approximate version of the Ringel-Kotzig conjecture (which asserts the existence of a cyclic packing of 2n-1 copies of any T into the complete graph of order 2n-1) for these trees. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labelling with high probability.