
## 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.