pith. sign in

arxiv: 1612.07652 · v3 · pith:76NPDN3Bnew · submitted 2016-12-22 · 🧮 math.CO

Fair representation in the intersection of two matroids

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

For a simplicial complex ${\mathcal C}$ denote by $\beta({\mathcal C})$ the minimal number of edges from ${\mathcal C}$ needed to cover the ground set. If ${\mathcal C}$ is a matroid then for every partition $A_1, \ldots, A_m$ of the ground set there exists a set $S \in {\mathcal C}$ meeting each $A_i$ in at least $\frac{|A_i|}{\beta({\mathcal C})}$ elements. We conjecture that a slightly weaker result is true for the intersections of two matroids: if ${\mathcal D}={\mathcal P} \cap {\mathcal Q}$, where ${\mathcal P},{\mathcal Q}$ are matroids on the same ground set $V$ and $\beta({\mathcal P}), \beta({\mathcal P}) \le k$, then for every partition $A_1, \ldots, A_m$ of the ground set there exists a set $S \in {\mathcal D}$ meeting each $A_i$ in at least $(\frac{1}{k}-\frac{1}{|V|})|A_i|-1$ elements. We prove this for a partition into two sets.

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.