prove or supply counter example about graph

Let $G = (V, E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup ... \cup V_n$ be a partition of its $4n$ vertices into n pairwise disjoint subsets, each of cardinality 4. Is it true that there must be an independent set of $G$ containing precisely one vertex from each $V_i$? (Prove or supply a counter example.)

I think this is not right because just consider square with four vertices and four edges,but I have doubt that it is proper counter example.please help with your knowledge,thank you very much.

actually this is exercise 4 of chapter 5 from alon spencer probabilistic method.so I also tag this question as mentioned.

Solution 1:

Despite appearing in the local lemma chapter of Alon and Spencer's Probabilistic Method, this problem is (to the best of my knowledge) not solvable probabilistically. In particular, any attempt at the using the local lemma fails because the dependency is too high. For example, if we choose a uniform element from each of $V_1, V_2, \dots, V_n$, and define $A_{vw}$ for each edge $vw$ of the cycle to be the event that both endpoints of $vw$ are chosen, then $\Pr[A_{vw}] =\frac1{16}$, but there are $14$ other events that $A_{vw}$ is not independent from: if $v \in V_i$ and $w \in V_j$, then there are $7$ other edges incident to vertices in $V_i$, and $7$ more incident to vertices in $V_j$.

(So this is my motivation for answering this very old question: it's an important exercise from a well-known textbook, and the other answer solves it incorrectly.)

Here's an argument that does not use probability. If $G$ is the cycle of length $4n$, number its vertices $\{1, 2, \dots, 4n\}$. Call the edges $\{(1,2), (3,4), \dots, (4n-1,4n)\}$ the odd edges and $\{(2,3), (4,5), \dots, (4n,1)\}$ the even edges.

First, arbitrarily partition $V_i = W_{2i-1} \cup W_{2i}$ for each $i$ so that $|W_{2i-1}| = |W_{2i}| = 2$ and $W_{2i-1} \cap W_{2i} = \varnothing$. We choose $w_i \in W_i$ for each $i \in \{1, \dots, 2n\}$ so that if $i\ne j$, $w_i$ and $w_j$ aren't joined by an odd edge. This can be done greedily: choosing $w_1 \in W_1$ puts a restriction only on one $W_i$ (the one containing the vertex joined by the odd edge from $w_1$) so we can pick the other element of $W_i$, which puts a restriction on only one $W_j$, and we keep going until all elements are assigned.

Second, let $V_i' = \{w_{2i-1}, w_{2i}\} \subset V_i$, where $w_{2i-1}, w_{2i}$ were chosen earlier. We choose $v_i \in V_i'$ for each $i \in \{1, \dots, n\}$ so that if $i \ne j$, $v_i$ and $v_j$ aren't joined by an even edge. Once again, we can do this greedily: each $V_i'$ has two options, and choosing one of them eliminates an option from at most one other $V_j'$.

Now we have chosen a $v_i \in V_i$ for each $i$. We cannot have $v_i$ and $v_j$ joined by an edge for $i \ne j$; if that edge were odd, we would not have chosen $v_i$ and $v_j$ in the first step, and if it were even, we would not have chosen $v_i$ and $v_j$ in the second step. So $\{v_1, v_2, \dots, v_n\}$ is the independent set we wanted.

If you're still confused, try reading my answer to this question. It finds a $4$-coloring, which is stronger than an independent set, and though it's for $4\cdot 25$ vertices the answer is fully general. I think my argument there is more clear, though the idea is the same.

Our inability to use the local lemma here strikes again when we ask a more general question. Suppose that $G$ is not a $4n$-cycle but a general graph with maximum degree $\Delta$ which is partitioned into classes $V_1, V_2, \dots, V_n$. When can we choose an independent transversal: an independent set $\{v_1, v_2, \dots, v_n\}$ of $G$ with $v_i \in V_i$ for each $i$?

• Alon (The linear arboricity of graphs, 1988) uses the local lemma to show that if $|V_i| \ge 2e\Delta$ for each $i$, then an independent transversal always exists. That result would solve this exercise if we had $|V_1|, \dots, |V_n| = 11 > 4e$ instead of $|V_1|, \dots, |V_n| = 4$.

• Haxell (A note on vertex list coloring, 2001) uses a variant of Hall's theorem for hypergraphs to show that having $|V_i| \ge 2\Delta$ for each $i$ is enough (in particular, generalizing this exercise). By the way, this result is best possible in the sense that it cannot hold for $c\Delta$ with $c < 2$.