4
$\begingroup$

Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta>10$. Prove that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A|\leq O(\dfrac{n\ln\delta}{\delta})$, and each vertex of $B$ has $\geq 1$ neighbor in $A$ and $\geq 1$ neighbor in $B$.

[Source: The probabilistic method, Alon and Spencer]

I would like to set up a probabilistic argument here, but not sure how to start.

$\endgroup$
  • $\begingroup$ My best guess is for each vertex of the graph, randomly and independently place it in set $A$ with probability $\ln \delta/\delta$, and otherwise place in set $B$. Then apply the Lovasz Local Lemma. However, I'm not really getting the details to work out easily -- perhaps there is a better method. $\endgroup$ – Tyler Seacrest Oct 20 '14 at 15:52
0
$\begingroup$

I propose this algorithm for the partition:

  1. Select an unassigned vertex and put it in $A$.
  2. Put all the unassigned neighbors of vertices in $A$ in $B$.
  3. Put all the unassigned neighbors of vertices in $B$ in $A$.
  4. Repeat steps 2 and 3 until no more progress is made. If graph is partitioned, you're done. If not (in case of multiple components), return to 1.

This may not be a probabilistic argument, but at least it's an argument!

Edit: Oops, I completely missed $|A| \leq O(\frac{n \ln \delta}{\delta})$. Perhaps this would work:

  1. Select an unassigned vertex and put it in $A$.
  2. Put all the unassigned neighbors of vertices in $A$ in $B$.
  3. Select an unassigned vertex without any neighbors in $B$ and put it in $A$.
  4. Repeat steps 2 and 3 until no more progress is made. If graph is partitioned, you're done. If not, repeat steps 1 and 2 until graph is partitioned.

This will put at least $\delta$ times as many vertices into $B$ as $A$ at first, but then will taper off. I'm not sure how to ensure that $|A| \leq O(\frac{n \ln \delta}{\delta})$, but this is a possible starting point.

$\endgroup$
  • 2
    $\begingroup$ Consider when you have a bunch of $\delta$-cliques with one element from each assigned to $A$. Then we connect each element assigned to $B$ some nodes which is connected only to elements previously assigned to $B$. Quite frankly, we could put an arbitrary number of such new nodes into the graph, and this would cause $\frac{|A|}{n}$ to approach $1$ as you add nodes in this clearly worst-case scenario. However, if you choose each element in (1) and (3) to maximize the number of unassigned neighbors, this scenario can't occur. $\endgroup$ – Andrew Koche Oct 29 '14 at 16:55

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.