6
$\begingroup$

I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two sets $V_1, V_2$ in a way that for each vertex $v\in V_1$ (and the same for every vertex in $V_2$) , if the vertex $v$ has out-degree $d(v) \geq c(n)$ in $G$, then its out degree in the corresponding subgraph will be between $\frac{1}{3}d(v)$ and $\frac{2}{3}d(v)$.

I suspect that it is the kind of statements which can be proved by the probabilistic method, using the local lemma (since there are some similar theorems proven in this way). However I couldn't figure out how to do that, will be glad for help.
(I have also asked this question in math.stackexchange a while ago, but since this is a research question, I believe this forum is more appropriate).

$\endgroup$
  • $\begingroup$ Did you mean to ask about partitioning edges? If $V_1$ and $V_2$ partition the set of vertices then there won't be any vertices $v$ present in both the graph induced by $V_1$ and the graph induced by $V_2$, and so your desired condition will vacuously hold. $\endgroup$ – Mikhail Rudoy Aug 6 '17 at 4:31
  • $\begingroup$ What I was trying to say is that the condition will hold in both subgraphs (will edit the post). It is a vertex partition. $\endgroup$ – Lyla Aug 6 '17 at 4:35
  • $\begingroup$ Cool. That makes perfect sense :) $\endgroup$ – Mikhail Rudoy Aug 6 '17 at 4:54
4
$\begingroup$

This is a special version of the Beck-Fiala theorem. Define a set system on the vertices whose sets are the out-neighborhoods of the vertices. The in-degree condition will give that every element is in at most $n$ sets. The theorem states that in this case the elements can be colored with red and blue such that the difference of the red and blue elements in any set is at most $2n-1$. This means that in your digraph the out-degree of each vertex $v$ in the corresponding subgraph is between $d(v)/2-n$ and $d(v)/2+n$, so for your specific question $c(n)\ge 6n$ is sufficient.

$\endgroup$
  • $\begingroup$ Thanks. As far as I understand, the partition is $V_1 = \{ v : x(v) = -1 \}$ and $V_2 = \{ u : x(u) = 1\} $(or all the red vertices and blue vertices). If I am correct, may you please explain why in the induced subgraphs it holds that the degree is between $d(v) -n$ and $d(v) +n$? $\endgroup$ – Lyla Aug 6 '17 at 13:00
  • $\begingroup$ @Lyla Sorry, I missed the $/2$'s, is it OK now? $\endgroup$ – domotorp Aug 6 '17 at 19:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.