Consider the complete graph $K_n$ and suppose we colour each edge of $K_n$ red or blue with equal probability.

For every $k$, $1\leq k \leq n$, give a formula for the expected number of $k$-tuples $X$ of vertices such that all edges between the vertices of $X$ have the same colour.

I have some ideas so far. For $k=1$ we have $E(X)=n$ (the number of vertices) and for $k=2$ we have $E(X)=\begin{pmatrix}n\\2\end{pmatrix}$ (the number of edges). I also think that for $n=k$ we have $E(X)=2\times2^{-\begin{pmatrix}n\\2\end{pmatrix}}$.

However I'm unsure how to make a unified formula for a general $k$. Does such a formula exist?


We use the method of indicator random variables. I will assume, perhaps unreasonably, that a $k$-tuple of vertices is a set of $k$ vertices. The answer does not change if by $k$-tuple we mean a sequence of $k$ distinct vertices. But the answer below does not deal with ordered $k$-tuples of not necessarily distinct vertices.

There are $B=\binom{n}{k}$ such sets. List them as $S_1,S_2,\dots,S_B$. For $i=1$ to $B$, define random variable $X_i$ by $X_i=1$ if all the edges between vertices of $S_i$ have the same colour, and by $X_i=0$ otherwise.

Then the number $Y$ of monochromatic $k$-sets of vertices is given by $Y=X_1+\cdots +X_B$, and by the linearity of expectation we have $E(Y)=E(X_1)+\cdots +E(X_B)$.

For $k\ge 2$, the probability that a $k$-set is monochromatic is $\dfrac{2}{2^{\binom{k}{2}}}$. It follows that $E(Y)=\dfrac{2\binom{n}{k}}{2^{\binom{k}{2}}}$.


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.