On the Number of Irreducible Points in Polyhedra |
| |
Authors: | Aleksandr Yu Chirkov Nikolai Yu Zolotykh |
| |
Institution: | 1.National Research Lobachevsky State University of Nizhni Novgorod,Nizhny Novogorod,Russia;2.National Research University Higher School of Economics,Nizhni Novgorod,Russia |
| |
Abstract: | An integer point in a polyhedron is called irreducible iff it is not the midpoint of two other integer points in the polyhedron. We prove that the number of irreducible integer points in n-dimensional polytope P is at most \(O(m^{\lfloor \frac{n}{2}\rfloor }\log ^{n-1}\gamma )\), where n is fixed and P is given by a system of m linear inequalities with integer coefficients not exceeding (by absolute value) \(\gamma \). This bound is tight. Using this result we prove the conjecture asserting that the teaching dimension in the class of threshold functions of k-valued logic in n variables is \(\varTheta (\log ^{n-2} k)\) for any fixed \(n\ge 2\). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |