Discrete Mathematics and Optimization Seminar

Monday November 27th at 4.30pm
Burnside 1205

Title. On some axiomatisations of pseudoline arrangements, oriented matroids, and graph drawings.

Abstract. This talk introduces oriented matroids through several objects: pseudoline arrangements, point configurations,
and spatial graph projection drawings.

A pseudoline arrangement is a finite set of curves in a plane, such that each one is homeomorphic to a line,
and two pseudolines always cross at one point. The advantage of pseudolines in comparison with (straight) lines
is that there exist combinatorial axiomatizations: an equivalence with rank 3 oriented matroids, and even a
first-order logical axiomatization.

Graph drawings whose edges are drawn with curves that cross at most once can be described with a similar but
extended logical structure. According to Ringel's theorem, two pseudoline arrangements in general positions can
always be transformed one into the other by a sequence of triangle flips. This result generalizes to complete
graph drawings.

Considering points in the 3-dimensional real space leads on one hand to a spatial graph formed by the straight
edges joining the points, and on the other hand to a rank 4 oriented matroid. With the previous results, will
see that this last combinatorial structure determines, here, for instance, a projection of the spatial graph up
to triangle flips.