The ubiquity of linear orders in combinatorics (06.08.2020)

José Alejandro Samper and Alexander Heaton

One common technique in the study of structures associated to a finite set is to enrich them with a total order and study the additionally acquired properties. This occurs frequently in mathematics, oftentimes implicitly. For instance, a collection of vectors on \(\mathbb{R}^n\) can be arranged as the columns of a matrix. Often, the order of these columns matters a great deal. For example, solving very large linear systems underlies much of scientific computing, and choosing a good column order can make the difference between a usable solution and complete failure. Even in theoretical situations where you may think order plays no role, it can provide additional structure worth studying.

By abstracting the notion of linear independence one encounters matroids: objects originally defined by Whitney to study graphs and vector configurations. Matroids have found a place in numerous applications to pure and applied mathematics. Roughly speaking, one forgets about coordinates but remembers which vectors are linearly independent. This allows us to better understand the topology of hyperplane arrangements, torus orbits in Grassmannians, the success of greedy algorithms, and more, purely in terms of combinatorics. In all these examples, much of the combinatorial analysis relies heavily on the choice of linear order.

One advantage of passing to the language of matroids is that many questions can be recast in terms of polytopes and simplicial complexes, which have rich combinatorial and geometric structure. Of particular interest to us are shelling orders; inductive recipes to build these combinatorial objects in a way that easily keeps track of some important changes occurring along the way. The importance of constructing matroids by using shelling orders has long been recognized, but the dependence on the specific order has not been fully exploited.

Figure 1: Graphical matroid with two activity posets (right) obtained from different linear functionals (orders on the edges) applied to the 4-dimensional matroid polytope in \(\mathbb{R}^5\) whose Schlegel diagram is displayed on the left.

Every matroid \(M\) has a matroid basis polytope \(P_M\) and an independence simplicial complex \(I(M)\). In recent work [2] we use the geometry of \(P_M\) to navigate a large family of shelling orders of \(I(M)\). A generic linear functional on the ambient space of the polytope induces a linear order on the ground set of the matroid. Sorting the vertices according to the values of linear functionals recovers the classical theory of linear orders, including the classical internal activity defined by Tutte. The geometry further suggests that sorting the vertices by values of certain piecewise linear functionals interpolates between the results of different linear orders, producing a large amount of additional combinatorial data. Our methods allow the systematic study of differences between choices of linear orders and their piecewise linear generalizations. This opens the future possibility of using these tools to choose shelling orders according to different needs. The results continue and expand previous work [1, 3] related to linear orders on matroids.

We also investigate potential connections of our new results to two old conjectures in combinatorics due to Stanley and Simon, and present freely available software for their exploration. Our experiments reveal many possible directions for future inquiry, listed in various conjectures and questions throughout.


[1] Federico Castillo, Jeremy Martin, and José Alejandro Samper. Hopf monoids of ordered simplicial complexes. To appear in the proceedings of FPSAC 2020. arXiv:2004.07308, 2020.
[2] Alexander Heaton and José Alejandro Samper. Dual matroid polytopes and internal activity of inde- pendence complexes. arXiv:2005.04252, 2020.
[3] José Alejandro Samper. Quasi-matroidal classes of ordered simplicial complexes. To appear in Journal of Combinatorial Theory, Series A., 2020.
06.08.2020, 16:43