Back to Search Start Over

On the number of irreducible points in polyhedra

Authors :
Chirkov, A. Yu.
Zolotykh, N. Yu.
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

Subjects :
Mathematics - Combinatorics

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