The symmetric functions catalog

An overview of symmetric functions and related topics

2024-06-24

Matroids

Matroids were first introduced by H. Whitney [Whi35], and independently by [NK09]. This was further developed by

One motivating example for introducing matriods is the notion of bases for a vector space. Let $E = \{v_1,\dotsc, v_n \}$ be a collection of vectors in some $r$-dimensional space $V.$ We let $\mathcal{B}$ be the collection of subsets of $E$ which constitute a basis for $V.$ The pair $(E,\mathcal{B})$ is then an example of a matroid.

There are many equivalent definitions of a matroid. Let $E$ be a set (called the ground set) and let $\mathcal{B}$ be a collection of subsets of size $r$ from $E.$ Then $M = (E,\mathcal{B})$ is a matroid if the basis exchange axiom is satisfied. This states that for every two different $A, B \in \mathcal{B}$ and $x \in A \setminus B,$ there is some $y \in B \setminus A$ such that

\[ (A \setminus \{x\}) \cup \{y\} \in \mathcal{B}. \]

The cardinality, $r,$ of each set in $\mathcal{B}$ is called the rank of the matroid, and the set $\mathcal{B}$ are the bases of $M.$

Example (Uniform matroid).

The uniform matroid $U_{r,n}$ is the matroid on ground set $[n]$ and the bases being all $r$-element subsets of $[n].$

Dual of a matroid

If $M=(E,\mathcal{B})$ then $M^* \coloneqq (E,\mathcal{B}^*)$ with

\[ \mathcal{B}^* \coloneqq (E \setminus A : A \in \mathcal{B}) \]

is also a matroid. The matroid $M^*$ is called the dual of $M.$

The dual of the uniform matroid $U_{r,n}$ is the uniform matroid $U_{n-r,n}.$

Realizable matroids and graphical matroids

A matroid isomorphism from $(E_1,\mathcal{B}_1)$ to $(E_2,\mathcal{B}_2)$ is a bijection from $E_1$ to $E_2$ which induces a bijection from $\mathcal{B}_1$ to $\mathcal{B}_2.$

Given a $r \times n$ full-rank matrix $X$ over a field $\mathbb{F},$ we let $M[X]$ be the matriod with ground set being the column vectors of $X,$ and bases being the collection of all sets of columns being of full rank.

A matroid $M$ is said to be realizable over a field $\mathbb{F}$ if it is isomorphic to some $M[X]$ with $X \in \mathbb{F}^{r \times n }.$

There are matroids which are not realizable over any field, for example the Vámos matroid. It is the matroid whose bases are all $4$-elememnt subsets of $[8],$ except

\[ 1234, 1256, 1278, 3456, 5678. \]
Theorem.

If $M$ is representable over $\mathbb{F}$ then so is $M^*.$

Matroid loops and coloops

Let $M$ be a matroid on the ground set $E.$ An element $e \in E$ is called a loop if it does not appear in any basis. An element $e \in E$ is called a coloop if it appears in every basis.

Minors of a matroid

Let $M=(E,\mathcal{B})$ be a matroid and $e \in E.$ The deletion $M \setminus e$ is the matroid on ground set $E\setminus \{e\}$ whose bases are $\{ B \in \mathcal{B} : e \notin B \}.$ Simply put, it is everything in $M$ avoiding $e.$

The contraction $M / e$ is the matroid on ground set $E\setminus \{e\}$ whose bases are $\{ B \setminus \{e\} : B \in \mathcal{B} \text{ and } e \in B \} .$

One has that $M/e = (M^* \setminus e)^*.$

Tutte polynomial

The Tutte polynomial $T_M(x,y)$ of a matroid $M$ (on ground set $E$) is defined via a deletion-contraction recursion. If $M$ is the empty matroid (on ground set $\emptyset$) then $T_M(x,y) \coloneqq 1.$

If $x \in E$ is a loop in $M$ then

\[ T_m(x,y) = y \cdot T_{M/e}(x,y). \]

If $x \in E$ is a coloop in $M$ then

\[ T_m(x,y) = x \cdot T_{M/e}(x,y). \]

If $x \in E$ is neither a loop or a coloop, then

\[ T_m(x,y) = T_{M/e}(x,y) + T_{M\setminus e}(x,y). \]
Example.

The uniform matroid $U_{2,4}$ has Tutte polynomial $x^2 + 2x + y^2 + 2y.$

Internal and external activity

In the definition below, we assume that the ground set is $\{1,2,\dotsc,n\}.$ For other ground sets, one needs to choose a total ordering on the ground set, and the word 'smaller' refers to this ordering.

Definition (Internally and externally active elements).

Let $\mathcal{B}$ be the set of bases for a matroid with ground set $E=\{1,2,\dotsc,n\}.$ Let $F \in \mathcal{B}.$ An element $e\in E$ is said to be

  • internally active if $e \in F,$ and there is no smaller $y \in E\setminus F$ such that \[ (F\setminus \{e\})\cup \{y\} \text { is in } \mathcal{B}; \]
  • externally active if $e \notin F,$ and there is no smaller $y \in F$ such that \[ (F\setminus \{y\})\cup \{e\}\text { is in } \mathcal{B}. \]

The Tutte polynomial can then be expressed as

\[ T_M(x,y) = \sum_{B \in \mathcal{B}} x^{ia(B)} y^{ea(B)} \]

where $ia(b)$ and $ea(B)$ denotes the internal and external activity, respectively.

Properties of the Tutte polynomial

We have that $T_{M}(x,y) = T_{M^*}(y,x).$ Moreover, the Tutte polynomial is multiplicative with respect to direct sum:

\[ T_{M_1 \oplus M_2}(x,y) = T_{M_1}(x,y) T_{M_2}(x,y). \]

Rank functions

A matroid can also be defined via a rank function. Let $E$ be a (ground) set. A rank function $r$ is an integer-valued function on subsets of $E,$ satisfying the following three properties:

  • $0 \leq r(X) \leq |X|$ for every $X \subseteq E$;
  • $r(X) \leq r(Y)$ for all $X\subseteq Y \subseteq E$;
  • $r(X \cup Y) + r(X \cap Y) \leq r(X)+r(Y),$ whenever $X,Y \subseteq E.$

A set is an independent set if $r(X)=|X|.$ The bases of a matroid are all independent sets of maximal rank.

If $(E,\mathbal{B})$ is a matroid with bases $\mathbal{B},$ then the rank of a set $X$ is simply

\[ \max \{ |X \cap B| : B \in \mathbal{B} \}. \]

That is, the rank is the cardinality of the maximal independent set it contains.

Flats

A subset $X \subseteq E$ of a matroid is called a flat (or closed) if there is no element we can add to $X$ from $E \setminus X$ and preserve the rank.

The set of flats form a lattice under inclusion.

Lattice path matroids

The Tutte polynomial for a lattice path matroid can be computed efficiently, see https://arxiv.org/pdf/math/0211188.pdf. Moreover, there is a nice combinatorial description on the internal and external activity for the bases.

Kazhdan–Lusztig polynomials

https://arxiv.org/pdf/2007.15349.pdf Inverse Kazhdan–Lusztig polynomials for matroids.

https://arxiv.org/pdf/2311.06929.pdf

Saturated Newton polytopes

Given a polynomial $f \in \setC[x_1,\dotsc,x_n]$ with $f = \sum_\alpha c_\alpha \xvec^\alpha,$ with $\alpha \in \setN^n,$ the support of $f$ is the set $\mathrm{supp}(f) \coloneqq \{\alpha : c_\alpha \neq 0\}.$ The Newton polytope of $f$ is defined as the convex hull of the support. This is a polytope in $\setR^n$ which we denote by $\mathrm{Newton}(f).$

A polynomial has a saturated Newton polytope (SNP) if

\[ \mathrm{Newton}(f)\cap \setZ^n = \mathrm{supp}(f). \]

Several classical polynomials such as Schur polynomials, Stanley symmetric functions have saturated Newton polytopes.

A seminal paper in this area is [MTY19] where many conjectures were presented. Several have since then been proved.

Key polynomials and Schubert polynomials have SNP [FMD18]. Key polynomials in other types ($A_r,$ $B_r,$ $C_r,$ $F_4,$ $G_2$) also have SNP, see [BJK23]. SNP for Chromatic symmetric polynomials obtained from incomparability graphs of (3+1)-free posets was proved in [MMS22].

For more background and results, see [WZZ24].

In [NNTNDTDLH23] the authors prove SNP for many families of symmetric functions, such as SChur-P and Schur-Q polynomials as well as many of the above mentioned families. Moreover, they prove that $\mathrm{Newton}(f)$ has the integer decomposition property in many cases.

M-convexity

A subset $J \in \setN^n$ is M-convex if for all $\alpha,\beta \in J,$ and any index $i\in [n]$ with $\alpha_i \gt \beta_i,$ there is some index $j$ with $\alpha_j \lt \beta_j$ and $\alpha - e_i + e_j \in J.$ Here, $e_i$ is the $i^\thsup$ unit vector.

This notion generalizes the basis exchange axiom for matroids.

Theorem (See [Diz20]).

A homogeneous polynomial $f$ is M-convex if and only if $f$ has a saturated Newton polytope and this Newton polytope a generalized permutahedron.

Key polynomials are M-convex (conjectured earlier by Monical, Tokcan and Yong [MTY19]) see [FGPS20].

In [WZZ24], it is proved that affine Stanley symmetric functions and cylindric skew Schur functions are $M$-convex.

https://arxiv.org/pdf/2406.14944 q-Delta-matroids

https://arxiv.org/pdf/2405.09088 Determining if contraction of element in transversal matroid is a gain transversal, can be done in polynomial time.

https://arxiv.org/pdf/2404.09347.pdf

https://www.sciencedirect.com/science/article/pii/089396599290103G Matchings and transversal matroids are the same.

https://maa.org/sites/default/files/pdf/shortcourse/2011/TransversalNotes.pdf Bonin, intro to transversal matroids and LPMs

https://arxiv.org/pdf/2201.12442.pdf Ehrhart for panhandle and Lattice paths

https://www.math.ucdavis.edu/~deloera/RECENT_WORK/matroidpolys.pdf Ehrhart poly is not computable via deletion-contraction.

Tutte polynomials for polymatroids

https://arxiv.org/pdf/2311.15441.pdf Symmetric lattice path matroids

https://arxiv.org/pdf/2406.05384 Schubert calculus and sparse paving matroids

https://arxiv.org/pdf/2311.01640.pdf Matroids, Ehrhart stuff (looks nice) https://arxiv.org/pdf/2110.11549.pdf Matroids (Schubert matroids) Ehrhart positivity, Kohnert diagrams https://arxiv.org/pdf/2402.01272.pdf Matroid counterexample thing

https://arxiv.org/pdf/1912.08318.pdf Dyck paths, unit intervals and positroids

https://arxiv.org/pdf/2402.17582.pdf Polymatroids

https://arxiv.org/pdf/2402.17841.pdf Every positroid envelope class contains at least one graphic matroid, by explicitly constructing a planar graph whose cycle matroid lies in the desired positroid envelope.

https://arxiv.org/pdf/2403.17696.pdf Tutte polynomials and valuations, Ferroni, Schröter

https://doi.org/10.1016/j.jctb.2011.04.004 Every matroid basis polytope has IDP. Earlier, in here: https://arxiv.org/pdf/math/0307236.pdf

https://arxiv.org/pdf/2309.10229.pdf Every matroid base polytope has a regular unimodular triangulation

References