ECCC-Report TR05-095https://eccc.weizmann.ac.il/report/2005/095Comments and Revisions published for TR05-095en-usSat, 27 Aug 2005 16:50:06 +0300
Paper TR05-095
| Partitioning multi-dimensional sets in a small number of ``uniform'' parts |
Noga Alon,
Ilan Newman,
Alexander Shen,
GĂˇbor Tardos,
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2005/095Our 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.
Sat, 27 Aug 2005 16:50:06 +0300https://eccc.weizmann.ac.il/report/2005/095