9 papers · 1 filter
Optimally building spanning graphs in semirandom graph processes
Michael Anastos, Maurício Collares, Joshua Erde +3
The semirandom graph process constructs a graph in a series of rounds, starting with the empty graph on vertices. In each round, a player is offered a vertex chosen uni…
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…
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…
Long cycles in percolated expanders
Maurício Collares, Sahar Diskin, Joshua Erde +1
Given a graph and probability , we form the random subgraph by retaining each edge of independently with probability . Given and constants $0<c…
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…
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 as the density increases fro…