Random Gale diagrams and neighborly polytopes in high dimensions (Q2042129)

A convex polytope \(P\) in Euclidean space \(\mathbb{R}^d\) is \(k\)-neighborly if any \(k\) or fewer vertices of \(P\) are neighbors, i.e. if their convex hull is a face of \(P\). The author recalls a suggestion of David Gale from 1956 and generates sets of combinatorially isomorphic polytopes by choosing their Gale diagrams at random. Importantly, the paper provides a definition of a random Gale diagram. Inspired by a result of [\textit{D. L. Donoho} and \textit{J. Tanner}, Proc. Natl. Acad. Sci. USA 102, No. 27, 9452--9457 (2005; Zbl 1135.60300)], Theorem 1 shows that in high dimensions and under suitable assumptions on the growth of several parameters, the obtained random polytopes have strong neighborliness properties with high probability. Theorem 2 considers the expectation of the involved random variables and describes a phase transition with an explicit threshold.