Joshua Erde
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Joshua Erde has a total of 35 co-authors. Here are the top co-authors by number of shared publications:
- Mihyun Kang
Institute of Discrete Mathematics Graz University of Technology Graz Austria
10 shared publications - Michael Krivelevich
Tel Aviv University
9 shared publications - Jochen Pascal Gollin
FAMNIT, University of Primorska, Koper, Slovenia
8 shared publications - Sahar Diskin
Tel-Aviv University, Israel
8 shared publications - Max Pitz
University of Hamburg
7 shared publications - Christian Elbracht
Department of Mathematics, Universität Hamburg, Germany
6 shared publications
Latest Publications
- Open Access
- 10 August 2026
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 58 (8) , e70464
A short proof of a central limit theorem for the order of the giant component and k‐core
In this note we outline a new and simple approach to proving central limit theorems for various ‘global’ graph parameters that have robust ‘local’ approximations, using the Efron–Stein inequality, which relies on a combinatorial analysis of the stability of these approximations under resampling an edge. As an application, we give short proofs of a central limit theorem for the order of the giant component and of the ‐core for sparse random graphs.
- 10 August 2026
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 58 (8) , e70464
Open AccessA short proof of a central limit theorem for the order of the giant component and k‐core
In this note we outline a new and simple approach to proving central limit theorems for various ‘global’ graph parameters that have robust ‘local’ approximations, using the Efron–Stein inequality, which relies on a combinatorial analysis of the stability of these approximations under resampling an edge. As an application, we give short proofs of a central limit theorem for the order of the giant component and of the ‐core for sparse random graphs.
- Open Access
Nearly spanning cycle in the percolated hypercube
Let $Q^d$ be the $d$-dimensional binary hypercube. We form a random subgraph $Q^d_p\subseteq Q^d$ by retaining each edge of $Q^d$ independently with probability $p$. We show that, for every constant $\varepsilon>0$, there exists a constant $C=C(\varepsilon)>0$ such that, if $p\ge C/d$, then with high probability $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny Díaz, Girão, Kühn, and Osthus [Hamiltonicity of random subgraphs of the hypercube, Mem. Amer. Math. Soc. 305 (2024), No. 1534].Open AccessNearly spanning cycle in the percolated hypercube
Let $Q^d$ be the $d$-dimensional binary hypercube. We form a random subgraph $Q^d_p\subseteq Q^d$ by retaining each edge of $Q^d$ independently with probability $p$. We show that, for every constant $\varepsilon>0$, there exists a constant $C=C(\varepsilon)>0$ such that, if $p\ge C/d$, then with high probability $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny Díaz, Girão, Kühn, and Osthus [Hamiltonicity of random subgraphs of the hypercube, Mem. Amer. Math. Soc. 305 (2024), No. 1534]. - Open Access
- 17 January 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (1) , P1.8
Long Cycles in Percolated Expanders
Given a graph $G$ and probability $p$, we form the random subgraph $G_p$ by retaining each edge of $G$ independently with probability $p$. Given $d\in\mathbb{N}$, constants $0- 17 January 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (1) , P1.8
Open AccessLong Cycles in Percolated Expanders
Given a graph $G$ and probability $p$, we form the random subgraph $G_p$ by retaining each edge of $G$ independently with probability $p$. Given $d\in\mathbb{N}$, constants $0 - Open Access
- 27 September 2024
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 4 (2)
Ubiquity of locally finite graphs with extensive tree-decompositions
A graph \(G\) is said to be ubiquitous, if every graph \(\Gamma\) that contains arbitrarily many disjoint \(G\)-minors automatically contains infinitely many disjoint \(G\)-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.Mathematics Subject Classifications: 05C83, 05C63Keywords: Graph minors, infinite graphs, ubiquity- 27 September 2024
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 4 (2)
Open AccessUbiquity of locally finite graphs with extensive tree-decompositions
A graph \(G\) is said to be ubiquitous, if every graph \(\Gamma\) that contains arbitrarily many disjoint \(G\)-minors automatically contains infinitely many disjoint \(G\)-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.Mathematics Subject Classifications: 05C83, 05C63Keywords: Graph minors, infinite graphs, ubiquity - Open Access
Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
Given a graph $G$ and $p\in [0,1]$, the random subgraph $G_p$ is obtained by retaining each edge of $G$ independently with probability $p$. We show that for every $ε>0$, there exists a constant $C>0$ such that the following holds. Let $d\ge C$ be an integer, let $G$ be a $d$-regular graph and let $p\ge \frac{C}{d}$. Then, with probability tending to one as $|V(G)|$ tends to infinity, there exists a matching in $G_p$ covering at least $(1-ε)|V(G)|$ vertices. We further show that for a wide family of $d$-regular graphs $G$, which includes the $d$-dimensional hypercube, for any $p\ge \frac{\log^5d}{d}$ with probability tending to one as $d$ tends to infinity, $G_p$ contains an induced subgraph on at least $(1-o(1))|V(G)|$ vertices, whose degrees are tightly concentrated around the expected average degree $dp$.Open AccessLarge matchings and nearly spanning, nearly regular subgraphs of random subgraphs
Given a graph $G$ and $p\in [0,1]$, the random subgraph $G_p$ is obtained by retaining each edge of $G$ independently with probability $p$. We show that for every $ε>0$, there exists a constant $C>0$ such that the following holds. Let $d\ge C$ be an integer, let $G$ be a $d$-regular graph and let $p\ge \frac{C}{d}$. Then, with probability tending to one as $|V(G)|$ tends to infinity, there exists a matching in $G_p$ covering at least $(1-ε)|V(G)|$ vertices. We further show that for a wide family of $d$-regular graphs $G$, which includes the $d$-dimensional hypercube, for any $p\ge \frac{\log^5d}{d}$ with probability tending to one as $d$ tends to infinity, $G_p$ contains an induced subgraph on at least $(1-o(1))|V(G)|$ vertices, whose degrees are tightly concentrated around the expected average degree $dp$. - Open Access
Long cycles in percolated expanders
Given a graph $G$ and probability $p$, we form the random subgraph $G_p$ by retaining each edge of $G$ independently with probability $p$. Given $d\in\mathbb{N}$ and constants $0Open AccessLong cycles in percolated expanders
Given a graph $G$ and probability $p$, we form the random subgraph $G_p$ by retaining each edge of $G$ independently with probability $p$. Given $d\in\mathbb{N}$ and constants $0 - Open Access
Percolation on High-dimensional Product Graphs
We consider percolation on high-dimensional product graphs, where the base graphs are regular and of bounded order. In the subcritical regime, we show that typically the largest component is of order logarithmic in the number of vertices. In the supercritical regime, our main result recovers the sharp asymptotic of the order of the largest component, and shows that all the other components are typically of order logarithmic in the number of vertices. In particular, we show that this phase transition is quantitatively similar to the one of the binomial random graph. This generalises the results of Ajtai, Koml\'os, and Szemer\'edi and of Bollob\'as, Kohayakawa, and \L{}uczak who showed that the $d$-dimensional hypercube, which is the $d$-fold Cartesian product of an edge, undergoes a phase transition quantitatively similar to the one of the binomial random graph.
Open AccessPercolation on High-dimensional Product Graphs
We consider percolation on high-dimensional product graphs, where the base graphs are regular and of bounded order. In the subcritical regime, we show that typically the largest component is of order logarithmic in the number of vertices. In the supercritical regime, our main result recovers the sharp asymptotic of the order of the largest component, and shows that all the other components are typically of order logarithmic in the number of vertices. In particular, we show that this phase transition is quantitatively similar to the one of the binomial random graph. This generalises the results of Ajtai, Koml\'os, and Szemer\'edi and of Bollob\'as, Kohayakawa, and \L{}uczak who showed that the $d$-dimensional hypercube, which is the $d$-fold Cartesian product of an edge, undergoes a phase transition quantitatively similar to the one of the binomial random graph.
- Open Access
- 4 April 2024
- Published by Springer Nature in Combinatorica
- Vol. 44 (4) , 741-784
Isoperimetric Inequalities and Supercritical Percolation on High-Dimensional Graphs
It is known that many different types of finite random subgraph models undergo quantitatively similar phase transitions around their percolation thresholds, and the proofs of these results rely on isoperimetric properties of the underlying host graph. Recently, the authors showed that such a phase transition occurs in a large class of regular high-dimensional product graphs, generalising a classic result for the hypercube. In this paper we give new isoperimetric inequalities for such regular high-dimensional product graphs, which generalise the well-known isoperimetric inequality of Harper for the hypercube, and are asymptotically sharp for a wide range of set sizes. We then use these isoperimetric properties to investigate the structure of the giant component $$L_1$$ in supercritical percolation on these product graphs, that is, when $$p=\frac{1+\epsilon }{d}$$ , where d is the degree of the product graph and $$\epsilon >0$$ is a small enough constant. We show that typically $$L_1$$ has edge-expansion $$\Omega \left( \frac{1}{d\ln d}\right) $$ . Furthermore, we show that $$L_1$$ likely contains a linear-sized subgraph with vertex-expansion $$\Omega \left( \frac{1}{d\ln d}\right) $$ . These results are best possible up to the logarithmic factor in d. Using these likely expansion properties, we determine, up to small polylogarithmic factors in d, the likely diameter of $$L_1$$ as well as the typical mixing time of a lazy random walk on $$L_1$$ . Furthermore, we show the likely existence of a cycle of length $$\Omega \left( \frac{n}{d\ln d}\right) $$ . These results not only generalise, but also improve substantially upon the known bounds in the case of the hypercube, where in particular the likely diameter and typical mixing time of $$L_1$$ were previously only known to be polynomial in d.- 4 April 2024
- Published by Springer Nature in Combinatorica
- Vol. 44 (4) , 741-784
Open AccessIsoperimetric Inequalities and Supercritical Percolation on High-Dimensional Graphs
It is known that many different types of finite random subgraph models undergo quantitatively similar phase transitions around their percolation thresholds, and the proofs of these results rely on isoperimetric properties of the underlying host graph. Recently, the authors showed that such a phase transition occurs in a large class of regular high-dimensional product graphs, generalising a classic result for the hypercube. In this paper we give new isoperimetric inequalities for such regular high-dimensional product graphs, which generalise the well-known isoperimetric inequality of Harper for the hypercube, and are asymptotically sharp for a wide range of set sizes. We then use these isoperimetric properties to investigate the structure of the giant component $$L_1$$ in supercritical percolation on these product graphs, that is, when $$p=\frac{1+\epsilon }{d}$$ , where d is the degree of the product graph and $$\epsilon >0$$ is a small enough constant. We show that typically $$L_1$$ has edge-expansion $$\Omega \left( \frac{1}{d\ln d}\right) $$ . Furthermore, we show that $$L_1$$ likely contains a linear-sized subgraph with vertex-expansion $$\Omega \left( \frac{1}{d\ln d}\right) $$ . These results are best possible up to the logarithmic factor in d. Using these likely expansion properties, we determine, up to small polylogarithmic factors in d, the likely diameter of $$L_1$$ as well as the typical mixing time of a lazy random walk on $$L_1$$ . Furthermore, we show the likely existence of a cycle of length $$\Omega \left( \frac{n}{d\ln d}\right) $$ . These results not only generalise, but also improve substantially upon the known bounds in the case of the hypercube, where in particular the likely diameter and typical mixing time of $$L_1$$ were previously only known to be polynomial in d. - Open Access
- 1 April 2024
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 77 (4) , 1135-1162
Catching a robber on a random k-uniform hypergraph
The game of Cops and Robber is usually played on a graph, where a group of cops attempt to catch a robber moving along the edges of the graph. The cop number of a graph is the minimum number of cops required to win the game. An important conjecture in this area, due to Meyniel, states that the cop number of an n-vertex connected graph is $O(\sqrt {n})$ . In 2016, Prałat and Wormald showed that this conjecture holds with high probability for random graphs above the connectedness threshold. Moreover, Łuczak and Prałat showed that on a $\log $ -scale the cop number demonstrates a surprising zigzag behavior in dense regimes of the binomial random graph $G(n,p)$ . In this paper, we consider the game of Cops and Robber on a hypergraph, where the players move along hyperedges instead of edges. We show that with high probability the cop number of the k-uniform binomial random hypergraph $G^k(n,p)$ is $O\left (\sqrt {\frac {n}{k}}\, \log n \right )$ for a broad range of parameters p and k and that on a $\log $ -scale our upper bound on the cop number arises as the minimum of two complementary zigzag curves, as opposed to the case of $G(n,p)$ . Furthermore, we conjecture that the cop number of a connected k-uniform hypergraph on n vertices is $O\left (\sqrt {\frac {n}{k}}\,\right )$ .- 1 April 2024
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 77 (4) , 1135-1162
Open AccessCatching a robber on a random k-uniform hypergraph
The game of Cops and Robber is usually played on a graph, where a group of cops attempt to catch a robber moving along the edges of the graph. The cop number of a graph is the minimum number of cops required to win the game. An important conjecture in this area, due to Meyniel, states that the cop number of an n-vertex connected graph is $O(\sqrt {n})$ . In 2016, Prałat and Wormald showed that this conjecture holds with high probability for random graphs above the connectedness threshold. Moreover, Łuczak and Prałat showed that on a $\log $ -scale the cop number demonstrates a surprising zigzag behavior in dense regimes of the binomial random graph $G(n,p)$ . In this paper, we consider the game of Cops and Robber on a hypergraph, where the players move along hyperedges instead of edges. We show that with high probability the cop number of the k-uniform binomial random hypergraph $G^k(n,p)$ is $O\left (\sqrt {\frac {n}{k}}\, \log n \right )$ for a broad range of parameters p and k and that on a $\log $ -scale our upper bound on the cop number arises as the minimum of two complementary zigzag curves, as opposed to the case of $G(n,p)$ . Furthermore, we conjecture that the cop number of a connected k-uniform hypergraph on n vertices is $O\left (\sqrt {\frac {n}{k}}\,\right )$ . - Open Access
- 8 February 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (2) , 273-295
A note on the width of sparse random graphs
In this note, we consider the width of a supercritical random graph according to some commonly studied width measures. We give short, direct proofs of results of Lee, Lee and Oum, and of Perarnau and Serra, on the rank‐ and tree‐width of the random graph when for constant. Our proofs avoid the use of black box results on the expansion properties of the giant component in this regime, and so as a further benefit we obtain explicit bounds on the dependence of these results on . Finally, we also consider the width of the random graph in the weakly supercritical regime, where and . In this regime, we determine, up to a constant multiplicative factor, the rank‐ and tree‐width of as a function of and .
- 8 February 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (2) , 273-295
Open AccessA note on the width of sparse random graphs
In this note, we consider the width of a supercritical random graph according to some commonly studied width measures. We give short, direct proofs of results of Lee, Lee and Oum, and of Perarnau and Serra, on the rank‐ and tree‐width of the random graph when for constant. Our proofs avoid the use of black box results on the expansion properties of the giant component in this regime, and so as a further benefit we obtain explicit bounds on the dependence of these results on . Finally, we also consider the width of the random graph in the weakly supercritical regime, where and . In this regime, we determine, up to a constant multiplicative factor, the rank‐ and tree‐width of as a function of and .