The Connection between the Number of Realizations for Degree Sequences and Majorization

The \emph{graph realization problem} is to find for given nonnegative integers $a_1,\dots ,a_n$ a simple graph (no loops or multiple edges) such that each vertex $v_i$ has degree $a_i\mathrm{.}$ Given pairs of nonnegative integers $(a_1,b_1),\dots ,(a_n,b_n),$ (i) the \emph{bipartite realization problem} ask whether there is a bipartite graph (no loops or multiple edges) such that vectors $(a_1,\mathrm{.}\mathrm{.}\mathrm{.},a_n)$ and $(b_1,\mathrm{.}\mathrm{.}\mathrm{.},b_n)$ correspond to the lists of degrees in the two partite sets, (ii) the \emph{digraph realization problem} is to find a digraph (no loops or multiple arcs) such that each vertex $v_i$ has indegree $a_i$ and outdegree $b_i\mathrm{.}$\ The classic literature provides characterizations for the existence of such realizations that are strongly related to the concept of majorization. Aigner and Triesch (1994) extended this approach to a more general result for graphs, leading to an efficient realization algorithm and a short and simple proof for the Erd\H{o}s-Gallai Theorem. We extend this approach to the bipartite realization problem and the digraph realization problem.\ Our main result is the connection between majorization and the number of realizations for a degree list in all three problems. We show: if degree list $S^{\mathrm{\prime }}$ majorizes $S$ in a certain sense, then $S$ possesses more realizations than $S^{\mathrm{\prime }}\mathrm{.}$ We prove that constant lists possess the largest number of realizations for fixed $n$ and a fixed number of arcs $m$ when $n$ divides $m\mathrm{.}$ So-called \emph{minconvex lists} for graphs and bipartite graphs or \emph{opposed minconvex lists} for digraphs maximize the number of realizations when $n$ does not divide $m$.