A bound for the number of vertices of a polytope with applications (Q2250836)

The author shows that the number of vertices of a particular kind of convex \(n\)-polytope in \(\mathbb{R}^n\) is exponentially large in \(n\). Two applications of this result are discussed. First, every centrally symmetric convex \(n\)-polytope in \(\mathbb{R}^n\) with \(O(n)\) facets has \(2^{\Omega(n)}\) vertices. Second, the number of \(r\)-factors in a \(k\)-regular graph with \(v\) vertices is exponentially large in \(v\), provided \(k\geq 2r+1\) and there are no cuts of small size.