Skip to main content
Name of paper
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Poset-troids...?

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 aksingasking (see e.g. httpsCameron, Dinu, Michałek, and Seynnaeve - Flag matroids://arxiv.org/abs/1811.00272 algebra and geometry).

Poset-troids...?

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 aksing (see e.g. https://arxiv.org/abs/1811.00272).

Poset-troids?

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).

Source Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Poset-troids...?

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 aksing (see e.g. https://arxiv.org/abs/1811.00272).