Discrete Mathematics and Optimization Seminar

---

EMERIC GIOAN
LIRMM - CNRS
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.