Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-095 | 26th August 2005 00:00

Partitioning multi-dimensional sets in a small number of ``uniform'' parts


Authors: Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin
Publication: 27th August 2005 16:50
Downloads: 3071


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 the left nodes is bounded by a constant and the same condition holds for right nodes. We prove a similar statement for n-dimensional sets and show how it can be used to relate inequalities for Shannon entropy of random variables to inequalities between sizes of sections and their projections of multi-dimensional finite sets.

ISSN 1433-8092 | Imprint