On the number of irreducible points in polyhedra

DOI10.1007/S00373-016-1683-1MaRDI QIDQ343724zbMATH OpenOpenAlexFDO

Authors A. Y. Chirkov, N. Yu. Zolotykh

Publication date 29 November 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.4289

zbMATH Keywords

integer latticeirreducible pointspolyhedronteaching dimensionteaching setthreshold functionvertex

Mathematics Subject Classification ID

Polyhedra and polytopes; regular figures, division of spaces (51M20) (n)-dimensional polytopes (52B11) Computational learning theory (68Q32)

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^{lfloorfracn2floor}lo{g}^{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(lo{g}^{n-2}k)$ for any fixed $nge2$.

Recommendations

• On teaching sets of k-threshold functions
• On the minimal teaching sets of two-dimensional threshold functions
• On an upper bound for the cardinality of a minimal teaching set of a threshold function
• On integer points in polyhedra
• Computing the integer points of a polyhedron. I: Algorithm

Cites work

• Estimating the complexity of deciphering a threshold functions in a k-valued logic
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3735554 (Why is no real title available?)
• scientific article; zbMATH DE number 942482 (Why is no real title available?)
• Lectures on Polytopes
• On an upper bound for the cardinality of a minimal teaching set of a threshold function
• On integer points in polyhedra
• On integer points in polyhedra: A lower bound
• On specifying Boolean functions by labelled examples
• On the complexity of deciphering the threshold functions of \(k\)-valued logic
• On the minimal teaching sets of two-dimensional threshold functions
• On the Size of Weights for Threshold Gates
• Queries and concept learning
• The maximum numbers of faces of a convex polytope
• The vertices of the knapsack polytope
• Upper and lower bound results on the convex hull of integer points in polyhedra

Cited in

(5)

• On irreducible mappings into polyhedra
• Learning Boolean halfspaces with small weights from membership queries
• On teaching sets of k-threshold functions
• On teaching sets for 2-threshold functions of two variables
• On the number of congruent simplices in a point

This page was built for publication: On the number of irreducible points in polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q343724)