10
$\begingroup$

In many respects,

spanning tree : graph :: linear extension : poset

For instance, the number of spanning trees/linear extensions is a measure of the "richness" or "complexity" of the graph/poset. Also, the collection of all the spanning trees/linear extensions determines the graph/poset.

(Okay if the graph is not connected we should say "spanning forest" instead of "spanning tree"; but the tree terminology is more common.)

The collection of spanning trees of a graph (thought of as subsets of edges) is a prototypical example of a matroid. Indeed, the notion of matroid can be seen as an abstraction of this kind of collection.

Question: Has anyone ever defined/investigated a "matroid-like" abstraction of the collection of linear extensions of a poset? E.g., collections of permutations of size $n$ satisfying some compatibility condition?

A wildly optimistic guess would be that these could be related to the full flag variety in the way that matroids are related to Grassmannians; however, I take it that "flag matroids" already have an established meaning in this context, which at first glance does not appear to be related to what I am asking (see e.g. Cameron, Dinu, Michałek, and Seynnaeve - Flag matroids: algebra and geometry).

Improve this question
$\endgroup$
8
  • $\begingroup$ It seems maybe posets corresponding to “braid cones” and braid cones are unions of Weyl chambers (each of which correspond to a linear extension) might be in the direction of what you want? $\endgroup$
    – John Machacek
    Commented Apr 9, 2020 at 20:07
  • $\begingroup$ @JohnMachacek: Yes, I like this idea, but then every such poset-troid would be realizable as the set of linear extensions of a poset, right? $\endgroup$
    – Sam Hopkins
    Commented Apr 9, 2020 at 20:27
  • 1
    $\begingroup$ I guess it would depend on how we define poset-troids. I don't know what would be the correct definition with good properties. I could see it being something like: a collection of Weyl chambers that is connected in codim 1. This should include "realizable" poset-troids (coming from posets) plus some new things. $\endgroup$
    – John Machacek
    Commented Apr 10, 2020 at 0:56
  • $\begingroup$ Is there determinant or smth. like that formula for the number of linear extensions, like it exists for spanning trees? I know it only for skew Young tableaux. I am afraid that counting linear extensions is computationally hard even for finite subsets of $\mathbb{Z}^2$ (Igor Pak proved smth in this direction, I forgot exact formulation), so unlikely it exists, determinants are computationally ok. Maybe we should either restrict to some classes of posets, or modify the richness measure. $\endgroup$
    – Fedor Petrov
    Commented Apr 10, 2020 at 20:36
  • 1
    $\begingroup$ If you take a finite poset with a natural labeling, the set of linear extensions will be a down-set in the symmetric group with the weak Bruhat order. (I believe it will be a principal down-set if the poset is two-dimensional.) I would like to know how to characterize the down-sets that arise. $\endgroup$
    – Tri
    Commented May 14, 2020 at 21:12

1 Answer 1

Reset to default
3
$\begingroup$

I'm not aware of anything exactly along the lines of your question. It really depends on what properties you're hoping to generalize.

Here's one direction in which one can generalize. Promotion and evacuation are operations on the set of linear extensions of a poset. These operations can be formulated in a more general setting, as Stanley explains in his paper.

Your mention of the relationship between matroids and Grassmannians suggests that you might find the concept of Coxeter matroids interesting, but I don't think Coxeter matroids can plausibly be considered to be generalizations of the set of linear extensions of an arbitrary poset.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Timothy! Indeed, the question is vague, and what I'm "hoping" to generalize is unclear to me as well. The generalization of promotion/evacuation from Stanley's survey is very nice. I think the "flag matroids" which I mentioned in the question are a special case of Coxeter matroids, and as you said it's not clear that they're related to linear extension. $\endgroup$
    – Sam Hopkins
    Commented Apr 9, 2020 at 18:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .