 |
|
||||||||||
A Graph Theoretical Approach for Reconstruction and Generation of Oriented Matroids
IFOR Events
Seminar:
'Optimization & Applications'
(see information & program)
Feb 20 - May 28, 2012
IFOR Mitteilungen
This booklet informs about ongoing projects and future events at the IFOR and appears once at the end of the year.
| Author | Lukas Finschi |
| Abstract |
This thesis studies the reconstruction and generation of oriented matroids. Oriented matroids are a combinatorial abstraction of discrete geometric objects such as point configurations or hyperplane arrangements. Both problems, reconstruction and generation, address fundamental questions of representing and constructing (classes of) oriented matroids. The representations which are discussed in this thesis are based on graphs that are defined by the oriented matroids, namely tope graphs and cocircuit graphs. The first part of this thesis studies properties of these graphs and the question as to what extent oriented matroids are determined by these graphs. In the second part, these graph representations are used for the design of generation methods which produce complete lists of oriented matroids of given number of elements and given rank. These generation methods are used in the third part for the construction of a catalog of oriented matroids and of complete listings of the combinatorial types of point configurations and hyperplane arrangements. The reconstruction problem is the problem of whether an oriented matroid can be reconstructed from some representation of it, which is here the tope graph and the cocircuit graph. It is known that tope graphs determine oriented matroids up to isomorphism. However, there is no simple graph theoretical characterization of tope graphs of oriented matroids. We strengthen the known properties of tope graphs and prove that for every element f the topes that are not bounded by f induce a connected subgraph in the tope graph. This property is later used for the design of generation methods that are based on tope graphs. On the contrary to the tope graph case, it is known that cocircuit graphs do not determine isomorphism classes of oriented matroids. However, if every vertex is labeled by its supporting hyperplane, oriented matroids can be reconstructed up to reorientation. We present a simple algorithm which gives a constructive proof for this result. Furthermore, we extend the known results and show that the isomorphism class of a uniform oriented matroid is determined by its cocircuit graph. In addition, we present polynomial algorithms which provide a constructive proof to this result, and it is shown that the correctness of the input of the algorithms can be verified in polynomial time. The generation problem asks for methods for listing all oriented matroids of given cardinality of the ground set and given rank. The known generation methods have been designed primarily for uniform oriented matroids in rank 3 or 4. Our methods are based on tope graph and cocircuit graph representations and generate all isomorphism classes of oriented matroids, including non-uniform ones in arbitrary rank. The generation approach incrementally extends oriented matroids by adding single elements. These single element extensions are studied in terms of localizations of graphs, which are signatures on the vertex sets that characterize single element extensions. The first two generation methods are based on tope graphs. These methods make use of the properties of tope graphs studied earlier in this thesis, especially of the new connectedness property. The first method is a reverse search method for the generation of generalized localizations in the tope graph. In the second method graph automorphisms are used to reduce the amount of isomorphic single element extensions. Furthermore we discuss techniques which reduce multiple extension of the same oriented matroid from different minors. Two algorithms based on cocircuit graph representations are designed similarly to those based on tope graphs. However, all these first four generation methods lack efficiency, and a reason for this is that they do not use a good characterization of localizations. Due to a result of Las Vergnas, localizations of cocircuit graphs can be characterized by sign patterns on the coline cycles in the cocircuit graph. This allows us to design a fifth method which is efficient in practice. This method is a backtracking algorithm which enumerates all sign patterns of coline cycles that are feasible in terms of the characterization. It turns out that the method is similar to a method of Bokowski and Guedes de Oliveira for the uniform case. Our method is more general as it is capable to handle all oriented matroids in arbitrary rank, including non-uniform oriented matroids. Furthermore it uses an efficient data structure and a new dynamic ordering in the backtrack procedure. The generation methods are used for the construction of a catalog of oriented matroids. This catalog is organized using basis orientations of oriented matroids. We discuss some properties of the catalog and a method to generate the catalog. The catalog of oriented matroids can be used to find complete listings of combinatorial types of point configurations and hyperplane arrangements. We study these listing problems and discuss solution methods. Furthermore we show by an example the potential of these complete listings in resolving geometric conjectures. The listings of oriented matroids, point configurations, and hyperplane arrangements can be accessed via the Internet. |
| Download | PDF, PS, PS.gz |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
