2 citations · 2 across the 19 of their papers we have counts for
16 papers · 1 filter
Sampling from the antiferromagnetic Ising model on bipartite, regular expander graphs
Anna Geisler, Mihyun Kang, Michail Sarantis +1
The antiferromagnetic Ising model samples subsets of vertices of a graph with weight decaying exponentially in the number of edges induced. We study the problem of sampling from th…
Block-weighted random graphs: planar and beyond
Mihyun Kang, Zéphyr Salvy, Ronen Wdowinski
We investigate random connected graphs from a block-stable class whose distribution is weighted based on the number of -connected components, or blocks. This includes the class…
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…
Cycle lengths in the percolated hypercube
Michael Anastos, Sahar Diskin, Joshua Erde +3
Let be the random subgraph of the -dimensional binary hypercube obtained after edge-percolation with probability . It was shown recently by the authors that, for ever…
A short proof of a central limit theorem for the order of the giant component and -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-…
Nearly spanning cycle in the percolated hypercube
Michael Anastos, Sahar Diskin, Joshua Erde +3
Let be the -dimensional binary hypercube. We form a random subgraph by retaining each edge of independently with probability . We show that,…
Counting independent sets in percolated graphs via the Ising model
Anna Geisler, Mihyun Kang, Michail Sarantis +1
Given a graph , we form a random subgraph by including each edge of independently with probability . We provide an asymptotic expansion of the expected number of in…
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…
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 in the sparse regime, when $p = Θ\left(\frac{1}{n…
Universality of the matching number in percolated regular graphs
Sahar Diskin, Mihyun Kang, Lyuben Lichev
Fix a sequence of -regular graphs and denote by the graph obtained from after edge-percolation with probability , for a constant…
Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
Sahar Diskin, Joshua Erde, Mihyun Kang +1
Given a graph and , the random subgraph is obtained by retaining each edge of independently with probability . We show that for every , there exis…
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…
Bootstrap percolation on the high-dimensional Hamming graph
Mihyun Kang, Michael Missethan, Dominik Schmid
In the random -neighbour bootstrap percolation process on a graph , a set of initially infected vertices is chosen at random by retaining each vertex of independently wit…
Catching a robber on a random -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…
Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs
Nikolaos Fountoulakis, Mihyun Kang, Tamás Makai
We study majority dynamics on the binomial random graph with and , for some large . In this process, each vertex has a state in a…