Id: arxiv/2602.03774 Url: https://arxiv.org/abs/2602.03774 Tags: math.CO, math.PR Score: 0 Title: Minimum Number of Monochromatic Subgraphs of a Random Graph Domain: math.CO Source: arxiv Authors: Yatin Dandi, David Gamarnik, Haodong Zhu Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-03 Page: https://delphi.science/r/arxiv/2602.03774 We consider the problem of minimizing the number of monochromatic subgraphs of a random graph, when each node of the host graph is assigned one of the two colors. Using a recently discovered contiguity between appearance of strictly balanced subgraphs $F$ in a random graph, and random hypergraphs where copies of $F$ are generated independently, we show that the minimum value converges to a limit, when the expected number of copies of $F$ is linear in the number of nodes $|V|$. Furthermore, using the connections with mean field spin glass models, we obtain an asymptotic expression for this…