pith. sign in

arxiv: 1611.03196 · v1 · pith:HJHTPACVnew · submitted 2016-11-10 · 🧮 math.CO

Fair representation by independent sets

classification 🧮 math.CO
keywords fairlyalmostbetaindependentpartitionrepresentedsetsedge
0
0 comments X
read the original abstract

For a hypergraph $H$ let $\beta(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, \ldots, V_m)$ of $V(H)$ if $|S\cap V_i|\ge \lfloor\frac{|V_i|}{\beta(H)}\rfloor$ (resp. $|S\cap V_i|\ge \lfloor\frac{|V_i|}{\beta(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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.