{"id":"arxiv/2607.23334","url":"https://arxiv.org/abs/2607.23334","tags":["math.CO","math.PR"],"score":0,"title":"Large Monochromatic Components in Colored Random Graphs","domain":"math.CO","source":"arxiv","authors":["Xiao-Chuan Liu","Xu Yang"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-25","reactions":{}}