The symmetric functions catalog

An overview of symmetric functions and related topics



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. \]

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

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.


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 Moreover, there is a nice combinatorial description on the internal and external activity for the bases.

Kazhdan–Lusztig polynomials Inverse Kazhdan–Lusztig polynomials for matroids.

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.


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. q-Delta-matroids Determining if contraction of element in transversal matroid is a gain transversal, can be done in polynomial time. Matchings and transversal matroids are the same. Bonin, intro to transversal matroids and LPMs Ehrhart for panhandle and Lattice paths Ehrhart poly is not computable via deletion-contraction.

Tutte polynomials for polymatroids Symmetric lattice path matroids Schubert calculus and sparse paving matroids Matroids, Ehrhart stuff (looks nice) Matroids (Schubert matroids) Ehrhart positivity, Kohnert diagrams Matroid counterexample thing Dyck paths, unit intervals and positroids Polymatroids 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. Tutte polynomials and valuations, Ferroni, Schröter Every matroid basis polytope has IDP. Earlier, in here: Every matroid base polytope has a regular unimodular triangulation