7 papers
A first order phase transition for lower tails in sparse random graphs
Byron Chin
We study the graphon variational problem that governs lower tail large deviations of the number of copies of a fixed nonbipartite graph in a sparse Erdős--Rényi random graph. O…
Extremal subtrees of critical beta-splitting trees
Anna Brandenberger, Byron Chin, Elchanan Mossel
We determine the most and least likely shapes for an instance of the critical beta-splitting tree via a connection to data compression and Huffman's minimum redundancy codes. This…
The random stable roommates problem typically has no solution
Byron Chin, Marcus Michelen
Assume that potential roommates each have an ordered preference of the others. A stable matching is a perfect matching of the roommates in which no two unmatched…
Asymptotics for the harmonic descent chain and applications to critical beta-splitting trees
Anna Brandenberger, Byron Chin, Elchanan Mossel
Motivated by the connection to a probabilistic model of phylogenetic trees introduced by Aldous, we study the recursive sequence governed by the rule $x_n = \sum_{i=1}^{n-1} \frac{…
Exact threshold and limiting distribution for non-linear Hamilton cycles
Byron Chin
For positive integers , an -cycle in an -uniform hypergraph is a cycle where each edge consists of vertices and each pair of consecutive edges interse…
Matching Algorithms in the Sparse Stochastic Block Model
Anna Brandenberger, Byron Chin, Nathan S. Sheffield +1
The stochastic block model (SBM) is a generalization of the Erdős--Rényi model of random graphs that describes the interaction of a finite number of distinct communities. In sparse…
Structure of lower tails in sparse random graphs
Byron Chin
We study the typical structure of a sparse Erdős--Rényi random graph conditioned on the lower tail subgraph count event. We show that in certain regimes, a typical graph sampled fr…