Minimum Number of Monochromatic Subgraphs of a Random Graph
Yatin Dandi, David Gamarnik, Haodong Zhu · 2026
Read Minimum Number of Monochromatic Subgraphs of a Random Graph by Yatin Dandi, David Gamarnik, Haodong Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-03774.txt.
Description
Color every vertex of a random graph red or blue, and some subgraphs will end up all one color; how few can you force? Yatin Dandi and 2 co-authors study that minimization problem in a 2026 paper. The host graph is random, the copies counted are of a fixed subgraph shape, and the two-coloring is chosen to minimize monochromatic copies.
Using a recently discovered contiguity between balanced subgraphs in random graphs and random hypergraphs, the authors show the minimum converges to a limit. The convergence holds when the expected number of copies grows linearly in the number of vertices. Connections with mean-field spin glass models then give an asymptotic formula for the limit. The formula applies as the expected copy count and the subgraph's size both grow.
Catalog record
| CREATOR | Yatin Dandi, David Gamarnik, Haodong Zhu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-03774