A graph theoretical approach for reconstruction and generation of oriented matroids
A graph theoretical approach for reconstruction and generation of oriented matroids
复制标题
重构和生成定向拟阵的图论方法
DOI：
10.3929/ethz-a-004255224
复制
发表时间：
2001
影响因子：
0.5
通讯作者：
L. Finschi
中科院分区：
文献类型：
--
作者：
L. Finschi
本文研究了有向拟阵的重构与生成。定向矩阵是离散几何对象的组合抽象，如点配置或超平面排列。这两个问题，重建和生成，解决表示和构造（类）定向矩阵的基本问题。本文所讨论的表示是基于有向拟阵定义的图，即拓扑图和余圈图。本文第一部分研究了这类图的性质以及在何种程度上这类图决定了定向拟阵。在第二部分中，这些图表示被用于生成方法的设计，这些生成方法产生给定元素数和给定秩的有向拟阵的完整列表。这些生成方法在第三部分中用于构造有向拟阵的目录和点构型和超平面排列的组合类型的完整列表。重构问题是一个有向拟阵是否可以从它的某种表示中重构出来的问题，这里的表示是拓扑图和余圈图。拓扑图决定定向拟阵直到同构。然而，有向拟阵的拓扑图还没有简单的图论刻画。我们加强了拓扑图的已知性质，证明了对于每一个元素/，不被/包围的拓扑在拓扑图中诱导出一个连通子图.这个属性后来用于设计基于拓扑图的生成方法。与拓扑图的情况相反，已知上圈图不确定有向拟阵的同构类。然而，如果每个顶点都被其支持超平面所标记，则定向拟阵可以重构到重定向，我们给出了一个简单的算法，并对这个结果给出了构造性的证明。进一步推广了已有的结果，证明了一致定向拟阵的同构类是由其余回路图决定的。此外，我们还提出了多项式算法，对这一结果给出了构造性的证明，并证明了该算法的输入的连续性可以在多项式时间内得到验证。生成问题要求列出给定基集基数和秩的所有定向拟阵的方法。已知的生成方法主要是针对秩为3或4的均匀定向拟阵而设计的。我们的方法是基于拓扑图和余圈图表示，并产生所有的同构类的定向拟阵，包括非均匀在任意秩。生成方法通过添加单个元素来逐步扩展定向拟阵。这些单个元素
This thesis studies the reconstruction and generation of oriented matroids. Oriented ma¬ troids are a combinatorialabstraction of discrete geometric objects such as point configurations or hyperplane arrangements. Both problems, reconstruction and generation, addressfundamental questions of representing and constructing (classes of) oriented ma¬ troids. The representations which are discussedin this thesis are based on graphs that are definedby the oriented matroids, namely tope graphs and cocircuit graphs. The first part ofthis thesisstudies properties ofthese graphs and the questionas to what extent oriented matroids are determined by these graphs. In the second part, these graph representations are used for the design of generationmethods which produce complete lists of oriented matroids ofgiven number of elements and given rank. Thesegenerationmethods are used in the third part for the construction of a catalog of oriented matroids and of complete listings of the combinatorialtypesof point configurations and hyperplane arrangements. The reconstruction problem is the problem of whether an oriented matroid can be reconstructedfrom somerepresentation of it, which is here the tope graph and the cocir¬ cuit 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 dement / the topes that are not bounded by / induce a connected subgraph in the tope graph. This propertyis later used for the design of generationmethods that are based on topegraphs. On the contrary to the tope graph case, it is known that cocircuit graphs do not determine isomorphismclasses 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 algorithmwhich gives a constructive proof for this result. Furthermore, we extend the known results and showthatthe isomorphismclass of auniform oriented matroid is determined by its cocircuitgraph. In addition, we present polynomial algorithmswhich provide a constructive proofto this result, and it is shown that the conectness of the input of the algorithmscan be verifiedin polynomial time. The generationproblem asks for methods for listing all oriented matroids of given cardinality of the ground set and given rank. The known generationmethods 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 isomorphismclasses of oriented matroids, including non-uniformones in arbitrary rank. The generationap¬ proach incrementallyextends oriented matroids by adding Single elements.These Single