| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

4. New Polynomials Arising from Matroids


    1. Add remark

      Problem 4.1.

      Let $M$ be a matroid (say graphic) of rank $d$ with ground set $E$ with $m$ elements. Let $S_1, \dots, S_n \subseteq E$ (not necessarily disjoint). Let $\alpha \in \Z^n_{\ge 0}$ with $|\alpha| = \sum_{i=1}^n \alpha_i = d$. We define $c_{\alpha}$ to be the number of bases $B$ of the matroid $M$ s.t. $\exists T_1, \dots, T_n$ disjoint with $T_i \subseteq S_i$ and $|B \cap T_i| = \alpha_i$. Is \[ p(x) = \sum_{\alpha \in \Z^n_{\ge 0}, |\alpha| = d} \frac{c_{\alpha} x^{\alpha}}{\alpha!} \] Lorentzian?

        •     To a loopless matroid $M$ of rank $d+1$, we can associated a univariate polynomial of degree $d$ $H_M(t)$ (the Chow polynomial) recursively as follows: if the rank of the matroid is 0, then $H_M$ polynomial is identically 1, otherwise, this polynomial is defined by recursion by \[ H_M(t) = \sum_{F \text{ nonempty flat of }M} \overline{\chi_{M^F}}(t) H_{M_F}(t). \]

          Add remark

          Problem 4.2.

          Here, $M_F$ is the result of contracting $F$ in $M$, $M^F$ is the restriction of $M$ to $F$ and $ \overline{\chi_{M^F}}(t)$ is the reduced characteristic polynomial of $M$. Is this polynomial should be real rooted for any matroid?

              Cite this as: AimPL: The geometry of polynomials in combinatorics and sampling, available at http://aimpl.org/geompolysampling.