{
  "id": "1611.03196",
  "version": "v1",
  "published": "2016-11-10T06:31:33.000Z",
  "updated": "2016-11-10T06:31:33.000Z",
  "title": "Fair representation by independent sets",
  "authors": [
    "Ron Aharoni",
    "Noga Alon",
    "Eli Berger",
    "Maria Chudnovsky",
    "Dani Kotlar",
    "Martin Loebl",
    "Ran Ziv"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-10T06:31:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "independent set",
      "fair representation",
      "hypergraph",
      "minimal number",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}