4
$\begingroup$

Show: For a complete graph $K_{n}$, there is a coloring of the edges with $2$ colors, such that the number of monochromatic $k$-Cliques is a maximum of $\binom{n}{k}2^{1-\binom{k}{2}}$.

I do not know where to begin on this exercise. As a hint, our professor gave us the following pre-exercise, which I have been able to solve:

Let $n \in \mathbb N$, and $\mathcal{K}$ be the set of permutations possible for a set $\{1,...,n\}$. Let $\sigma \in \mathcal{K}, $ such that $\sigma: [n] \to [n]$ is a randomly selected permutation. Find the probability space, define random variable $X$ as the number of fixed points and find $\mathbb E[X]$.

How do the two questions fit together? I am lost.

$\endgroup$
1
  • $\begingroup$ I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most". $\endgroup$
    – BGM
    Nov 20, 2018 at 16:17

1 Answer 1

3
+50
$\begingroup$

This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.

Denote by $I_{x_1,...,x_k}$ the indicator function of the k-clique of vertices ${x_1,...,x_k}$(for a random coloring of $K_n$). Thus $I_{x_1,...,x_k}$ is 1 if ${x_1,...,x_k}$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $\sum_{x_1,...,x_k}I_{x_1,...,x_k}$ where the sum is taken over all ${n\choose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${n\choose k}P({x_1,...,x_k}$ is monochromatic $) = {n\choose k}2^{1-{k\choose 2}}$, by linearity of expectation and also by $E(I_A)=P(A)$, for any event set A, so you can find at least one graph with ${n\choose k}2^{1-{k\choose 2}}$ monochromatic k-Cliques.

For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{k\choose 2}}$ because ${x_1,...,x_k}$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $k \choose 2$ edges is red is exactly $\frac{1}{2}$)

$\endgroup$

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.