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

4. Combinatorics and Graph Theory

    1.     Let $S_{2n}$ be the convex hull of all adjacency matrices of perfect matchings. Let \[\mu_{2n}:=\min\{ \text{haf}(B):B\in S_{2n}\}, \] where \[\text{haf}(B):=\frac{1}{n!2^n}\frac{\partial}{\partial x_1\cdots\partial x_{2n}}(x^{T}Bx)^n \] is the hafnian of $B$.

      Problem 4.1.

      [S. Friedland]
      1. Is it true that \[\alpha:=\liminf_n \frac{\log\mu_{2n}}{2n}>-\infty \text{ ?}\]

      2. Estimate $\mu_{2n}$.

        •     The type-$D_n$ Eulerian polynomials are given by \[ E(x) : = \sum_w x^{\#\{s:\text{length}(ws)<\text{length}(w)\}}. \]

          Problem 4.2.

          [F. Brenti] Prove that E(x) has only real zeros.
            • Problem 4.3.

              [A. Sokal] Is there a decent multivariate extension of the Chudnovsky-Seymour Theorem that the vertex independent set polynomial of a claw-free graph has only real roots?
                • Problem 4.4.

                  [S. Friedland] Generalize the Chudnovsky-Seymour (Heilmann-Lieb) Theorem. Extend the common interlacing property to several variables.

                      Cite this as: AimPL: Stability and hyperbolicity, available at http://aimpl.org/hyperbolicpoly.