Discrete Mathematics 308 (2008), 1674-1689.
The max-flow min-cut property of 2-dimensional affine convex geometries.
by Masahiro Hachimori and Masataka Nakamura
Abstract
In a matroid, $(X,e)$ is a rooted circuit if $X$ is a set not containing
element $e$ and $X\cup\{e\}$ is a circuit. We call $X$ a stem of
$e$. A stem clutter is the collection of stems of a fixed element.
Seymour \cite{seymour} proved that a stem clutter of a binary matroid
has the max-flow min-cut property if and only if it does not contain
a minor isomorphic to $Q_6$.
We shall present an analogue of this result
in affine convex geometries.
Precisely, we shall show that a stem clutter of an element $e$
in a convex geometry arising from $2$-dimensional point configuration
has the max-flow min-cut property if and only if the configuration
has no subset forming a `Pentagon' configuration with center $e$.
Firstly we introduce the notion of closed-set systems.
This leads to a common generalization of rooted circuits
both of matroids and convex geometries (antimatroids).
We further study some properties of affine convex geometries
and their stem clutters.