Working Seminar on Formal Models, Discrete Structures, and Algorithms

Axiomatic theory of betweenness and related interval and convex structures

Matjaž Kovše (Slovenia)

When: Monday April 10, 10 am

Where: room C417 (at the very end of the corridor)


The experience of betweenness is natural in our everyday life as the concept of intermediacy is a universal concept. The betweenness relation has been implicitly used in the foundations of geometry since the times of Euclid. Gauss pointed out the absence of betweenness postulates in Euclid's treatment. Pasch in his book Vorlesungen über neuere Geometrie from 1882 followed with the first axiomatic treatment of this notion. Since then it has found its way of use also in many other areas outside geometry: algebra, topology, graph theory, computer science, bioinformatics, etc. During this talk we make a short introduction to the attempts of building a comprehensive mathematical theory of betweenness, intervals and convexity in discrete structures. We use the language of transit functions, which present a unifying approach for results and ideas on intervals, convexities and betweenness in graphs and posets, as proposed by Mulder. We present also a surprising connection between the recombination theory in evolutionary biology and oriented matroid theory, leading to the topological representations of transit sets of k-point crossover operators, and include some directions for further research. No previous knowledge on the topic is required.