# Probability of good colorings in randomly-colored graphs

Each vertex in a graph is randomly and independently colored either red or blue with equal probability. A coloring is called $r$-good, for some fraction $r\in[0,1]$, if at least a fraction $r$ of the edges touch at least one red vertex. Define $p(G,r)$ as the probability that a graph $G$ is $r$-good. Obviously $p(G,r)$ is decreasing with $r$.

What is the largest $r$ such that $p(G,r)>1/2$ for all finite graphs $G$?

There is an upper bound of $2/3$ (as noted by Kevin P. Costello) and a lower bound of $1/2$.

• For the upper bound, let $G$ be the clique with $3$ vertices. It has eight different colorings: one is 0-good, three are 2/3-good and four are 1-good. Therefore, $p(G,2/3)= 7/8$, but for every $r>2/3$, $p(G,r)\leq 1/2$.

• For the lower bound, consider an arbitrary graph $G$. For every coloring of $G$, either it or its opposite colorng is $1/2$-good; therefore $p(G,1/2)\geq 1/2$. To prove that $p(G,1/2)>1/2$, it is sufficient to prove the existence of a coloring that both it and its opposite are $1/2$-good. To construct such a coloring, assign a unique number to each vertex of $G$, and assign to each edge $(u,v)$ the number $(u+v)/2$. Let $D$ be the median of all edges' numbers. Color all vertices smaller than $D$ red and all other vertices blue. Both this coloring and its opposite are $1/2$-good. Hence $p(G,1/2)>1/2$.

Intuitively, the 3-clique seems to be the worst case, since when there are many vertices, the expected number of good edges is $3/4$. So my conjecture is that the real value is 2/3. In other words:

Conjecture. For every finite graph $G$, $p(G,2/3)>1/2$.

Is this true? Alternatively, can you prove tighter bounds?

• For $K_3$ we have $p(r) = 1/2$ for any $r>2/3$. It wouldn't surprise me if the lower bound approached $3/4$ as the size of the graph tended to infinity. With very high probability, a random coloring will have about half the edges connecting red and blue (since different edges being bicolored are pairwise independent). Half the time you have as many red-red edges than blue-blue edges. Unfortunately, this only gets you $1/2-\epsilon$ probability, instead of greater than $1/2$. Aug 10, 2017 at 6:54
• Interesting. So the gap is now [1/2,2/3], and if it ineed increases with the graph size then the real answer should be 2/3. But I do not understand the statement on bicolored edges: if in K3 two edges are bicolored then the third edge cannot be bicolored?! Aug 10, 2017 at 22:21
• This is as the number of edges goes to infinity. In a graph with $m$ vertices, the expected number of bicolored edges is $m/2$, and the variance is $m/4$, so there's concentration by Chebyshev's inequality if nothing else. Aug 10, 2017 at 23:12
• Szemerédi regularity lemma guaranties that the conjecture holds for graphs with sufficiently many vertices. It remains to verify "only" finitely many graphs. Good luck! Aug 26, 2017 at 15:39

For $r > 1/2$, consider the star graph $K_{1,n}$ for large $n$. Half of the time, the central vertex will be red, and the graph will certainly be $r$-good. The other half of the time, the central vertex will be blue, and the graph will be $r$-good only if a fraction $r$ of the other vertices are red. The probability of this event approaches $0$ as $n \rightarrow \infty$. So the probability of a large star graph being $r$-good (for $r > 1/2$) is only slightly greater than $1/2$.
You have defined $p(r)$ to be the smallest probability that a graph is $r$-good. In this case, there may not be a smallest probability; the probabilities approach a limit of $1/2$ (unless of course there is some other graph I have not considered which has a smaller probability of being $r$-good). So, if it is fair to alter the statement of the question to define $p(r)$ as the infimum of all such probabilities, then $p(r) \leq 1/2$ for all $r > 1/2$.
• Indeed, there might be no "smallest probability", but still, for every finite graph the probability is larger than $1/2$. I edited the question to better clarify the intention. Aug 18, 2017 at 9:13