Fair representation in the intersection of two matroids (Q2409842)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fair representation in the intersection of two matroids |
scientific article |
Statements
Fair representation in the intersection of two matroids (English)
0 references
16 October 2017
0 references
Summary: Mysteriously, hypergraphs that are the intersection of two matroids behave in some respects almost as well as one matroid. In the present paper we study one such phenomenon -- the surprising ability of the intersection of two matroids to fairly represent the parts of a given partition of the ground set. 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 \(\lfloor \frac{|A_i|}{\beta(\mathcal{C})}\rfloor\) elements. We conjecture that a slightly weaker result is true for the intersection 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{Q}) \leq 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}|A_i|-1\) elements. We prove that if \(m=2\) (meaning that the partition is into two sets) there is a set belonging to \(\mathcal{D}\) meeting each \(A_i\) in at least \((\frac{1}{k}-\frac{1}{|V|})|A_i|-1\) elements.
0 references
dimatroid
0 references
fair representation
0 references
0 references