On the number of irreducible points in polyhedra

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 with radius $k$ given by a system of $m$ linear inequalities is at most $O(m^{\lfloor \frac{n}{2}\rfloor }{\log }^{n-1}k)$ if $n$ is fixed. Using this result we prove the hypothesis asserting that the teaching dimension in the class of threshold functions of $k$-valued logic in $n$ variables is $\Theta ({\log }^{n-2}k)$ for any fixed $n\ge 2$.

24 pages, 4 figures

References in corpus (2)

• On the number of vertices in integer linear programming problems
• On the minimal teaching sets of two-dimensional threshold functions

Cited by in corpus (1)

• Specifying a positive threshold function via extremal points