2011/09/28 by Gennadiy Averkov, Averkov, Gennadiy
Computer Science · Mathematics · #52A01 #52C07 #90C10 #90C11 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #Optimization and Control (math.OC) #Point processes and geometric inequalities #math.CO #math.MG #math.OC #msc:52A01 #msc:52C07 #msc:90C10 #msc:90C11
paper · pdf · doi:10.48550/arxiv.1109.6179
openalex publication_date 2011/09/28 · arxiv created 2013/07/05 · arxiv updated 2013/07/08 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We study two combinatorial parameters, which we denote by f(S) and h(S), associated to an arbitrary set S ⊆ Rd, where d ∈ N. In the nondegenerate situation, f(S) is the largest possible number of facets of a d-dimensional polyhedron L such that the interior of L is disjoint with S and L is inclusion-maximal with respect to this property. The parameter h(S) is the Helly number of the family of all sets that can be given as the intersection of S with a convex subset of Rd. We obtain the inequality f(S) ≤ h(S) for an arbitrary S and the equality f(S)=h(S) for every discrete S. Furthermore, motivated by research in integer and mixed-integer optimization, we show that 2d is the sharp upper bound on f(S) in the case S = (Zd × Rn) ∩ C, where n ≥ 0 and C ⊆ Rd+n is convex. The presented material generalizes and unifies results of various authors, including the result h(Zd) = 2d of Doignon, the related result f(Zd)=2d of Lovász and the inequality f(Zd ∩ C) ≤ 2d, which has recently been proved for every convex set C ⊆ Rd by Dey & Morán.