Cospanning Characterizations of Violator and Co-violator Spaces

Given a finite set E and an operator σ:2^E⟶2^E, two subsets X,Y⊆E are cospanning if σ(X)=σ(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 α,β:2^E⟶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., α(βX)=α(X) and βαX=βX for every X⊆E.