Back to search

University of Crete (UOC)

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

Abstract

dc:description

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.

Degree

thesis:*
Grantor dc:publisher
University of Crete (UOC)
Year dc:date
2006

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Markoulakis, Nikolaos
  • Μαρκουλάκης, Νικόλαος

Subjects

dc:subject × 10

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/31919

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Markoulakis, Nikolaos; Μαρκουλάκης, Νικόλαος. Τυχαία πολύτοπα. University of Crete (UOC), 2006. http://hdl.handle.net/10442/hedi/31919