Vladimir Danilov ; Alexander Karzanov ; Gleb Koshevoy - The purity of set-systems related to Grassmann necklaces

dmtcs:2392 - Discrete Mathematics & Theoretical Computer Science, January 1, 2014, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) - https://doi.org/10.46298/dmtcs.2392
The purity of set-systems related to Grassmann necklacesArticle

Authors: Vladimir Danilov 1; Alexander Karzanov 2; Gleb Koshevoy 1

  • 1 Central Institute of Economics and Mathematics of the RAS
  • 2 Institute for System Analysis of the RAS

Studying the problem of quasicommuting quantum minors, Leclerc and Zelevinsky introduced in 1998 the notion of weakly separated sets in $[n]:=\{1,\ldots, n\}$. Moreover, they raised several conjectures on the purity for this symmetric relation, in particular, on the Boolean cube $2^{[n]}$. In 0909.1423[math.CO] we proved these purity conjectures for the Boolean cube $2^{[n]}$, the discrete Grassmanian $\binom{[n]}{r}$, and some other set-systems. Oh, Postnikov, and Speyer in arxiv:1109.4434 proved the purity for weakly separated collections inside a positroid which contain a Grassmann necklace $\mathcal {N}$ defining the positroid. We denote such set-systems as $\mathcal{Int}(\mathcal {N} )$. In this paper we give an alternative (and shorter) proof of the purity of $\mathcal{Int}(\mathcal {N} )$ and present a stronger result. More precisely, we introduce a set-system $\mathcal{Out}(\mathcal {N} )$ complementary to $\mathcal{Int}(\mathcal {N })$, in a sense, and establish its purity. Moreover, we prove (Theorem~3) that these two set-systems are weakly separated from each other. As a consequence of Theorem~3, we obtain the purity of set-systems related to pairs of weakly separated necklaces (Proposition 4 and Corollaries 1 and 2). Finally, we raise a conjecture on the purity of both the interior and exterior of a generalized necklace.


Volume: DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
Section: Proceedings
Published on: January 1, 2014
Imported on: November 21, 2016
Keywords: set systems,Grassmann necklaces,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 288 times.
This article's PDF has been downloaded 318 times.