Back to Search
Start Over
On the number of irreducible points in polyhedra
- Source :
- Graphs and Combinatorics. 2016. V. 32, N. 5. P. 1789-1803
- Publication Year :
- 2013
-
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$.<br />Comment: 24 pages, 4 figures
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- Graphs and Combinatorics. 2016. V. 32, N. 5. P. 1789-1803
- Publication Type :
- Report
- Accession number :
- edsarx.1306.4289
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s00373-016-1683-1