DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

                         An Introduction to Matroids,                        
                  Oriented Matroids, and Linear Programming                  

                               Jack R. Edmonds                               
             University of Waterloo and University of Copenhagen             

                   Wednesday, November 1, 1995, at 12:15 PM                  
                               The Seminar Room                              


A matroid is an axiomatically defined combinatorial  structure, and so is an
oriented matroid.  Both,  in very  different ways,  are  closely related  to
linear programming.

We  will  see  how  general  matroids  are  algorithmically  nice  by  being
essentially the same as certain special  systems of linear inequalities.  We
will see how oriented matroids  (special as matroids) are  an abstraction of
general systems of linear inequalities which helps us to discover and derive
algorithmically useful linear inequality theory.

To a large extent, "linear inequality theory" means "Farkas Lemma", which we
study in some  depth.  From an especially  simple oriented-matroid  proof of
Farkas lemma, we obtain a new linear programming pivot method, which remains
to be tested.

[This is part two of a talk in two parts]


                                                                 Bjarne Toft