Fair representation by independent sets

Abstract: For a hypergraph

H

let

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}, l d o t s, V_{m})

of

V (H)

if

(resp.

) for all

i l e 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.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: Fair representation by independent sets