# Supermodular colouring theorem

Theorem (Schrijver [1]). Let $p_1$ and $p_2$ be integer intersecting supermodular set functions on ground set S such that $\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}$ for every $X \subseteq S$. Then S can be partitioned into k sets $S_1,\dots,S_k$ such that $|\{i: S_i \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}$ for every $X \subseteq S$.

Bernáth and Király [2] proved the following extension of the theorem.

Theorem. Let $p_1$ and $p_2$ be integer skew-supermodular set functions on ground set S, both with maximal value k. Let furthermore $y \in {\mathbb Z}^S$ be a vector with $0 \leq y \leq k$ and $y(X) \geq \max\{p_1(X), p_2(X)\}$ for every $X \subseteq S$. Then there is a nearly uniform hypergraph H=(S,E) containing k hyperedges such that $|\{e \in E: e \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}$ for every $X \subseteq S$ and $d_H(s) \leq y(s)$ for every $s \in S$.

Another generalization was found by Frank, Király, Pap, and Pritchard [3]:

Theorem. Let $p_1$ and $p_2$ be integer set functions on ground set S such that

• $\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}$ for every $X \subseteq S$, and
• for $i \in\{1,2\}$ and for any intersecting $X,Y$ there exist $U \subseteq X \cup Y$ and $I \subseteq X \cap Y$ such that $p_i(U)+p_i(I) \geq p_i(X)+p_i(Y)$.

Then S can be partitioned into k sets $S_1,\dots,S_k$ such that $|\{i: S_i \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}$ for every $X \subseteq S$.

## References

1. A. Schrijver, Supermodular colourings, in: Matroid theory (Szeged, 1982), Colloq. Math. Soc. János Bolyai, vol. 40, North-Holland, Amsterdam, 1985, pp. 327-343.
2. A. Bernáth, T. Király, Covering skew-supermodular functions by hypergraphs of minimum total size, Operations Research Letters 37 (2009), 345-350. DOI link. EGRES Technical Report.
3. A. Frank, T. Király, J. Pap, D. Pritchard, Characterizing and recognizing generalized polymatroids, DOI link, EGRES Technical Report.