2012/01/09 by Gary Gordon, Gordon, Gary · 1 citation
Computer Science · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1201.1831
arxiv created 2012/01/09 · openalex publication_date 2012/01/09 · arxiv updated 2012/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a notion of duality (due to Brylawski) that generalizes matroid duality to arbitrary rank functions. This generalized duality allows for generalized operations (deletion and contraction) and a generalized polynomial based on the matroid Tutte polynomial. This polynomial satisfies a deletion-contraction recursion. We explore this notion of duality for greedoids, antimatroids and demi-matroids, proving that matroids correspond precisely to objects that are simultaneously greedoids and "dual" greedoids.