Séminaire Lotharingien de Combinatoire, B12a (1985).
[Formerly: Publ. I.R.M.A. Strasbourg, 1986, 314/S-12, p. 67-107.]

Pierre Duchet

La convexité dans les structures combinatoires

Abstract. Axiomatic convexity investigates properties from usual convexity in the framework of a purely abstract structure, such as a segment structure or a closure space (whose closed sets play the role of the convex sets). It includes, e.g., the synthetic approach to convexity and the search for general relations among parameters such as the Helly, partition and exchange numbers. Recent developments on these two topics are reviewed in the first part of the paper; the nerve problem and varieties are also mentioned.

Convex notions can be defined in various combinatorial structures. In the second part, we consider greedoids, graphs and hypergraphs, acyclic oriented matroids, partially ordered sets, and trees. The usefulness of convexity ideas is illustrated, for instance concerning alternative characterizations of shelling structures as convex geometries, and in connection with the Hadwiger conjecture on graph contraction and coloring.


The paper has been finally published under the title "Convexity in combinatorial structures" in Proceedings of the 14th winter school on abstract analysis (Srní, 1986). Rend. Circ. Mat. Palermo (2) Suppl. No. 14, (1987), 261-293.