Equitability in certain count matroids
Speaker: Attila Bernáth
Date: April 1, 2022, 14:00-15:00
Place: Room 3.518
Given integers k and l with k>0, a graph G=(V,E) is called (k,l)-sparse if |E[X]|≤max{k⋅|X|-l,0} for any subset X of V. The graph is called (k,l)-tight if furthermore |E| = k⋅|V|-l. The (k,l)-tight subsets of edges of a given graph (if non-empty) form the family of bases of a matroid defined on the edge set; this is called a count matroid (or sparsity matroid) in the literature. We only consider the case when k and l are non-negative and l≤k. We prove the following: If A and B are two disjoint (k,l)-tight subsets of the edges of a given graph G=(V,E) and X⊆A∪B is an edge set of even size, then we can find disjoint (k,l)-tight subsets A’ and B’ such that A’∪B’ = A∪B and |A’∩X | = |B’∩X|.
