Abstract We present a new algebraic-combinatorial approach to proving a Bézout-type inequality for zonoids in dimension three, which has recently been established by Fradelizi, Madiman, Meyer, and Zvavitch. Our approach hints at connections between inequalities for mixed volumes of zonoids and real algebra and matroid theory.

To confirm that the expressive power of ReLU neural networks grows with their depth, the function $F_n = \max (0,x_1,\ldots,x_n )$ has been considered in the literature. A conjecture by Hertrich, Basu, Di Summa, and Skutella [NeurIPS 2021] states that any ReLU network that exactly represents $F_n$ has at least $\lceil \log_2 (n+1) \rceil$ hidden layers. The conjecture has recently been confirmed for networks with integer weights by Haase, Hertrich, and Loho [ICLR 2023]. We follow up on this line of research and show that, within ReLU networks whose weights are decimal fractions, $F_n$ can only be represented by networks with at least $\lceil \log_3 (n+1) \rceil$ hidden layers. Moreover, if all weights are $N$-ary fractions, then $F_n$ can only be represented by networks with at least $\Omega( \frac{\ln n}{\ln \ln N})$ layers. These results are a partial confirmation of the above conjecture for rational ReLU networks, and provide the first non-constant lower bound on the depth of practically relevant ReLU networks.

Abstract We present an algorithm for the classification of triples of lattice polytopes with a given mixed volume m in dimension 3. It is known that the classification can be reduced to the enumeration of so-called irreducible triples, the number of which is finite for fixed m. Following this algorithm, we enumerate all irreducible triples of normalized mixed volume up to 4 that are inclusion-maximal. This produces a classification of generic trivariate sparse polynomial systems with up to 4 solutions in the complex torus, up to monomial changes of variables. By a recent result of Esterov, this leads to a description of all generic trivariate sparse polynomial systems that are solvable by radicals.

We study two combinatorial parameters, which we denote by $f(S)$ and $h(S)$, associated with an arbitrary set $S \subseteq \mathbb{R}^d$, where $d \in \mathbb{N}$. In the nondegenerate situation, $f(S)$ is the largest possible number of facets of a $d$-dimensional polyhedron $L$ such that the interior of $L$ is disjoint with $S$ and $L$ is inclusion-maximal with respect to this property. The parameter $h(S)$ is the Helly number of the family of all sets that can be given as the intersection of $S$ with a convex subset of $\mathbb{R}^d$. We obtain the inequality $f(S) \le h(S)$ for an arbitrary $S$, and the equality $f(S)=h(S)$ for every discrete $S$. Furthermore, motivated by research in integer and mixed-integer optimization, we show that $2^d$ is the sharp upper bound on $f(S)$ in the case $S = (\mathbb{Z}^d \times \mathbb{R}^n) \cap C$, where $n \ge 0$ and $C \subseteq \mathbb{R}^{d+n}$ is convex. The presented material generalizes and unifies results of various authors, including the result $h(\mathbb{Z}^d) = 2^d$ of Doignon, the related result $f(\mathbb{Z}^d)=2^d$ of Lovász, and the inequality $f(\mathbb{Z}^d \cap C) \le 2^d$, which has recently been proved for every convex set $C \subseteq \mathbb{R}^d$ by Morán and Dey.

Given an integral polyhedron $P\subseteq\mathbb{R}^n$ and a rational polyhedron $Q\subseteq\mathbb{R}^n$ containing the same integer points as $P$, we investigate how many iterations of the Chvátal--Gomory closure operator have to be performed on $Q$ to obtain a polyhedron contained in the affine hull of $P$. We show that if $P$ contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on $n$. On the other hand, we prove that if $P$ is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.

Let $\mathcal{T}^d$ be the set of all d-dimensional simplices T in $\mathbb{R}^d$ with integer vertices and a single integer point in the interior of T. It follows from a result of Hensley that $\mathcal{T}^d$ is finite up to affine transformations that preserve $\mathbb{Z}^d$. It is known that when d grows, the maximum volume of the simplices $T \in \mathcal{T}^d$ becomes extremely large. We improve and refine bounds on the size of $T \in \mathcal{T}^d$ (where by the size we mean the volume or the number of lattice points). It is shown that each $T \in \mathcal{T}^d$ can be decomposed into an ascending chain of faces $G_1 \subseteq \cdots \subseteq G_d=T$ such that for every $i \in \{1,\ldots,d\}$, $G_i$ is i-dimensional and the size of $G_i$ is bounded from above in terms of i and d. The bound on the size of $G_i$ is double exponential in i. The presented upper bounds are asymptotically tight on the log-log scale.