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

CREATORYatin Dandi, David Gamarnik, Haodong Zhu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-03774

Browse the full library · About the Tower of Babel