Violator spaces vs closure spaces

Abstract: Violator Spaces were introduced by J. Matousek et al. in 2008 as generalization of Linear Programming problems. Convex geometries were invented by Edelman and Jamison in 1985 as proper combinatorial abstractions of convexity. Convex geometries are defined by anti-exchange closure operators. We investigate an interrelations between violator spaces and closure spaces and show that violator mapping may be defined by a week version of closure operators. Moreover, we prove that violator spaces with an unique basis satisfies the anti-exchange and the Krein-Milman properties.

Review text

The purpose of this paper is to make connections between two combinatorial concepts: the violator space and the closure space. The authors show that a violator mapping may be defined by a weak version of a closure operator. Also, they prove that violator spaces with a unique basis satisfy both the anti-exchange and the Krein-Milman properties. The authors introduce convex spaces as a generalization of violator spaces. Finally, they obtain a more general proof of the equivalence between uniquely generated violator spaces and partitions of the hypercube by hypercubes, and extend this result to convex spaces.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Violator spaces vs closure spaces

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