Joshua Erde

activity

20122025

most citedA counterexample to the reconstruction conjecture for locally finite trees

5 citations · 32 across the 42 of their papers we have counts for

collaborators

52 papers

math.CO2025

Optimally building spanning graphs in semirandom graph processes

Michael Anastos, Maurício Collares, Joshua Erde +3

The semirandom graph process constructs a graph $G$ in a series of rounds, starting with the empty graph on $n$ vertices. In each round, a player is offered a vertex $v$ chosen uni…

math.CO2025

Majority bootstrap percolation on the permutahedron and other high-dimensional graphs

Maurício Collares, Joshua Erde, Anna Geisler +1

Majority bootstrap percolation is a model of infection spreading in networks. Starting with a set of initially infected vertices, new vertices become infected once half of their ne…

math.CO2025

Cycle lengths in the percolated hypercube

Michael Anastos, Sahar Diskin, Joshua Erde +3

Let $Q_{p}^{d}$ be the random subgraph of the $d$ -dimensional binary hypercube obtained after edge-percolation with probability $p$ . It was shown recently by the authors that, for ever…

math.CO2025

A short proof of a central limit theorem for the order of the giant component and $k$ -core

Michael Anastos, Joshua Erde, Mihyun Kang +1

In this note we outline a new and simple approach to proving central limit theorems for various 'global' graph parameters which have robust 'local' approximations, using the Efron-…

math.CO2025

Nearly spanning cycle in the percolated hypercube

Michael Anastos, Sahar Diskin, Joshua Erde +3

Let $Q^{d}$ be the $d$ -dimensional binary hypercube. We form a random subgraph $Q_{p}^{d} \subseteq Q^{d}$ by retaining each edge of $Q^{d}$ independently with probability $p$ . We show that,…

math.CO2025

Counting independent sets in expanding bipartite regular graphs

Maurício Collares, Joshua Erde, Anna Geisler +1

In this paper we provide an asymptotic expansion for the number of independent sets in a general class of regular, bipartite graphs satisfying some vertex-expansion properties, ext…

math.CO2025

The law of the circumference of sparse binomial random graphs

Michael Anastos, Joshua Erde, Mihyun Kang +1

There has been much interest in the distribution of the circumference, the length of the longest cycle, of a random graph $G (n, p)$ in the sparse regime, when $p = Θ\left(\frac{1}{n…

math.CO2024

Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

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 exis…

math.CO2024

Long cycles in percolated expanders

Maurício Collares, Sahar Diskin, Joshua Erde +1

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 N$ and constants $0<c…

math.CO2024

Universal behaviour of majority bootstrap percolation on high-dimensional geometric graphs

Maurício Collares, Joshua Erde, Anna Geisler +1

Majority bootstrap percolation is a monotone cellular automaton that can be thought of as a model of infection spreading in networks. Starting with an initially infected set, new v…

math.CO2024★ 1 cited

The evolution of the permutahedron

Maurício Collares, Joseph Doolittle, Joshua Erde

In their seminal paper introducing the theory of random graphs, Erdős and Rényi considered the evolution of the structure of a random subgraph of $K_{n}$ as the density increases fro…

math.CO2024

Matchings in the hypercube with specified edges

Joshua Erde

Given a matching $M$ in the hypercube $Q^{n}$ , the \emph{profile} of $M$ is the vector $x = (x_{1}, \dots, x_{n}) \in N^{n}$ such that $M$ contains $x_{i}$ edges whose en…

math.CO2023

Percolation through Isoperimetry

Sahar Diskin, Joshua Erde, Mihyun Kang +1

We provide a sufficient condition on the isoperimetric properties of a regular graph $G$ of growing degree $d$ , under which the random subgraph $G_{p}$ typically undergoes a phase tr…

math.CO2023

Catching a robber on a random $k$ -uniform hypergraph

Joshua Erde, Mihyun Kang, Florian Lehner +2

The game of \emph{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 \emph{cop number} of a gra…

math.PR2023

Isoperimetric Inequalities and Supercritical Percolation on High-dimensional Graphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

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…

math.CO2022★ 3 cited

Percolation on Irregular High-dimensional Product Graphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

We consider bond percolation on high-dimensional product graphs $G = □_{i = 1}^{t} G^{(i)}$ , where $□$ denotes the Cartesian product. We call the $G^{(i)}$ the base graphs and…

math.CO2022★ 1 cited

The emergence of a giant rainbow component

Oliver Cooley, Tuan Anh Do, Joshua Erde +1

The random coloured graph $G_{c} (n, p)$ is obtained from the Erdős-Rényi binomial random graph $G (n, p)$ by assigning to each edge a colour from a set of $c$ colours independently and…

math.CO2022★ 1 cited

Percolation on High-dimensional Product Graphs

Sahar Diskin, Joshua Erde, Mihyun Kang +1

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 co…

math.CO2022

A note on the width of sparse random graphs

Tuan Anh Do, Joshua Erde, Mihyun Kang

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,…

math.CO2021

Expansion in supercritical random subgraphs of the hypercube and its consequences

Joshua Erde, Mihyun Kang, Michael Krivelevich

It is well-known that the behaviour of a random subgraph of a $d$ -dimensional hypercube, where we include each edge independently with probability $p$ , undergoes a phase transition…

math.CO2021★ 1 cited

Duality and tangles of set separations

Reinhard Diestel, Christian Elbracht, Joshua Erde +1

Applications of tangles of connectivity systems suggest a duality between these, in which for two sets $X$ and $Y$ the elements $x$ of $X$ map to subsets $Y_{x}$ of $Y$ , and the…

math.CO2021★ 2 cited

Expansion, long cycles, and complete minors in supercritical random subgraphs of the hypercube

Joshua Erde, Mihyun Kang, Michael Krivelevich

Analogous to the case of the binomial random graph $G (d + 1, p)$ , it is known that the behaviour of a random subgraph of a $d$ -dimensional hypercube, where we include each edge indepe…

math.CO2021

Component behaviour and excess of random bipartite graphs near the critical point

Tuan Anh Do, Joshua Erde, Mihyun Kang +1

The binomial random bipartite graph $G (n, n, p)$ is the random graph formed by taking two partition classes of size $n$ and including each edge between them independently with probab…

math.CO2020

Ubiquity in graphs III: Ubiquity of locally finite graphs with extensive tree-decompositions

Nathan Bowler, Christian Elbracht, Joshua Erde +4

A graph $G$ is said to be ubiquitous, if every graph $Γ$ that contains arbitrarily many disjoint $G$ -minors automatically contains infinitely many disjoint $G$ -minors. The well-kno…

Optimally building spanning graphs in semirandom graph processes

Majority bootstrap percolation on the permutahedron and other high-dimensional graphs

Cycle lengths in the percolated hypercube

A short proof of a central limit theorem for the order of the giant component and k-core

Nearly spanning cycle in the percolated hypercube

Counting independent sets in expanding bipartite regular graphs

The law of the circumference of sparse binomial random graphs

Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs

Long cycles in percolated expanders

Universal behaviour of majority bootstrap percolation on high-dimensional geometric graphs

The evolution of the permutahedron

Matchings in the hypercube with specified edges

Percolation through Isoperimetry

Catching a robber on a random k-uniform hypergraph

Isoperimetric Inequalities and Supercritical Percolation on High-dimensional Graphs

Percolation on Irregular High-dimensional Product Graphs

The emergence of a giant rainbow component

Percolation on High-dimensional Product Graphs

A note on the width of sparse random graphs

Expansion in supercritical random subgraphs of the hypercube and its consequences

Duality and tangles of set separations

Expansion, long cycles, and complete minors in supercritical random subgraphs of the hypercube

Component behaviour and excess of random bipartite graphs near the critical point

Ubiquity in graphs III: Ubiquity of locally finite graphs with extensive tree-decompositions

A short proof of a central limit theorem for the order of the giant component and $k$ -core

Catching a robber on a random $k$ -uniform hypergraph