Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A Journey Through Discrete MathematicsFair Representation by Independent Sets

A Journey Through Discrete Mathematics: Fair Representation by Independent Sets [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 V (H) if |S∩Vi|≥|Vi|β(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\vert S \cap V _{i}\vert \geqslant \left \lfloor \frac{\vert V _{i}\vert } {\beta (H)} \right \rfloor$$ \end{document} (resp. |S∩Vi|≥|Vi|β(H)−1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\vert S \cap V _{i}\vert \geqslant \left \lfloor \frac{\vert V _{i}\vert } {\beta (H)} \right \rfloor - 1$$ \end{document}) for all i≤m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i\leqslant m$$ \end{document}. 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.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

A Journey Through Discrete MathematicsFair Representation by Independent Sets

Editors: Loebl, Martin; Nešetřil, Jaroslav; Thomas, Robin
Aharoni, Ron; Alon, Noga; Berger, Eli; Chudnovsky, Maria; Kotlar, Dani; Loebl, Martin; Ziv, Ran
Springer Journals — Oct 6, 2017
Download PDF
27 pages

Loading next page...
 
/lp/springer-journals/a-journey-through-discrete-mathematics-fair-representation-by-5JmCVJ8hrY
Publisher
Springer International Publishing
Copyright
© Springer International publishing AG 2017
ISBN
978-3-319-44478-9
Pages
31 –58
DOI
10.1007/978-3-319-44479-6_2
Publisher site
See Chapter on Publisher Site

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 V (H) if |S∩Vi|≥|Vi|β(H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\vert S \cap V _{i}\vert \geqslant \left \lfloor \frac{\vert V _{i}\vert } {\beta (H)} \right \rfloor$$ \end{document} (resp. |S∩Vi|≥|Vi|β(H)−1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\vert S \cap V _{i}\vert \geqslant \left \lfloor \frac{\vert V _{i}\vert } {\beta (H)} \right \rfloor - 1$$ \end{document}) for all i≤m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$i\leqslant m$$ \end{document}. 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.]

Published: Oct 6, 2017

Keywords: Fair Representation; Hypergraph; Matching Complexity; Borsuk-Ulam Theorem; Matroid Intersection Theorem

There are no references for this article.