Hi Math Stachexchange,
I am a Computer Science student who are new to this forum. I got troubled by this graph problem. Hearing that it is a useful forum, I wonder if I can get any helps here.
To state the problem:
Say we have a $k$-regular ($k$ even) graph $G$ with $n$ vertices. We wonder if there exist a subset of vertices such that there are at least $n/k$ vertices in the subset that are GOOD. For a GOOD vertex, I mean this vertex have $k/2$ neighbors in the selected subset and $k/2$ vertices neighbors not in this subset.
So there are really 2 parts to this problem. I: For what choices of $k$ we can find such subset? II: How do give a proof?
My thoughts so far:
I have been told for $k=6$, there exist such a subset. So this problem is somehow a generalization of that. Still, I can't really work out the case $k=6$.
I tried probabilistic method. Using this method, I set each vertex is in the subset with probability $1/2$. The standard way would be to apply union bound over undesired events and then take the complement. However, the complement would become intersection over desired events, which is NOT what I want. Because I only need 1 subset to be GOOD, not all subsets (which is equivalent to intersection).
I hope at least some one can give hints on how to solve the $k=6$ case, and perhaps I would generalize the idea from there on.
Some other thoughts: I found this similar question Partition a regular graph such the neighbors of each vertex are nearly evenly split. Only that he/she is asking about an approximate scheme.