{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Face Numbers of Random Polytopes\n",
"\n",
"In order to test the perfromance of their algorithms in polyhedral geometry people often employ random constructions. While this is a good idea, combinatorially such polytopes are very restricted.\n",
"\n",
"This will be demonstrated in this notebook by looking at random 6-polytopes.\n",
"\n",
"Relevant publications on the subject include:\n",
"\n",
"* Buchta, Müller & Tichy: Stochastical approximation of convex bodies, Math. Ann. 271 (1985)\n",
"* Borgwardt: The simplex method. A probabilistic analysis, Springer (1987).\n",
"\n",
"Author: [Michael Joswig](https://page.math.tu-berlin.de/~joswig/)\n",
"\n",
"On the software side this showcases the use of [polymake](https://polymake.org) from within [Oscar](http://oscar-system.org) (via [Polymake.jl](https://github.com/oscar-system/Polymake.jl))."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" ----- ----- ----- - ----- \n",
"| | | | | | | | | | \n",
"| | | | | | | | \n",
"| | ----- | | | |----- \n",
"| | | | |-----| | | \n",
"| | | | | | | | | | \n",
" ----- ----- ----- - - - - \n",
"\n",
"...combining (and extending) ANTIC, GAP, Polymake and Singular\n",
"Version\u001b[32m 0.6.0 \u001b[39m... \n",
" ... which comes with absolutely no warranty whatsoever\n",
"Type: '?Oscar' for more information\n",
"(c) 2019-2021 by The Oscar Development Team\n"
]
},
{
"data": {
"text/plain": [
"Polymake"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"using Oscar\n",
"const pm = Polymake"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Produce a 6-dimensional polytope with 20 vertices, drawn uniformly at random on the unit sphere, and print its f-vector."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"pm::Vector\n",
"20 167 641 1188 1041 347"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P = pm.polytope.rand_sphere(6,20)\n",
"P.F_VECTOR"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now for the g-vector of the same polytope, but this time it is converted to a Julia Array."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4-element Vector{Int32}:\n",
" 1\n",
" 13\n",
" 68\n",
" 71"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = convert(Array{Int32},P.G_VECTOR)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's do a census of 100 random samples and plot the result. Since g_0=1 and g_1=#vertices-dimension-1 are constant, it suffices to plot g_2 versus g_3."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"n_vertices=30\n",
"n_samples=100\n",
"g_vectors = Array{Int32}(undef,n_samples,2)\n",
"\n",
"for i=1:n_samples\n",
" RS = pm.polytope.rand_sphere(6,n_vertices)\n",
" g = RS.G_VECTOR\n",
" g_vectors[i,1] = g[3] # notice index shift as Julia counts from 1\n",
" g_vectors[i,2] = g[4]\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We use the Plots package for visual output."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"using Plots\n",
"scatter(g_vectors[:,1], g_vectors[:,2], xlabel=\"g_2\", ylabel=\"g_3\", legend=false)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Compare the empirically found g_3 values (as a function of g_2) with the true range from Stanley's g-theorem."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"30-element Vector{Int64}:\n",
" 1005\n",
" 1014\n",
" 1024\n",
" 1035\n",
" 1047\n",
" 1060\n",
" 1074\n",
" 1089\n",
" 1105\n",
" 1122\n",
" 1140\n",
" 1141\n",
" 1143\n",
" ⋮\n",
" 1176\n",
" 1185\n",
" 1195\n",
" 1206\n",
" 1218\n",
" 1231\n",
" 1245\n",
" 1260\n",
" 1276\n",
" 1293\n",
" 1311\n",
" 1330"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"min_g2 = minimum(g_vectors[:,1])\n",
"max_g2 = maximum(g_vectors[:,1])\n",
"ub = [ Int(pm.polytope.pseudopower(g2,2)) for g2 in min_g2:max_g2 ]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Or even compare with the maximal g-vector from McMullen's upper bound theorem shows that the random polytopes have rather few faces."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"pm::Vector\n",
"1 23 276 2300"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pm.polytope.upper_bound_theorem(6,n_vertices).G_VECTOR"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The lesson to learn here is the following.\n",
"\n",
"By just looking at this class of random polytopes, one cannot get an adequate intuition about the set of all 6-polytopes with 20 vertices, not even the simplicial ones."
]
}
],
"metadata": {
"@webio": {
"lastCommId": "a4609bbcc9d14b458feee9a56e4351e1",
"lastKernelId": "76441be8-f811-48aa-869d-758fe6dddb8b"
},
"kernelspec": {
"display_name": "Julia 1.6.2",
"language": "julia",
"name": "julia-1.6"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.6.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}