maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-4-87-109mais-45Research ArticleОригинальные статьиArticlesДвойственность Гейла и смежностность случайных многогранников. IIGale Duality and the Neighborliness of Random Polytopes. IIБродскийАлексей ГермановичBrodskiyA. G.

руководитель службы разработки

руководитель службы разработки

abrodskiy@yandex-team.ruООО «Яндекс»РоссияООО «Яндекс»Russian Federation20122802201519487109Copyright © Бродский А.Г., 20152015Бродский А.Г.Brodskiy A.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/45

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

We have obtain of some distribution-independent results on the k-neighborliness of random polytopes. They confirm the well-known Gale conjecture for the general case.

k-смежностный многогранниквероятностное пространствослучайные точкислучайный многогранникне зависящее от распределения свойствоk-neighborly polytopeprobability spacerandom pointsrandom polytopedistribution-independent propertyReferencesБогачев В.И. Основы теории меры. Т. 1, 2. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003.Богачев В.И. Основы теории меры. Т. 1, 2. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003.Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995.Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995.Бондаренко В.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогранниках // Дискретная математика. 2008. Т. 20, №1. C. 64–69.Бондаренко В.А., Бродский А.Г. О случайных 2-смежностных 0/1-многогранниках // Дискретная математика. 2008. Т. 20, №1. C. 64–69.Бродский А.Г. O 2-смежностных многогранниках и конструкции Гейла // Моделирование и анализ информационных систем. 2009. Т. 16, №2. С. 5–21.Бродский А.Г. O 2-смежностных многогранниках и конструкции Гейла // Моделирование и анализ информационных систем. 2009. Т. 16, №2. С. 5–21.Бродский А.Г. О двойственности Гейла и k-смежностных случайных многогранниках // Заметки по информатике и математике: сб. науч. ст. Вып. 2 / отв. ред. А.Н. Морозов; Яросл. гос. ун-т им. П.Г. Демидова. Ярославль: ЯрГУ, 2010. С. 28-33.Бродский А.Г. О двойственности Гейла и k-смежностных случайных многогранниках // Заметки по информатике и математике: сб. науч. ст. Вып. 2 / отв. ред. А.Н. Морозов; Яросл. гос. ун-т им. П.Г. Демидова. Ярославль: ЯрГУ, 2010. С. 28-33.Бродский А.Г. Двойственность Гейла и смежностность случайных многогранников. I // Моделирование и анализ информационных систем. 2012. Т. 19. №2. С. 62–86.Бродский А.Г. Двойственность Гейла и смежностность случайных многогранников. I // Моделирование и анализ информационных систем. 2012. Т. 19. №2. С. 62–86.Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998.Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998.Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии. М.: Наука, 1966.Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии. М.: Наука, 1966.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.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.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.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.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.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.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.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.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.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.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.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.Candes E., Tao T. Decoding by linear programming // IEEE Transactions on Information Theory. 2005. V. 51, №12. P. 4203–4215.Candes E., Tao T. Decoding by linear programming // IEEE Transactions on Information Theory. 2005. V. 51, №12. P. 4203–4215.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.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.Donoho D.L. High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension // Discrete and Computational Geometry. 2006. V. 35, №4. P. 617–652.Donoho D.L. High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension // Discrete and Computational Geometry. 2006. V. 35, №4. P. 617–652.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.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.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.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.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.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.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.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.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.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.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–2016Donoho 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–2016Gale 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.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.Gillmann R. 0/1-polytopes: typical and extremal properties. Dissertation. Berlin: Technische Universit¨at Berlin, 2007. 125 p.Gillmann R. 0/1-polytopes: typical and extremal properties. Dissertation. Berlin: Technische Universit¨at Berlin, 2007. 125 p.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.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.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.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.Reitzner M. Random polytopes // New perspectives in stochastic geometry / W.S. Kendall, I. Molchanov, Eds. Oxford: Oxford University Press, 2010. P. 45–76.Reitzner M. Random polytopes // New perspectives in stochastic geometry / W.S. Kendall, I. Molchanov, Eds. Oxford: Oxford University Press, 2010. P. 45–76.Rudelson M., Vershynin R. Geometric approach to error correcting codes and reconstruction of signals // International Mathematical Research Notices. 2005. V. 64. P. 4019–4041.Rudelson M., Vershynin R. Geometric approach to error correcting codes and reconstruction of signals // International Mathematical Research Notices. 2005. V. 64. P. 4019–4041.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.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.Schneider R. Recent results on random polytopes // Bollettino dell’Unione Matematica Italiana. Sez. B. 2008. V. 1. P. 17–39.Schneider R. Recent results on random polytopes // Bollettino dell’Unione Matematica Italiana. Sez. B. 2008. V. 1. P. 17–39.Schneider R., WeilW. Stochastic and integral geometry (Probability and its Applications). Berlin-Heidelberg: Springer, 2008.Schneider R., WeilW. Stochastic and integral geometry (Probability and its Applications). Berlin-Heidelberg: Springer, 2008.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.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.Wendel J.G. A problem in geometric probability // Mathematica Scandinavica. 1962. V. 11. P. 109–111.Wendel J.G. A problem in geometric probability // Mathematica Scandinavica. 1962. V. 11. P. 109–111.

The authors declare that there are no conflicts of interest present.