Τυχαία πολύτοπα

Abstract

The main result of the Thesis is a lower bound for the maximal possible number of facets of a 0/1 polytope in Rn. By definition, a 0/1 polytope is the convex hull of a subset of the vertices of [0, 1]n.In general, if P is a polytope in Rn, we write fn−1(P) for the number of its facets. Let g(n) := max ©fn−1(Pn) : Pn a 0/1 polytope in Rn ª. Fukuda and Ziegler asked what the behaviour of g(n) is as n → ∞. The best known upper bound to date is g(n) ≤ 30(n − 2)! (for n large enough), which is established by Fleiner, Kaibel and Rote. Regarding lower bounds, a major breakthrough was made by B´ar´any and P´or who proved that g(n) ≥ ³cn log n´n/4, where c > 0 is an absolute constant. We show that the exponent n/4 can in fact be improved to n/2: There exists a constant c > 0 such that g(n) ≥ µ cn log n¶n/2. The existence of 0/1 polytopes with many facets is established by a refinement of the probabilistic method developed by B´ar´any and P´or. We work with ±1 polytopes (i.e., polytopes whose vertices are sequences of signs). Let X1, . . . , Xn be independent and identically distributed ±1 random variables, defined on some probability space (Ω, F, P), with distribution P(X = 1) = P(X = −1) = 1 2. Set X~ = (X1, . . . , Xn) and, for a fixed N satisfying n < N ≤ 2 n, consider N independent copies X~1, . . . , X~ N of X~ . This procedure defines the random0/1 polytope KN = conv{X~1, . . . , X~ N }. Under some restrictions on the range of values of N, we obtain a lower bound for the expected number of facets E[fn−1(KN )], for each fixed N:There exist two positive constants a and b such that: for all sufficiently large n, and all N satisfying na ≤ N ≤ exp(bn), one has that E[fn−1(KN )] ≥ µ log Na log n¶n/2. For the lower bound for g(n) one only has to choose N = bexp(bn/ log n)c. The second part of the Thesis is related to the strong form of Sylvester’s classical problem about random points uniformly distributed in plane convexregions. We prove the following two facts: (1) If K is a plane convex body with area |K| = 1 and if AK denotes the distribution function of the area of a random triangle in K, then AK(α) ≥ A∆(α) for all α > 0, where ∆ is a triangle. If AK = A∆ then K is a triangle. (2) If K is a symmetric plane convex body with area |K| = 1 and if BK denotes the distribution function of the area of a random symmetric parallelogram in K, then BK(α) ≥ BP (α) for all α > 0, where P is a parallelogram. If BK = BP then K is a parallelogram.