Noga Alon, Ilan Newman, Alexander Shen, GĂˇbor Tardos, Nikolay Vereshchagin

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>