Geodesic
Gale Duality and the Neighborliness of Random Polytopes. II
Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 4, pp. 87-109.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: $k$-neighborly polytope, probability space, random points, random polytope, distribution-independent property. 
@article{MAIS_2012_19_4_a8,
     author = {A. G. Brodskiy},
     title = {Gale {Duality} and the {Neighborliness} of {Random} {Polytopes.} {II}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {87--109},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a8/}
}
TY  - JOUR
AU  - A. G. Brodskiy
TI  - Gale Duality and the Neighborliness of Random Polytopes. II
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2012
SP  - 87
EP  - 109
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a8/
LA  - ru
ID  - MAIS_2012_19_4_a8
ER  - 
%0 Journal Article
%A A. G. Brodskiy
%T Gale Duality and the Neighborliness of Random Polytopes. II
%J Modelirovanie i analiz informacionnyh sistem
%D 2012
%P 87-109
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a8/
%G ru
%F MAIS_2012_19_4_a8
A. G. Brodskiy. Gale Duality and the Neighborliness of Random Polytopes. II. Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 4, pp. 87-109. http://geodesic.mathdoc.fr/item/MAIS_2012_19_4_a8/

[1] V. I. Bogachev, Osnovy teorii mery, v. 1, 2, NITs «Regulyarnaya i khaoticheskaya dinamika», Moskva–Izhevsk, 2003

[2] V. A. Bondarenko, Poliedralnye grafy i slozhnost v kombinatornoi optimizatsii, YarGU, Yaroslavl, 1995

[3] V. A. Bondarenko, A. G. Brodskii, “O sluchainykh 2-smezhnostnykh 0/1-mnogogrannikakh”, Diskretnaya matematika, 20:1 (2008), 64–69 | DOI | MR | Zbl

[4] A. G. Brodskii, “O 2-smezhnostnykh mnogogrannikakh i konstruktsii Geila”, Modelirovanie i analiz informatsionnykh sistem, 16:2 (2009), 5–21 | MR

[5] A. G. Brodskii, “O dvoistvennosti Geila i $k$-smezhnostnykh sluchainykh mnogogrannikakh”, Sb. nauch. st., Zametki po informatike i matematike, 2, ed. A. N. Morozov, YarGU, Yaroslavl, 2010, 28–33

[6] A. G. Brodskii, “Dvoistvennost Geila i smezhnostnost sluchainykh mnogogrannikov, I”, Modelirovanie i analiz informatsionnykh sistem, 19:2 (2012), 62–86

[7] R. Grekhem, D. Knut, O. Patashnik, Konkretnaya matematika. Osnovanie informatiki, Mir, M., 1998

[8] G. Khadviger, Lektsii ob ob'eme, ploschadi poverkhnosti i izoperimetrii, Nauka, M., 1966

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

[10] I. Bárány, “Random points and lattice points in convex bodies”, Bulletin of the American Mathematical Society, 45:3 (2008), 339–365 | DOI | MR | Zbl

[11] I. Bárány, Z. Füredi, “On the shape of the convex hull of random points”, Probability Theory and Related Fields, 77:2 (1988), 231–240 | DOI | MR

[12] C. Buchta, “On a conjecture of R.E. Miles about the convex hull of random points”, Monatshefte für Mathematik, 102 (1986), 91–102 | DOI | MR | Zbl

[13] E. Candes, M. Rudelson, T. Tao, R. Vershynin, “Error correction via linear programming”, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS'2005, IEEE, 2005, 295–308

[14] E. Candes, T. Tao, “Near optimal signal recovery from random projections and universal encoding strategies”, IEEE Transactions on Information Theory, 52 (2004), 5406–5425 | DOI | MR

[15] E. Candes, T. Tao, “Decoding by linear programming”, IEEE Transactions on Information Theory, 51:12 (2005), 4203–4215 | DOI | MR

[16] D. L. Donoho, Neighborly polytopes and sparse solution of underdetermined linear equations, 21 pp.

[17] D. L. Donoho, “High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension”, Discrete and Computational Geometry, 35:4 (2006), 617–652 | DOI | MR | Zbl

[18] D. L. Donoho, J. Tanner, “Sparse nonnegative solution of underdetermined linear equations by linear programming”, Proceedings of the National Academy of Sciences of the USA, 102:27 (2005), 9446–9451 | DOI | MR

[19] D. L. Donoho, J. Tanner, “Neighborliness of randomly-projected simplices in high dimensions”, Proceedings of the National Academy of Sciences of the USA, 102:27 (2005), 9452–9457 | DOI | MR | Zbl

[20] D. L. Donoho, J. Tanner, “Counting faces of randomly-projected polytopes when the projection radically lowers dimension”, Journal of the American Mathematical Society, 22:1 (2009), 1–53 | DOI | MR | Zbl

[21] D. L. Donoho, J. Tanner, “Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing”, Philosophical Transactions of the Royal Society. Ser. A, 367 (2009), 4273–4293 | DOI | MR | Zbl

[22] D. L. Donoho, J. Tanner, “Counting the faces of randomly-projected hypercubes and orthants, with applications”, Discrete and Computational Geometry, 43:3 (2010), 522–541 | DOI | MR | Zbl

[23] D. L. Donoho, J. Tanner, “Exponential bounds implying construction of compressed sensing matrices, error-correcting codes and neighborly polytopes by random sampling”, IEEE Transactions on Information Theory, 56:4 (2010), 2002–2016 | DOI | MR

[24] D. Gale, “Neighboring vertices on a convex polyhedron”, Linear inequalities and related systems, Annals of Mathematics Studies, 38, eds. H. W. Kuhn, A. W. Tucker, Princeton University Press, Princeton, New Jersey, 1956, 255–263 ; D. Geil, “Sosednie vershiny na vypuklom mnogogrannike”, Lineinye neravenstva i smezhnye voprosy, eds. G. U. Kun, A. U. Takker, IL, M., 1959, 355–362 | MR

[25] R. Gillmann, 0/1-polytopes: typical and extremal properties, Dissertation, Technische Universität Berlin, Berlin, 2007, 125 pp.

[26] B. Grünbaum, Convex polytopes, Graduate Texts in Mathematics, 221, Second edition, eds. V. Kaibel, V. Klee, G. M. Ziegler, Springer, New York, 2003 | DOI | MR

[27] S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, “Reconstruction and subgaussian operators in asymptotic geometric analysis”, Geometric and Functional Analysis, 17:4 (2007), 1248–1282 | DOI | MR | Zbl

[28] M. Reitzner, “Random polytopes”, New perspectives in stochastic geometry, eds. W. S. Kendall, I. Molchanov, Oxford University Press, Oxford, 2010, 45–76 | MR | Zbl

[29] M. Rudelson, R. Vershynin, “Geometric approach to error correcting codes and reconstruction of signals”, International Mathematical Research Notices, 64 (2005), 4019–4041 | DOI | MR | Zbl

[30] R. Schneider, “Discrete aspects of stochastic geometry”, Handbook of discrete and computational geometry, second edition, eds. J. E. Goodman, J. O'Rourke, Chapman Hall/CRC Press, Boca Raton, Florida, 2004, 255–278 | MR

[31] R. Schneider, “Recent results on random polytopes”, Bollettino dell'Unione Matematica Italiana. Sez. B, 1 (2008), 17–39 | MR | Zbl

[32] R. Schneider, W. Weil, Stochastic and integral geometry, Probability and its Applications, Springer, Berlin-Heidelberg, 2008 | DOI | MR

[33] A. M. Vershik, P. V. Sporyshev, “Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem”, Selecta Mathematica Sovietica, 11:2 (1992), 181–201 | MR | Zbl

[34] J. G. Wendel, “A problem in geometric probability”, Mathematica Scandinavica, 11 (1962), 109–111 | MR | Zbl