Large Monochromatic Components in Colored Random Graphs
We study the size of the largest monochromatic connected component that must appear in any edge-coloring of a random graph. Let $G\sim G(n,p)$ with $p\gg 1/n$ and $p=o(1)$, and write $np=he^h$. We show that, with high probability, every $2$-edge-coloring of $G$ contains a monochromatic connected component of order at least $n-Θ(ne^{-h})$. Moreover, we construct colorings showing that this bound is best possible up to constant factors. We extend this result to three colors: for $p\gg 1/n$ and $p=o(1)$, with high probability every $3$-edge-coloring of $G$ contains a monochromatic connected…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.23334
curl -X POST /api/v1/records/arxiv/2607.23334/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.23334/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'