Cospanning Characterizations of Violator and Co-violator Spaces

Given a finite set E and an operator \(\sigma :2^{E}\longrightarrow 2^{E}\) , two subsets \(X,Y\subseteq E\) are cospanning if \(\sigma (X)=\sigma (Y)\) (Korte, Lovász, Schrader; 1991). We investigate cospanning relations on violator spaces. A notion of a violator space was introduced in (Gärtner, Matoušek, Rüst, Škovroňby; 2008) as a combinatorial framework that encompasses linear programming and other geometric optimization problems. Violator spaces are defined by violator operators. We introduce co-violator spaces based on contracting operators known also as choice functions. Let \(\alpha ,\beta :2^{E}\longrightarrow 2^{E}\) be a violator operator and a co-violator operator, respectively. Cospanning characterizations of violator spaces allow us to obtain some new properties of violator operators and co-violator operators, emphasizing their interconnections. In particular, we show that uniquely generated violator spaces satisfy so-called Krein-Milman properties, i.e., \(\alpha (\beta \left( X\right) )=\alpha (X)\) and \(\beta \left( \alpha \left( X\right) \right) =\beta \left( X\right) \) for every \(X\subseteq E\) .