On the graph-density of random 0/1-polytopes
| dc.creator | Kaibel, Volker | |
| dc.creator | Remshagen, Anja | |
| dc.date | 2003-06-17 | |
| dc.date.accessioned | 2026-07-07T04:58:59Z | |
| dc.date.available | 2026-07-07T04:58:59Z | |
| dc.description | Let X_{d,n} be an n-element subset of {0,1}^d chosen uniformly at random, and denote by P_{d,n} := conv X_{d,n} its convex hull. Let D_{d,n} be the density of the graph of P_{d,n} (i.e., the number of one-dimensional faces of P_{d,n} divided by n(n-1)/2). Our main result is that, for any function n(d), the expected value of D_{d,n(d)} converges (with d tending to infinity) to one if, for some arbitrary e > 0, n(d) <= (\sqrt{2}-e)^d holds for all large d, while it converges to zero if n(d) >= (\sqrt{2}+e)^d holds for all large d. | |
| dc.description | 11 pages, to appear in: Proceedings of RANDOM03 (Princeton Univ., Aug 24 - Aug 26, 2003) | |
| dc.identifier | https://arxiv.org/abs/math/0306246 | |
| dc.identifier | http://arxiv.org/abs/math/0306246 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67805 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.subject | Probability | |
| dc.subject | 52B12; 52B05; 90C57; 60C05 | |
| dc.title | On the graph-density of random 0/1-polytopes | |
| dc.type | text |