Supermodular colouring theorem

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

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

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

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

Theorem. Let [math]p_1[/math] and [math]p_2[/math] be integer set functions on ground set S such that

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

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