Mathematics – Combinatorics
Scientific paper
2012-01-14
Mathematics
Combinatorics
Aside from the abstract, this paper was written before the author learned of antimatroids. Antimatroid theorists will no doubt
Scientific paper
Antimatroids were discovered by Dilworth in the context of lattices [4] and introduced by Edelman and Jamison as convex geometries in[5]. The author of the current paper independently discovered (possibly infinite) antimatroids in the context of proof systems in mathematical logic [1]. Carlson, a logician, makes implicit use of this view of proof systems as possibly infinite antimatroids in [2]. Though antimatroids are in a sense dual to matroids, far fewer antimatroid forbidden minor theorems are known. Some results of this form are proved in [6], [7], [8], and [9]. This paper proves two forbidden induced minor theorems for these objects, which we think of as proof systems. Our first main theorem gives a new proof of the forbidden induced minor characterization of partial orders as proof systems, proved in [8] in the finite case and stated in [10] for what we call strong aut descendable proof systems. It essentially states that, pathologies aside, there is a certain unique simplest nonposet. Our second main theorem states the new result that, pathologies aside, there is a certain unique simplest proof system containing points $x$ and $y$ such that $x$ needs $y$ in one context, yet $y$ needs $x$ in another.
No associations
LandOfFree
Two Forbidden Induced Minor Theorems for Antimatroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Two Forbidden Induced Minor Theorems for Antimatroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two Forbidden Induced Minor Theorems for Antimatroids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-693736