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

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai Vereshchagin

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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 that all the resulting bipartite graphs 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 the right nodes. Stated differently, every finite 2-dimensional set S ⊂ N2 can be partitioned into poly (log | S |) parts so that in every part the ratio between the maximal size and the minimal size of non-empty horizontal section is bounded by a constant and the same condition holds for vertical sections. We prove a similar statement for n-dimensional sets for any n and show how it can be used to relate information inequalities for Shannon entropy of random variables to inequalities between sizes of sections and their projections of multi-dimensional finite sets.

Original languageEnglish (US)
Pages (from-to)134-144
Number of pages11
JournalEuropean Journal of Combinatorics
Volume28
Issue number1
DOIs
StatePublished - Jan 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Partitioning multi-dimensional sets in a small number of "uniform" parts'. Together they form a unique fingerprint.

Cite this