Двойственность Гейла и смежностность случайных многогранников. II


https://doi.org/10.18255/1818-1015-2012-4-87-109

Полный текст:


Аннотация

Получены не зависящие от распределения результаты о k-смежностности случайных многогранников. Они подтверждают известную гипотезу Гейла в общем случае.


Об авторе

Алексей Германович Бродский
ООО «Яндекс»
Россия
руководитель службы разработки


Список литературы

1. Богачев В.И. Основы теории меры. Т. 1, 2. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003.

2. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995.

3. Бондаренко В.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогранниках // Дискретная математика. 2008. Т. 20, №1. C. 64–69.

4. Бродский А.Г. O 2-смежностных многогранниках и конструкции Гейла // Моделирование и анализ информационных систем. 2009. Т. 16, №2. С. 5–21.

5. Бродский А.Г. О двойственности Гейла и k-смежностных случайных многогранниках // Заметки по информатике и математике: сб. науч. ст. Вып. 2 / отв. ред. А.Н. Морозов; Яросл. гос. ун-т им. П.Г. Демидова. Ярославль: ЯрГУ, 2010. С. 28-33.

6. Бродский А.Г. Двойственность Гейла и смежностность случайных многогранников. I // Моделирование и анализ информационных систем. 2012. Т. 19. №2. С. 62–86.

7. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998.

8. Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии. М.: Наука, 1966.

9. Adamczak R., Litvak A.E., Pajor A., Tomczak-Jaegermann N. Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. Preprint, 34 p., available at arXiv:0904.4723v1 [math.PR] 30 Apr 2009.

10. B´ar´any I. Random points and lattice points in convex bodies // Bulletin of the American Mathematical Society. 2008. V. 45, №3. P. 339–365.

11. B´ar´any I., F¨uredi Z. On the shape of the convex hull of random points // Probability Theory and Related Fields. 1988. V. 77, №2. P. 231–240.

12. Buchta C. On a conjecture of R.E. Miles about the convex hull of random points // Monatshefte f¨ur Mathematik. 1986. V. 102. P. 91–102.

13. Candes E., Rudelson M., Tao T., Vershynin R. Error correction via linear programming // Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), IEEE. 2005. P. 295–308.

14. Candes E., Tao T. Near optimal signal recovery from random projections and universal encoding strategies // IEEE Transactions on Information Theory. 2004. V. 52. P. 5406–5425.

15. Candes E., Tao T. Decoding by linear programming // IEEE Transactions on Information Theory. 2005. V. 51, №12. P. 4203–4215.

16. Donoho D.L. Neighborly polytopes and sparse solution of underdetermined linear equations. Preprint, 21 p., available at http://www-stat.stanford.edu/~donoho/Reports/2005/NPaSSULE-01-28-05.pdf.

17. Donoho D.L. High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension // Discrete and Computational Geometry. 2006. V. 35, №4. P. 617–652.

18. Donoho D.L., Tanner J. Sparse nonnegative solution of underdetermined linear equations by linear programming // Proceedings of the National Academy of Sciences of the USA. 2005. V. 102, №27. P. 9446–9451.

19. Donoho D.L., Tanner J. Neighborliness of randomly-projected simplices in high dimensions // Proceedings of the National Academy of Sciences of the USA. 2005. V. 102, №27. P. 9452–9457.

20. Donoho D.L., Tanner J. Counting faces of randomly-projected polytopes when the projection radically lowers dimension // Journal of the American Mathematical Society. 2009. V. 22, №1. P. 1–53.

21. Donoho D.L., Tanner J. Observed universality of phase transitions in highdimensional geometry, with implications for modern data analysis and signal processing // Philosophical Transactions of the Royal Society. Ser. A. 2009. V. 367. P. 4273–4293.

22. Donoho D.L., Tanner J. Counting the faces of randomly-projected hypercubes and orthants, with applications // Discrete and Computational Geometry. 2010. V. 43, №3. P. 522–541.

23. Donoho D.L., Tanner˙J. Exponential bounds implying construction of compressed sensing matrices, error-correcting codes and neighborly polytopes by random sampling // IEEE Transactions on Information Theory. 2010. V. 56, №4. P. 2002–2016

24. Gale D. Neighboring vertices on a convex polyhedron // Linear inequalities and related systems / H.W. Kuhn, A.W. Tucker, Eds. (Annals of Mathematics Studies. №38). Princeton, New Jersey: Princeton University Press, 1956. P. 255–263.Имеется русский перевод: Гейл Д. Соседние вершины на выпуклом многограннике // Линейные неравенства и смежные вопросы / Под ред. Г.У. Куна и А.У. Таккера. М.: ИЛ, 1959. С. 355–362.

25. Gillmann R. 0/1-polytopes: typical and extremal properties. Dissertation. Berlin: Technische Universit¨at Berlin, 2007. 125 p.

26. Gr¨unbaum B. Convex polytopes (Graduate Texts in Mathematics. V. 221). Second edition prepared by V. Kaibel, V. Klee and G.M. Ziegler. New York: Springer, 2003.

27. Mendelson S., Pajor A., Tomczak-Jaegermann N. Reconstruction and subgaussian operators in asymptotic geometric analysis // Geometric and Functional Analysis. 2007. V. 17, №4. P. 1248–1282.

28. Reitzner M. Random polytopes // New perspectives in stochastic geometry / W.S. Kendall, I. Molchanov, Eds. Oxford: Oxford University Press, 2010. P. 45–76.

29. Rudelson M., Vershynin R. Geometric approach to error correcting codes and reconstruction of signals // International Mathematical Research Notices. 2005. V. 64. P. 4019–4041.

30. Schneider R. Discrete aspects of stochastic geometry // Handbook of discrete and computational geometry / J.E. Goodman, J. O’Rourke, Eds. (second edition). Boca Raton (Florida): Chapman & Hall / CRC Press, 2004. P. 255–278.

31. Schneider R. Recent results on random polytopes // Bollettino dell’Unione Matematica Italiana. Sez. B. 2008. V. 1. P. 17–39.

32. Schneider R., WeilW. Stochastic and integral geometry (Probability and its Applications). Berlin-Heidelberg: Springer, 2008.

33. Vershik A.M., Sporyshev P.V. Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem // Selecta Mathematica Sovietica. 1992. V. 11, №2. P. 181–201.

34. Wendel J.G. A problem in geometric probability // Mathematica Scandinavica. 1962. V. 11. P. 109–111.


Дополнительные файлы

Для цитирования: Бродский А.Г. Двойственность Гейла и смежностность случайных многогранников. II. Моделирование и анализ информационных систем. 2012;19(4):87-109. https://doi.org/10.18255/1818-1015-2012-4-87-109

For citation: Brodskiy A.G. Gale Duality and the Neighborliness of Random Polytopes. II. Modeling and Analysis of Information Systems. 2012;19(4):87-109. (In Russ.) https://doi.org/10.18255/1818-1015-2012-4-87-109

Просмотров: 152

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)