A long-standing question posed by Fukuda (1995) and Ziegler (2000) inquires about the asymptotic behavior of $g(n)$, the maximum number of facets that an $n$-dimensional $0/1$-polytope can have. A remarkable result by B\'ar\'any and P\'or (2001) via probabilistic methods established that $g(n)$ is at least superexponential in $n$. In this paper, we propose a drastic change of perspective, which leads us to show that for each $n\geq 10$ there exists a $0/1$-polytope having at least $(n-\lceil 2\log_2 (n)\rceil - 1)!$ facets. This provides a significant improvement over the currently known lower bounds for $g(n)$. Furthermore, when combined with known upper bounds, our construction establishes the asymptotic behavior of $\log g(n)$ up to an error of $O((\log n)^2)$. The methods employed throughout this paper are elementary and fully deterministic. The underlying ideas in our proof stem from the combinatorics of hypersimplices and permutohedra.
Let $g(n)$ denote the largest number of facets of a full-dimensional $0/1$-polytope in $\R^n$. We prove that there are absolute constants $c>0$ and $n_0$ such that $$ g(n)\ge (cn)^{n/2}\quad(n\ge n_0). $$ This removes the logarithmic factor from the lower bound $\bigl(cn/\log n\bigr)^{n/2}$ of Gatzouras, Giannopoulos,...
Let $D(N)$ denote the largest cardinality of a subset of $\{1,\ldots,N\}$ containing no nonzero square difference. While a construction certifying $D(N)\geq (1-o(1))N^{1/2}$ is almost trivial, Erd\H{o}s conjectured that this bound is sharp up to polylogarithmic factors. This was disproved by S\'ark\"ozy and later again...
Let $g_n$ be the largest number of Euclidean balls of diameter $1$ which may be needed to cover a set of diameter $1$ in $\mathbb{R}^n$. We study this problem for finite sets invariant under all coordinate permutations. We prove that the exponential growth rate in this symmetric problem can be characterized exactly as...
Andrii Arman, A. Bondarenko, A. Prymak et al.· 0 citations
We prove that the proportion of $0/1$-equivalence classes of $d$-dimensional $(0,1)$-polytopes that are normal tends to zero at least at a double exponential rate as $d\to\infty$. As a consequence, the same holds for any of the following classes given by the type of triangulation possible: (a) quadratic, (b) flag unimo...
For practical $N$ let $h(N)$ be the least $k$ such that every integer $1\le m\le N$ is a sum of at most $k$ distinct divisors of $N$. We prove $h(n!)\le(2\log2+o(1))\,n/\log n$. This improves the bounds of order $n/(\log n)^{1/2-\varepsilon}$ established in Tenenbaum-Yokota's Lemma 4 and Yokota's 1995 knapsack note. We...
We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the ou...
