Fair representation by independent sets

Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, Ran Ziv

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Scopus citations

Abstract

For a hypergraph H let β(H) denote the minimal number of edges from H covering V(H). An edge S of H is said to represent fairly (resp. almost fairly) a partition (V1, V2, …, Vm) of for all i ≤ 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 Kn;n. We prove that partitions of E(Kn;n) into three sets can be represented almost fairly. The methods of proofs are topological.

Original languageEnglish (US)
Title of host publicationA Journey through Discrete Mathematics
Subtitle of host publicationA Tribute to Jiri Matousek
PublisherSpringer International Publishing
Pages31-58
Number of pages28
ISBN (Electronic)9783319444796
ISBN (Print)9783319444789
DOIs
StatePublished - Jan 1 2017

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics
  • Economics, Econometrics and Finance(all)
  • General Business, Management and Accounting

Fingerprint

Dive into the research topics of 'Fair representation by independent sets'. Together they form a unique fingerprint.

Cite this