# Bi-set

Let V be a finite ground set. A pair $X=(X_O,X_I)$ of subsets of V is called a bi-set if $X_I \subseteq X_O \subseteq V$. We call $X_O$ the outer member of X and $X_I$ the inner member of X. The following notions are used in relation to bi-sets:

• The intersection of two bi-sets X and Y is $X \cap Y=(X_O \cap Y_O,X_I \cap Y_I)$.
• The union of X and Y is $X \cup Y=(X_O \cup Y_O,X_I \cup Y_I)$.
• We say that $X \subseteq Y$ if $X \cap Y=X$ and $X \cup Y=Y$.
• X and Y are independent if $X_O \cup Y_O=V$ or $X_I \cap Y_I=\emptyset$.

If X is a bi-set, we say that an arc uv covers X if $u \in V \setminus X_O$ and $v \in X_I$. An undirected edge uv covers X if one of its endnodes is in $V \setminus X_O$ and the other is in $X_I$.

For some examples of bi-sets in graph optimization, see Bérczi and Frank [1][2].

## References

1. K. Bérczi, A. Frank, Variations for Lovász' submodular ideas, in: M. Grötschel, G.O.H. Katona (eds.), Building Bridges Between Mathematics and Computer Science, Bolyai Society, Springer 2008, pp. 137-164. EGRES Technical Report link.
2. K. Bérczi, A. Frank, Packing Arborescences, EGRES Technical Report no. 2009-04.