Mihyun Kang

activity

20162026

most citedResolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs

2 citations · 2 across the 19 of their papers we have counts for

collaborators

20 papers

math.PR2026

Counting subgraphs in bounded-size Achlioptas processes

Mihyun Kang, Oliver Riordan

Achlioptas processes such as the Bohman--Frieze process are much harder to analyse than the classical Erdős--Rényi process, due to the dependence between edges added at different s…

math.CO2026

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…

math.PR2026

Uniqueness and locality of the ground state of the disordered Monomer-Dimer models on independently weighted Unimodular Bienaymé-Galton-Watson trees

Mihyun Kang, Mike Liu

Consider a finite graph $G = (V (G), E (G))$ and two continuous weight distributions $ω$ and $ξ$ , for which we only assume that $ξ$ is lower bounded. Next, independently draw weights $(…

math.CO2026

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 $2$ -connected components, or blocks. This includes the class…

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 percolated graphs via the Ising model

Anna Geisler, Mihyun Kang, Michail Sarantis +1

Given a graph $G$ , we form a random subgraph $G_{p}$ by including each edge of $G$ independently with probability $p$ . We provide an asymptotic expansion of the expected number of in…

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.CO2025

Universality of the matching number in percolated regular graphs

Sahar Diskin, Mihyun Kang, Lyuben Lichev

Fix a sequence of $d$ -regular graphs $(G_{d})_{d \in N}$ and denote by $G_{d, p}$ the graph obtained from $G_{d}$ after edge-percolation with probability $p = c / d$ , for a constant…

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

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

Bootstrap percolation on the high-dimensional Hamming graph

Mihyun Kang, Michael Missethan, Dominik Schmid

In the random $r$ -neighbour bootstrap percolation process on a graph $G$ , a set of initially infected vertices is chosen at random by retaining each vertex of $G$ independently wit…

math.PR2024

Bootstrap Percolation on the Binomial Random $k$ -uniform Hypergraph

Mihyun Kang, Christoph Koch, Tamás Makai

We investigate the behaviour of $r$ -neighbourhood bootstrap percolation on the binomial $k$ -uniform random hypergraph $H_{k} (n, p)$ for given integers $k \geq 2$ and $r \geq 2$ . In $r$ -…

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.CO2019★ 2 cited

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 $G (n, p)$ with $p = d / n$ and $d > λ n^{1/2}$ , for some large $λ > 0$ . In this process, each vertex has a state in ${- 1, + 1}$ a…

math.PR2016

A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs

Nikolaos Fountoulakis, Mihyun Kang, Christoph Koch +1

A bootstrap percolation process on a graph with infection threshold $r \geq 1$ is a dissemination process that evolves in time steps. The process begins with a subset of infected ver…

Counting subgraphs in bounded-size Achlioptas processes

Sampling from the antiferromagnetic Ising model on bipartite, regular expander graphs

Uniqueness and locality of the ground state of the disordered Monomer-Dimer models on independently weighted Unimodular Bienaymé-Galton-Watson trees

Block-weighted random graphs: planar and beyond

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 percolated graphs via the Ising model

Counting independent sets in expanding bipartite regular graphs

The law of the circumference of sparse binomial random graphs

Universality of the matching number in percolated regular graphs

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

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

Bootstrap percolation on the high-dimensional Hamming graph

Bootstrap Percolation on the Binomial Random k-uniform Hypergraph

Catching a robber on a random k-uniform hypergraph

Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs

A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs

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

Bootstrap Percolation on the Binomial Random $k$ -uniform Hypergraph

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