Let $G = (V,E) $ be a finite graph. For any set $ W $ of vertices and any edge $e \in E $, define the indicator function $$ I_W(e) = \begin{cases} 1 , &\ e \textrm{ connects } W \textrm{ and } W^c \\ \ \\ 0,&\ \textrm{otherwise} \\ \ \\ \end{cases} $$

Set $ N_W := \sum_{e \in E} I_W(e)$. Show that there exists $ W \subset V$ such that $N_W \ge \frac{1}{2} \cdot |E| $


The idea is:

Suppose we toss a fair coin repeatedly.(independent)

$ W \subset V $ denotes this process.

In other words: For every $ v \in V $ we toss a coin. If the coin shows head, we say that $ v \in W$, otherwise $ v \notin W$. In this way $N_W$ can be regarded as a random variable. I'm sure that the expected value can us help to solve the problem. Unfortunately I'm stucked here. Remark: I'm sure that there exists other solutions, but I want to solve it with my attempt.

Thank you for your help.

  • $\begingroup$ $e \in W$, an edge that is an element of a set of vertices? $\endgroup$ – Paul Dec 11 '17 at 15:00
  • $\begingroup$ @Paul you're right. I meant $ e \in E $ $\endgroup$ – RukiaKuchiki Dec 11 '17 at 16:01
  • $\begingroup$ Have you found out what the probability that an edge $e \in E$ crosses $W$ is? $\endgroup$ – Manuel Lafond Dec 11 '17 at 16:12

When starting to learn the probabilistic method, it's often helpful to write out the expected values and summation very explicitly. Often the trick is taking the thing you want to count and counting it in a different way, which in its basic form corresponds to swapping the order of two sums. Let's see this in action with your idea.

$$ \mathbb{E}(N_W) = \sum_W P(W) N_W = \sum_W P(W) \sum_{e\in E} I_W(e) = \sum_{e\in E} \sum_W P(W) I_W(e) $$

We might interpret $\sum_W P(W) I_W(e)$ for a given $e \in E$ as the probability that $e \in [W, W^c]$ over all possible choices of $W$. (You could also just count this sum out directly.) You should be able to argue that this is $\frac{1}{2}$, from which the result immediately follows (the specifics I'll leave to you; they just involve finishing calculating the expected value and interpreting it).

The main idea here is that we switched from counting over all possible $W$ to counting over all edges $e$ first. It was much easier to look at each edge individually, since the edges of the graph are fixed and not probabilistic, then to see how the probabilistic components interact with those fixed components.

(Note that this is actually a really important problem that we've solved: you can take any graph and turn it into a bipartite graph with losing only half the edges.)

  • $\begingroup$ "In this thesis we study hypergraphs using the probabilistic method, where by the probabilistic method we mean the taking of sums in two different ways." – V. Chvátal $\endgroup$ – Misha Lavrov Dec 11 '17 at 17:02
  • $\begingroup$ @Bob Krueger First of all: Thank you for your amazing answer! I have a question: Can you explain why $ \mathbb{E}(N_W) $ = $ \sum_W P(W) N_W$ ? My apologies for this simple question. I'm just a little confused. I know that $ \mathbb{E} (X)$ = $ \sum_{x \in X(\Omega)} x \cdot P(X=x) $ The rest of your answer is clear: Now I have found out that the expected value is $\frac{1}{2}$ |E|. I'm almost done, I guess. I only have to explain why there is a $W$ such that $ N_W \ge \mathbb{E}(N_W) $, right? $\endgroup$ – RukiaKuchiki Dec 11 '17 at 19:52
  • $\begingroup$ We can define expected value as the a weighted average over all possible values of a random sample, which is what your given definition does, or we may define expected value as a weighted average over all outcomes in the sample space, which is what my definition is. We take the set of all possible $W$ as the sample space, and $P(W)$ as the probability of a given $W$ occurring in the sample space. $\endgroup$ – Bob Krueger Dec 11 '17 at 20:56
  • $\begingroup$ You're definition of expected value follows from the one I made here: $ \sum_W P(W) N_W = \sum_n n \sum_{W\text{ with } N_W = n} P(W) = \sum_n n \cdot P(N_W = n)$. Also, explaining why there is a $W$ such that $N_W \geq \mathbb{E}(N_W)$ can be done easily by contradiction. $\endgroup$ – Bob Krueger Dec 11 '17 at 20:57

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.