5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ That is not a counterexample, as in the case of the square, i.e., $n=1$, there is only one part in the partition and any single vertex is certainly an independent set. $\endgroup$
    – Casteels
    May 10, 2014 at 5:57

2 Answers 2

9
+100
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ Can you clarify the greedy algorithm? For the "put a restriction on only one $W_j$", it also requires "$W_j$ has no restriction already", otherwise we can't pick an element from $W_j$ subsequently. IE Suppose $V_1 = \{ 1, 3, 5, 7 \}, W_1 = \{1, 3 \}, W_2 = \{ 5, 7 \}$ and $ V_2 = \{ 2, 4, 6, 8 \}, W_3 = \{2, 6 \}, W_4 = \{ 4, 8 \}$, and I chose $ w_1 = 1, w _ 2 = 5$, then what is $w_3$? $\endgroup$
    – Calvin Lin
    Dec 14, 2020 at 16:05
  • 1
    $\begingroup$ Ah, perhaps the greedy algorithm works not by selecting $W_i$ in order, but working with $|W_i | = 1$, else $W_i$ in order. This way, I believe that your approach will work. $\endgroup$
    – Calvin Lin
    Dec 14, 2020 at 16:08
  • 1
    $\begingroup$ Yes. Another way to put it is that each step involves picking a maximum independent set from a union of even cycles. $\endgroup$ Dec 14, 2020 at 16:32
0
$\begingroup$

The answer given by Misha can be reworked as a LLL based proof as follows;

The $W_i$s partition the vertex set of $G$ into $2n$ sets each of size 2. Choose an element uniformly at random from each $W_i$. For each odd edge $e=(a,b)$, let $A_e$ be the bad event that both $a$ and $b$ are picked. We may assume that the vertex $a$ is in $W_i= \{a,x\}$ and the vertex $b$ is in $W_j=\{b,y\}$. The only possible event to which $A_e$ is dependent is $A_{e'}$ where $e'=(x,y)$. ($e'$ is the only possible odd edge). Thus d=1. Since $\mathbb{P}[A_e]=\frac{1}{4} < \frac{1}{e}$, all bad events can be avoided simultaneously. Thus no odd edge will be present in the $2n$ vertices picked. Repeat a similar argument and avoid the even edges.

$\endgroup$
4
  • $\begingroup$ Why should $(x,y)$ be an edge? In general, we should also expect to see cases where there's some odd edge $e'$ containing $x$ and another odd edge $e''$ containing $y$, in which case $A_e$ is dependent on both $A_{e'}$ and $A_{e''}$. $\endgroup$ Dec 3, 2021 at 20:32
  • $\begingroup$ If $(x,y)$ is not an edge, there is one less dependency. The dependency graph contains only the events related to the odd edges. The even edges aren't considered in the first stage. $\endgroup$ Dec 4, 2021 at 19:33
  • $\begingroup$ Yes, I am saying that there is a case where there are two odd edges $e'$ and $e''$, one containing $x$ and one containing $y$. For example, when $n=2$, we could have $W_1 = \{1,5\}$ and $W_2 = \{2,8\}$. Then $A_{12}$ is dependent on both $A_{56}$ and $A_{78}$. $\endgroup$ Dec 4, 2021 at 19:35
  • $\begingroup$ I see the trouble. $\endgroup$ Dec 4, 2021 at 19:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .