Matroid Enumeration for Incidence Geometry |
| |
Authors: | Yoshitake Matsumoto Sonoko Moriyama Hiroshi Imai David Bremner |
| |
Institution: | 1. Graduate School of Information Science and Technology, University of Tokyo, Tokyo, Japan 2. Graduate School of Information Sciences, Tohoku University, Sendai, Japan 3. Faculty of Computer Science, Univesity of New Brunswick, Fredericton, Canada
|
| |
Abstract: | Matroids are combinatorial abstractions for point configurations and hyperplane arrangements, which are fundamental objects
in discrete geometry. Matroids merely encode incidence information of geometric configurations such as collinearity or coplanarity,
but they are still enough to describe many problems in discrete geometry, which are called incidence problems. We investigate
two kinds of incidence problem, the points–lines–planes conjecture and the so-called Sylvester–Gallai type problems derived
from the Sylvester–Gallai theorem, by developing a new algorithm for the enumeration of non-isomorphic matroids. We confirm
the conjectures of Welsh–Seymour on ≤11 points in ℝ3 and that of Motzkin on ≤12 lines in ℝ2, extending previous results. With respect to matroids, this algorithm succeeds to enumerate a complete list of the isomorph-free
rank 4 matroids on 10 elements. When geometric configurations corresponding to specific matroids are of interest in some incidence
problems, they should be analyzed on oriented matroids. Using an encoding of oriented matroid axioms as a boolean satisfiability
(SAT) problem, we also enumerate oriented matroids from the matroids of rank 3 on n≤12 elements and rank 4 on n≤9 elements. We further list several new minimal non-orientable matroids. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|