<p>This is a special version of the <a href="https://en.wikipedia.org/wiki/Beck%E2%80%93Fiala_theorem" rel="nofollow noreferrer">Beck-Fiala theorem</a>.
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.</p>

CC BY-SA 3.0
2017-08-06T13:00:27.913Z
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$?
Lyla
CC BY-SA 3.0
2017-08-06T19:26:00.780Z
@Lyla Sorry, I missed the $/2$'s, is it OK now?
domotorp
CC BY-SA 3.0
2017-08-06T12:03:41.343Z
2017-08-06T19:24:13.370Z
2017-08-06T19:24:13.370Z
domotorp
<p>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)$.  </p>

<p>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.<br>
(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). </p>

CC BY-SA 3.0
2017-08-06T04:31:33.890Z
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.
Mikhail Rudoy
CC BY-SA 3.0
2017-08-06T04:35:39.983Z
What I was trying to say is that the condition will hold in both subgraphs (will edit the post). It is a vertex partition.
Lyla
CC BY-SA 3.0
2017-08-06T04:54:11.010Z
Cool. That makes perfect sense :)
Mikhail Rudoy
<graph-theory><co.combinatorics><pr.probability><randomized-algorithms><combinatorics>
Directed graph with bounded in-deg can be partitioned in a balanced way
Lyla
# Directed graph with bounded in-deg can be partitioned in a balanced way

(Asked by: username_0 on 2017-08-05)

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

**Tags:** graph-theory, co.combinatorics, pr.probability, randomized-algorithms, combinatorics

> **Comments:**
> **username_1**: 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.  
> **username_0**: What I was trying to say is that the condition will hold in both subgraphs (will edit the post). It is a vertex partition.  
> **username_1**: Cool. That makes perfect sense :)  

---

## 1 answers

### Answer by username_2 on 2017-08-06. Score: 3 | Accepted answer

This is a special version of the [Beck-Fiala theorem](https://en.wikipedia.org/wiki/Beck%E2%80%93Fiala_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.

> **Comments:**
> **username_0**: 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$?  
> **username_2**: @username_0 Sorry, I missed the $/2$'s, is it OK now?  

---

