Fair representation by independent sets

Abstract

For a hypergraph $H$ let ${\hat{I}}^2(H)$ denote the minimal number of edges from $H$ covering $V(H)$. An edge $S$ of $H$ is said to represent {\em fairly} (resp. {\em almost fairly}) a partition $(V_1,V_2,\dots ,V_m)$ of $V(H)$ if $|S\cap V_i|\ge \lfloor \frac{|V_i|}{{\hat{I}}^2(H)}\rfloor$ (resp. $|S\cap V_i|\ge \lfloor \frac{|V_i|}{{\hat{I}}^2(H)}\rfloor -1$) for all $i\le m$. In matroids any partition of $V(H)$ can be represented fairly by some independent set. We look for classes of hypergraphs $H$ in which any partition of $V(H)$ can be represented almost fairly by some edge. We show that this is true when $H$ is the set of independent sets in a path, and conjecture that it is true when $H$ is the set of matchings in $K_{n,n}$. We prove that partitions of $E(K_{n,n})$ into three sets can be represented almost fairly. The methods of proofs are topological.