Minimum Number of Monochromatic Subgraphs of a Random Graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918321667964928 |
|---|---|
| author | Dandi, Yatin Gamarnik, David Zhu, Haodong |
| author_facet | Dandi, Yatin Gamarnik, David Zhu, Haodong |
| contents | 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 limit as the normalized expected number of copies of $F$ and the size of $F$ diverge to infinity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_03774 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Minimum Number of Monochromatic Subgraphs of a Random Graph Dandi, Yatin Gamarnik, David Zhu, Haodong Combinatorics Probability 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 limit as the normalized expected number of copies of $F$ and the size of $F$ diverge to infinity. |
| title | Minimum Number of Monochromatic Subgraphs of a Random Graph |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2602.03774 |