Discrete Mathematics 308 (2008), 1674-1689.

The max-flow min-cut property of 2-dimensional affine convex geometries.

by Masahiro Hachimori and Masataka Nakamura


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.