Cospanning characterizations of antimatroids and convex geometries

Kempner Yulia, Vadim E. Levit

פרסום מחקרי: נייר עבודה / גרסה מוקדמתגרסה מוקדמת

36 הורדות (Pure)

תקציר

Given a finite set $E$ and an operator $\sigma:2^{E}\longrightarrow2^{E}$, two sets $X,Y\subseteq E$ are \textit{cospanning} if $\sigma\left( X\right) =\sigma\left( Y\right) $. Corresponding \textit{cospanning equivalence relations} were investigated for greedoids in much detail (Korte, Lovasz, Schrader; 1991). For instance, these relations determine greedoids uniquely. In fact, the feasible sets of a greedoid are exactly the inclusion-wise minimal sets of the equivalence classes. In this research, we show that feasible sets of convex geometries are the inclusion-wise maximal sets of the equivalence classes of the corresponding closure operator. Same as greedoids, convex geometries are uniquely defined by the corresponding cospanning relations. For each closure operator $\sigma$, an element $x\in X$ is \textit{an extreme point} of $X$ if $x\notin\sigma(X-x)$. The set of extreme points of $X$ is denoted by $ex(X)$. We prove, that if $\sigma$ has the anti-exchange property, then for every set $X$ its equivalence class $[X]_{\sigma}$ is the interval $[ex(X),\sigma(X)]$. It results in the one-to-one correspondence between the cospanning partitions of an antimatroid and its complementary convex geometry. The obtained results are based on the connection between violator spaces, greedoids, and antimatroids. Cospanning characterization of these combinatorial structures allows us not only to give the new characterization of antimatroids and convex geometries but also to obtain the new properties of closure operators, extreme point operators, and their interconnections.
שפה מקוריתאנגלית
סטטוס פרסוםפורסם - 18 יולי 2021

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Cospanning characterizations of antimatroids and convex geometries'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי