Growing balanced covering sets (Q1981677): Difference between revisions

This paper starts with the following problem: Given a bipartite graph with bipartition \((A,B)\), where \(B\) is equipartitioned into \(k\) blocks, can the vertices in \(A\) be picked one by one so that at every step, the picked vertices cover roughly the same number of vertices in each of these blocks? Coming up, the author shows that there is an ordering \(v_1,\dots,v_n\) of the vertices in \(A\) such that for every \(j\in\{1,\dots,n\}\), the numbers of vertices with a neighbor in \(\{v_1,\dots,v_j\}\) in every two blocks differ by at most \(\sqrt{2(k-1)c}\dot m\) if each block has cardinality \(m\), the vertices in \(B\) have the same degree, and each vertex in \(A\) has at most \(cm\) neighbors in every block, where \(c>0\) is a small constant. This is related to a well-known lemma of Steinitz, and partially answers an unpublished question of Scott and Seymour. Furthermore, the results of this paper are of interest to the people working in related areas.