Finite sequences realizable by degree difference in digraphs

Question

Let $n>0$ be an integer, and let $[n] = \{1,\ldots,n\}$. A function $f:[n]\to \mathbb{Z}$ is said to be in- and out-degree-realizable (or io-realizable for short) if there is a directed graph $G = ([n], E)$ where $E \subseteq [n]\times[n]$ such that for all $k\in[n]$ we have $$f(k) = \text{deg}_+(k) - \text{deg}_-{k}$$ where $\text{deg}_+(\cdot)$ denotes the in-degree of $k$, and $\text{deg}_-{k}(\cdot)$ denotes the out-degree of $k$.

Of course, any io-realizable functions obeys the condition $\sum_{k\in[n]} f(k) = 0$.

If $f:[n]\to \mathbb{Z}$ obeys the condition above and $|f(k)| < n/2$ for all $k\in[n]$, is $f$ io-realizable?

Answer 1

Yes. Case $n\leqslant 2$ is clear, so assume that $n\geqslant 3$. We may use the following well-known

Lemma. Let $G=(V,E)$ be an undirected graph (multiple edges allowed, loops not allowed) and $g:V\to \{0,1,2,\dots\}$ be a function such that $\sum_{v\in V} g(v)=|E|$. Then there exists an orientation of $G$ with out-degrees $g(v)$, $v\in V$, if and only if $\sum_{v\in U} g(v)\geqslant |E(U)|$ for any subset $U\subset V$, where $E(U)$ denotes the set of edges with both endpoints in $U$.

Now assume that we have $2k$ odd numbers between the values of your function $f$. Construct the undirected graph $G$ on the vertex set $[n]$ with exactly $2k$ odd degrees and maximal possible number of edges. Namely, if $n$ is odd, remove $k$ disjoint edges from the complete graph; if $n$ is even remove $n/2-k$ disjoint edges from the complete graph. Now define $g(v)=(f(v)+\deg(v))/2$, where the vertices are enumerated so that this $g(v)$ is integer for all $v\in [n]$. We have $g(v)\geqslant n-2-(n-1)/2=(n-3)/2\geqslant 0$ and $\deg(v)-g(v)=(-f(v)+\deg(v))/2\geqslant (n-3)/2\geqslant 0$.

We want an orientation of $G$ with outdegrees $g(v)$. We need to check that $\sum_v g(v)=|E(G)|$ (holds since $\sum_v f(v)=0$, $\sum_v \deg(v)=2|E(G)|$) and $\sum_{v\in U} g(v)\geqslant |E(U)|$ for any subset $U\subset V$. Thus $$ \sum_{v\in U} g(v)\geqslant |U|(n-3)/2\geqslant |U|(|U|-1)/2\geqslant |E(U)|$ $$ unless $|U|=n-1$ or $|U|=n$. If $|U|=n$, we have $\sum_{v\in U} g(v)=|E(G)|=|E(U)|$. If $|U|=n-1$, $U=[n]\setminus \{v\}$, then $\sum_{v\in U} g(v)=|E(G)|-g(v)=|E(U)|+\deg(v)-g(v)\geqslant |E(U)|$, that finishes the proof.