Vertex Decompositions in Hypercube Graphs, and Dehn–Sommerville Type Relations
Andrey O. Matveev · 2023
An arrangement of distinct oriented lines crossing the origin (0, 0) the two-dimensional Euclidean space ℝ 2 on a piece of paper represents implicitly a rank 2 system of homogeneous strict linear inequalities. If there is no point lying on the positive sides of all lines of the arrangement, then the inclusion-maximal positive parts of topes of the oriented matroid realized by the arrangement are the multi-indices of maximal feasible subsystems of an infeasible system. If the system has at least five maximal feasible subsystems, then the numbers of feasible subsystems satisfy relations derived from the Dehn–Sommerville equations for the face numbers of the boundary complexes of simplicial convex polytopes. In such a situation, the tope set of our oriented matroid, regarded as the vertex set of a symmetric cycle in a hypercube graph, leads us to Dehn–Sommerville type relations for a certain abstract simplicial complex associated with the decomposition set for the positive vertex of the graph. In this chapter, we present Dehn–Sommerville type relations that are valid for arbitrary vertices of hypercube graphs with sufficiently large decomposition sets.