Minimum Number of Monochromatic Subgraphs of a Random Graph
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.03774
curl -X POST /api/v1/records/arxiv/2602.03774/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.03774/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'