Suppose $G$ is a graph with $n$ vertices and $e$ edges, and suppose we color the vertices as black or white with probability 1/2, making independent random choices at each vertex. Let $X$ be the random variable counting the number of edges that connect a white to a black vertex. I have reasoned as follows to find a formula for $E[X]$.

Let $X_{i,j}$ be the indicator random variable for whether $i$ is connected to $j$ and a different color. Then

$$E[X] = \displaystyle\sum_{i<j} P(X_{i,j}=1) = \sum_{i<j}\frac{e}{n}\frac{1}{2} = \frac{e}{2n}\binom{n}{2} = \frac{e(n-1)}{4}$$

I next need to show that this is at least half the size of the maximum. That is to say, if $C_1,C_2,...,C_x$ is every possible coloring, and $E_i$ is the set of edges adjoining distinctly colored vertices under coloring $C_i$, and if $M = \max\{|E|: E=E_i\text{ for some } i\}$, then what I need to show is

$$E[X] \geq M/2$$

No formula

I have convinced myself that there is no formula for $M$ in terms of the number of edges and nodes because I can draw two graphs with the same numbers of edges and nodes, but which will have different maxima. There may be some non-trivial, valuable lower-bound for this quantity but I don't know it if there is.

Induction from the maximum

I have tried imagining some optimal coloring, and looking at the probability that this algorithm produces it or some variant of it, but I think proceeding in this way assumes the independence of sub-problems in a way that doesn't hold. Namely, if you consider any edge and think of the scenario in which the nodes are colored optimally, or not, the remaining count of edges is affected.


I also considered a proof by contradiction assuming

$$e(n-1)/4 < M/2 \Leftrightarrow e(n-1)<2M$$

However, the product $e(n-1)$ doesn't seem geometrically meaningful in any way that I could imagine being helpful here, and I don't have a formula, so I'm not sure how this would go forward.

[Edit: I have just convinced myself that $M<n$ so that's progress.]


Your computation of $E[X]$ is incorrect. Firstly, it doesn't make sense to have $X_{i,j}$ be the indicator random variable for $i$ is connected to $j$ as well as whether $i$ and $j$ are different colors. You are given a fixed graph $G$, in which either $i$ is connected to $j$ or it isn't.

If we just define $X_{ij}$ for an edge $ij$ to be the indicator random variable which is $1$ if the two endpoints get different colors, then we have $$ E[X] = \sum_{ij \in E(G)} E[X_{ij}] = \sum_{ij \in E(G)} \frac12 = \frac e2. $$ Alternatively, if we say that $G$ is chosen uniformly at random from all graphs with $n$ vertices and $e$ edges, then we can define $X_{ij}$ as you do. But in that case, the probability that $i$ is adjacent to $j$ is not $\frac en$ but $\frac{e}{\binom n2}$, so once again we get $$ E[X] = \sum_{i < j} E[X_{ij}] = \sum_{i < j} \frac{e}{\binom n2} \cdot \frac12 = \binom n2 \cdot \frac{e}{\binom n2} \cdot \frac12 = \frac e2. $$

From computing $E[X] = \frac e2$, you should be able to deduce $E[X] \ge \frac M2$ fairly easily...

  • $\begingroup$ It may help me in the future to understand better why you cannot take $X_{i,j}$ to be the indicator variable as I've defined it. I thought that I could take any two vertices and define the indicator variable that way, since they either do or don't have an edge and do or don't share a color--is there something methodologically wrong with approaching it that way? I guess maybe, defining it that way, I mis-used the probability space over which it's defined whereas defining it your way, it's easier to work with the associated probability? $\endgroup$
    – Addem
    Feb 6 '18 at 17:41
  • $\begingroup$ You can define it that way, but when computing the probability, you shouldn't be adding a factor of $e$ over anything for "the probability that $i$ and $j$ are connected": that probability is either $0$ or $1$. So the ultimate effect is that for $ij \in E$, $X_{ij}$ is the indicator variable for joining a black and a white vertex, and for $ij \notin E$, $X_{ij}$ is identically $0$. (And if that's what you're going for, it makes more sense to define $X_{ij}$ that way from the beginning.) $\endgroup$ Feb 6 '18 at 17:43

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.