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

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

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.

## More on matroids

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 polymatroidshttps://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

- [BJK23] Marc Besson, Sam Jeralds and Joshua Kiers. Weight polytopes and saturation of Demazure characters. Mathematische Annalen, May 2023.
- [Diz20] Avery J St. Dizier. Combinatorics of Schubert polynomials. Cornell university. 2020.
- [FGPS20] Neil J. Y. Fan, Peter L. Guo, Simon C. Y. Peng and Sophie C. C. Sun. Lattice points in the Newton polytopes of key polynomials. SIAM Journal on Discrete Mathematics, 34(2):1281–1289, January 2020.
- [FMD18] Alex Fink, Karola Mészáros and Avery St. Dizier. Schubert polynomials as integer point transforms of generalized permutahedra. Advances in Mathematics, 332:465–475, July 2018.
- [MMS22] Jacob P. Matherne, Alejandro H. Morales and Jesse Selover. The Newton polytope and Lorentzian property of chromatic symmetric functions. arXiv e-prints, 2022.
- [MTY19] Cara Monical, Neriman Tokcan and Alexander Yong. Newton polytopes in algebraic combinatorics. Selecta Mathematica, 25(5), October 2019.
- [NK09] Hirokazu Nishimura and Susumu Kuroda. A lost mathematician, takeo nakasawa. Birkhäuser Basel, 2009.
- [NNTNDTDLH23] Duc-Khanh Nguyen, Giao Nguyen Thi Ngoc, Hiep Dang Tuan and Thuy Do Le Hai. Newton polytope of good symmetric polynomials. Comptes Rendus. Mathématique, 361(G4):767–775, May 2023.
- [Whi35] Hassler Whitney. On the abstract properties of linear dependence. American Journal of Mathematics, 57(3):509, July 1935.
- [WZZ24] Bo Wang, Candice X. T. Zhang and Zhong-Xue Zhang. Newton polytopes of dual $k$-Schur polynomials. arXiv e-prints, 2024.