|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Partitioning multi-dimensional sets in a small number of "uniform" partsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 18 июля 2013 г.
- Авторы: Alon Noga, Newman Ilan, Shen Alexander, Tardos Gabor, Vereshchagin Nikolai
- Журнал: European Journal of Combinatorics
- Том: 28
- Год издания: 2007
- Издательство: Academic Press
- Местоположение издательства: United States
- Первая страница: 134
- Последняя страница: 144
- DOI: 10.1016/j.ejc.2005.08.002
- Аннотация: Our main result implies the following easily formulated statement. The set of edges EE of every finite bipartite graph can be split into poly(log|E|)(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⊂N2S⊂N2 can be partitioned into View the MathML sourcepoly(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 nn-dimensional sets for any nn 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.
- Добавил в систему: Верещагин Николай Константинович