{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-03","reactions":{}}