Covering a supermodular-like function in a mixed hypergraph

Abstract

In this paper, we solve a conjecture by Szigeti in [Matroid-rooted packing of arborescences, submitted], which characterizes a mixed hypergraph $\mathcal{F}=(V,\mathcal{E}\cup \mathcal{A})$ having an orientation $\overrightarrow{\mathcal{E}}$ of $\mathcal{E}$ such that $e_{\overrightarrow{\mathcal{E}}\cup \mathcal{A}}(\mathcal{P})\ge {\sum }_{X\in \mathcal{P}}h(X)-b(\cup \mathcal{P})$ for every subpartition $\mathcal{P}$ of $V$, where $h$ is an integer-valued, intersecting supermodular function on $V$ and $b$ a submodular function on $V$. As a corollary, another conjecture in the same paper is confirmed, which characterizes a mixed hypergraph having a packing of mixed hyperarborescences such that their roots form a basis in a given matroid, each vertex $v$ belongs to exactly $k$ of them and is the root of at least $f(v)$ and at most $g(v)$ of them.