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?

  • 2
    $\begingroup$ 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$. $\endgroup$ – Kevin P. Costello Aug 10 '17 at 6:54
  • $\begingroup$ 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?! $\endgroup$ – Erel Segal-Halevi Aug 10 '17 at 22:21
  • $\begingroup$ 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. $\endgroup$ – Kevin P. Costello Aug 10 '17 at 23:12
  • $\begingroup$ 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! $\endgroup$ – Ron P Aug 26 '17 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$.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Erel Segal-Halevi Aug 18 '17 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.