Nima Amini

Nima Amini

PhD student
Department of Mathematics, KTH Royal Institute of Technology
     CV

ORCID iD iconMy ORCiD ID

Research interests:

  • Algebraic Combinatorics
  • Hyperbolic/Stable polynomials
  • Spectrahedral representations
  • Enumerative Combinatorics

Click on a figure to learn more about my research!

ResearchPictures Hyperbolic matroids d-matching polynomials Relaxed matching polynomials Combinatorial statistics and pattern avoidance The cyclic sieving phenomenon Hyperbolic polynomials

Papers

Non-representable hyperbolic matroids

and

Advances in Mathematics 43 (2018), 417-449.

Spectrahedrality of hyperbolicity cones of multivariate matching polynomials

Journal of Algebraic Combinatorics (to appear).

Equidistributions of Mahonian statistics over pattern avoiding permutations

Electronic Journal of Combinatorics 25 (1) (2018), P7

The cone of cyclic sieving phenomena

and

Discrete Mathematics 342 (6) (2019), 1581-1601

Stable multivariate generalizations of matching polynomials

(submitted)

Other Writings

Combinatorics and zeros of multivariate polynomials

PhD Thesis, KTH 2019.

Infinite-dimensional Lie algebras

Part III Essay, Cambridge Mathematical Tripos 2013-2014.

Extremal polymatroids

Unfinished thoughts on a new intriguing class of extremal problems

Geometry of zeros and applications

Typed personal notes based on lecture notes by Petter Brändén

Research

Hyperbolic polynomials may be viewed as multivariate generalizations of real-rooted polynomials in one variable. Formally, a polynomial \(h(\mathbf{z}) \in \mathbb{R}[z_1,\dots, z_n]\) is said to be hyperbolic with respect to a vector \(\mathbf{e} \in \mathbb{R}^n\) if \begin{align*} &(i) \hspace{0.5cm} h(\mathbf{z}) \text{ is a homogeneous polynomial } \text{ (i.e., } h(t\mathbf{z}) = t^dh(\mathbf{z})), \\ &(ii) \hspace{0.38cm} h(\mathbf{e}) \neq 0, \\ &(iii) \hspace{0.28cm} \text{for all } \mathbf{x} \in \mathbb{R}^n, \text{the univariate polynomial} \\ & \hspace{2cm} t \mapsto h(t\mathbf{e} - \mathbf{x}), \\ & \hspace{1.2cm} \text{has real zeros only.} \end{align*} Example: Let \(Z\) be a symmetric \(n \times n\) matrix with \(\binom{n+1}{2}\) indeterminate entries. An important example of a hyperbolic polynomial is the determinant polynomial \(h(Z) = \det(Z)\) which is hyperbolic with respect to the identity matrix \(\mathbf{e} = I\). Indeed, condition \((iii)\) amounts to the well-known fact that the characteristic polynomial of a real symmetric matrix is real-rooted.

The study of hyperbolic polynomials originated in PDE theory with the works for Petrowsky, Gårding, Hörmander, Atiyah and Bott. The analytical significance of hyperbolicity is that on the half-space \(H = \{\mathbf{x} \in \mathbb{R}^n : (\mathbf{x}, \mathbf{e}) \geq 0 \}\), the Cauchy problem $$ h\left ( \frac{\partial}{\partial z_1}, \dots, \frac{\partial}{\partial z_n} \right )u(\mathbf{z}) = f(\mathbf{z}) $$ has a unique solution \(u(\mathbf{z})\) for every \(f \in C_0^{\infty}(H) \) if and only if \(h\) is a hyperbolic polynomial with respect to \(\mathbf{e}\). Naturally such equations are called hyperbolic partial differential equations. A classical example is the second order wave equation $$ \frac{\partial^2 u}{\partial t^2} - c^2\frac{\partial^2 u}{\partial x^2} = 0. $$ In analogy with \(h(Z) = \det(Z)\), the roots of the univariate polynomial in \((iii)\) are called (hyperbolic) eigenvalues of \(\mathbf{x}\). The set of vectors \(\mathbf{x} \in \mathbb{R}^n\) with non-negative eigenvalues forms a convex cone \(\Lambda_+(h, \mathbf{e})\) called the hyperbolicity cone of \(h\) with respect to \(\mathbf{e}\).

The figure: The middle figure on the front page depicts the zero surface of the hyperbolic polynomial $$h(x,y,z) = 4xyz + xz^2 + yz^2 + 2z^3 − x^3 − 3zx^3 − y^3 − 3zy^2$$ with respect to \(\mathbf{e} = (0,0,1)\). The hyperbolicity cone consists of the connected component in \(\mathbb{R}^3\) containing \(\mathbf{e}\) (the pink line) cut out by the zero surface of \(h\).

Recently, efficient interior point methods have been developed for doing optimization over hyperbolicity cones, so called hyperbolic programming : \begin{align*} &\textbf{minimize } \hspace{1cm} \mathbf{c}^T \mathbf{x} \\ &\textbf{subject to } \hspace{0.8cm} A\mathbf{x} = \mathbf{b} \hspace{0.3cm} \text{and} \\ & \hspace{3.3cm} \mathbf{x} \in \Lambda_+(h,\mathbf{e}) \end{align*} Notable subfields of hyperbolic programming are Linear Programming (LP) and Semidefinite Programming (SDP). Linear Programming corresponds to minimizing a linear functional over a polyhedral cone, i.e, the hyperbolicity cone of a product of linear forms. Semidefinite Programming corresponds to minimizing a linear functional over the cone of positive semidefinite matrices, i.e., the hyperbolicity cone of the determinant polynomial \(h(Z) = \det(Z)\).

A major open problem with respect to hyperbolic polynomials is the Generalized Lax Conjecture which roughly asserts that hyperbolic programming is in fact not a generalization of semidefinite programming at all, but that the two fields are equivalent. The conjecture has been confirmed for a few special classes, but otherwise there is not overwhelming evidence.

In my research I have proved the Generalized Lax Conjecture for the class of multivariate matching polynomials $$ h_G(\mathbf{z}, \mathbf{w}) = \sum_{M} (-1)^{|M|} \prod_{v \not \in V(M)} z_v \prod_{e \in M} w_e^2 $$ where \(M\) runs over the set of matchings of a graph \(G\) and \(V(M) = \bigcup_{ij \in M} \{ i,j\}\). Recall that a matching \(M\) of a graph \(G\) is a subset of edges, no two of which have a vertex in common. On the flip side I have, together with my advisor Petter Brändén, constructed obstructions to stronger (algebraic) versions of the Generalized Lax Conjecture.

Back to top

Let \(h(\mathbf{z})\) be a hyperbolic polynomial with respect to \(e \in \mathbb{R}^n\). In analogy with the rank of a matrix, one defines the (hyperbolic) rank of \(\mathbf{x} \in \mathbb{R}^n\) by $$ \text{rk}(\mathbf{x}) = \text{#non-zero eigenvalues of } \mathbf{x}. $$ The connection between hyperbolic polynomials and matroids was noted by Gurvits: \begin{align*} &\text{Let } \nu = (\mathbf{v}_1,\dots, \mathbf{v}_n) \text{ be a tuple of rank one vectors in a hyperbolicity cone } \Lambda_+(h, \mathbf{e}).\\ &\text{Define a function } r_{\nu}:2^{[m]} \to \mathbb{N}, \text{ by } r_{\nu}(S) = \text{rk}\left(\sum_{i\in S} \mathbf{v}_i \right ).\\ &\text{Then } r_{\nu} \text{ is the rank function of a matroid.} \end{align*} In 2006 Helton and Vinnikov made a breakthrough by proving the Lax conjecture, which asserted that all hyperbolic polynomials \(h(x,y,z)\) with respect to \(\mathbf{e} \in \mathbb{R}^3\) have a definite determinantal representation, that is, $$ h(x,y,z) = \det(xA+yB+zC) $$ for some real symmetric matrices \(A,B,C\) such that \(Ae_1+Be_2+Ce_3 \) is positive definite. The conjecture cannot hold for hyperbolic polyomials in more than three variables. This can easily be verified by a count of parameters.

For hyperbolic polynomials in more than three variables Helton and Vinnikov conjectured that \(h(\mathbf{z})^N\) has a definite determinantal representation for some positive integer \(N\). An unexpected counterexample to this conjecture was however produced by Brändén via considering the bases generating polynomial of a certain non-representable hyperbolic matroid (the Vámos matroid).

Other than the Vámos matroid and a certain generalization of it, no other matroids were previously known to be both non-representable and hyperbolic - two essential properties in the counterexample to the conjecture by Helton and Vinnikov. In particular it was unknown whether this class of matroids is infinite. In joint work with Brändén we constructed an infinite family of non-representable hyperbolic matroids parametrized by graphs. Along the way we prove several interesting symmetric function inequalities generalizing and strengthening for instance the Laguerre-Túran inequality and an inequality due to Jensen.

The figure: The top-left figure on the front page depicts a simple graph together with its corresponding hyperbolic matroid in our family. The matroid is non-representable since it contains the Vámos matroid as a minor.

Back to top

The real-rootedness of the matching polynomial of a graph \(G\), $$ \mu_G(x) = \sum_{i=0}^{\lfloor n/2 \rfloor} m_i x^{i} $$ where \(m_i\) denotes the number of matchings of size \(i\) in \(G\), is a well known result in algebraic graph theory. Hall, Puder and Sawin recently introduced the notion of the \(d\)-matching polynomial in order to prove the existence of infinite families of bipartite Ramanujan \(d\)-coverings, generalizing seminal work of Marcus, Spielman and Srivastava for the case \(d=2\).

Consider a labeling of the edges of \(G\) by permutations in \(S_d\). A \(d\)-covering \(H\) of a graph \(G\) can be constructed via such a labeling by replacing each edge in \(G\) with the perfect matching induced by the permutation.

The figure: The top-right figure on the front page depicts a graph \(G\) labeled by permutations \((\sigma_1,\sigma_2, \sigma_3,\sigma_4,\sigma_5) = ((1 \hspace{0.1cm} 2),(1 \hspace{0.1cm} 2)(3 \hspace{0.1cm} 4),(1 \hspace{0.1cm} 3 \hspace{0.1cm} 2), (1 \hspace{0.1cm} 2 \hspace{0.1cm} 3 \hspace{0.1cm} 4), (1 \hspace{0.1cm} 2 \hspace{0.1cm} 3)) \) and its corresponding \(4\)-covering \(H\).

The \(d\)-matching polynomial of a graph \(G\) is defined as the average matching polynomial over all \(d\)-coverings \(H\) of \(G\), that is, $$ \mu_{G,d}(x) = \mathbb{E}_H \mu_H(x). $$ Hall, Puder and Sawin prove that \(\mu_{G,d}(x)\) is real-rooted for all loopless connected graphs \(G\). The authors asked for a more direct proof and conjectured that their result ought to hold even for graphs containing loops.

In my research I give a direct proof of the real-rootedness of \(\mu_{G,d}(x)\) and also remove the redundant hypothesis of loop-freeness. In fact I deduce real-rootedness by proving something stronger. A polynomial \(P(\mathbf{z}) \in \mathbb{C}[z_1,\dots, z_n]\) is said to be stable if \(P(z_1,\dots, z_n) \neq 0\) whenever \(\text{Im}(z_i) > 0\) for all \(i = 1,\dots, n\). I prove that $$ \mu_{G,d}(\mathbf{z}) = \mathbb{E}_{H} \mu_H(\mathbf{z}) $$ is stable for any graph \(G\) where $$ \mu_G(\mathbf{z}) = \sum_{M} (-1)^{|M|} \prod_{i \in [n] \setminus V(M)} z_i. $$ is the multivariate matching polynomial. Since real stable univariate polynomials are the same as real-rooted polynomials, the real-rootedness of \(\mu_{G,d}(x)\) can be deduced by setting \(\mathbf{z} = (x,\dots, x)\).

Back to top

Although the matching polynomial of a graph \(G\) is real-rooted due to a classical result by Heilmann and Lieb, the same is not necessarily true for hypergraphs. In my research I consider a relaxation of the notion of matchings in hypergraphs. This notion give rise to a weighted polynomial which is real-rooted over such matchings. For graphs this new polynomial reduces to the ordinary matching polynomial, thus providing a hypergraphic generalization to the Heilmann-Lieb theorem.

Define a "team" to be a group of at least two people. Consider the problem of assigning a subset of \(n\) people with prescribed competencies into teams working on a subset of \(m\) different projects in such a way that no person is assigned to more than one project and each person has the competency to work on the project they are assigned to. We shall call such team assignments "relaxed matchings".

More formally, define a relxed matching in a hypergraph \(H = (V(H),E(H))\) to be a collection \(M = (S_e)_{e \in E}\) of edge subsets such that \(E \subseteq E(H)\), \(S_e \subseteq e\), \(|S_e| > 1\) and \(S_e \cap S_{e'} = \emptyset\) for all pairwise distinct edges \(e,e' \in E\).

The figure: The bottom-right figure on the front page depicts a relaxed matching \(M = (S_{e_1}, S_{e_3}, S_{e_4})\) in a hypergraph \(H\) with \(S_{e_1} = \{1,2\}\), \(S_{e_3} = \{4,5\}\), \(S_{e_4} =\{6,7,8\}\).

Back to top

A permutation \(\sigma \in S_n\) is said contain an occurrence of the classical pattern \(\pi \in S_m\), \(m \leq n\) if there exists a subsequence in \(\sigma\) whose letters are in the same relative order as those in \(\pi\) i.e. there exists \(i_{\pi(1)} \lt i_{\pi(2)} \lt \cdots \lt i_{\pi(m)}\) such that \(\sigma(i_1) \lt \sigma(i_2) \cdots \lt \sigma(i_m) \). Otherwise \(\sigma\) is said to avoid the pattern \(\pi\).

Example: The permutation \(\sigma = 241563 \in S_6\) has four occurrences of the pattern \(\pi = 231 \in S_3\) given by the subsequences \(241, 453, 463\) and \(563\) in \(\sigma\). On the other hand \(\sigma\) avoids the pattern \(321\).

If \(\pi\) is a pattern, then we denote by \(S_n(\pi)\) the class of patterns in \(S_n\) avoiding \(\pi\). All permutation classes avoiding a classical pattern of length three are enumerated by the Catalan numbers.

The figure: The bottom-left figure on the front page depicts bijections from \(S_n(321)\) to two other objects in the Catalan zoo, namely Dyck paths and (shortened) polyominoes.

Vincular patterns were introduced by Babson and Steíngrimsson in 2000 as a generalization to classical patterns. Vincular patterns are similar to classical patterns except that they also allow for expressing adjacency restrictions. All vincular patterns give rise to a permutation statistic counting the number of occurrences of the pattern in a given permutation. Babson and Steíngrimsson classified all conic combinations of vincular pattern-statistics of length at most three giving rise Mahonian statistics, i.e., statistics that have the same distribution as the inversion statistic on permutations. Many familiar Mahonian statistics are covered by the classification, including the inversion statistic and the major index statistic.

In my research I study equidistributions between the statistics in Babson-Steíngrimsson's classification over permutation classes avoiding a classical pattern of length three. This study is carried out using a variety of techniques ranging from direct bijective arguments to the use of generating functions and intermediate Catalan objects.

Back to top

The cyclic sieving phenomenon (CSP) was introduced by Reiner, Stanton and White in 2004 and consists of three pieces of data, a set \(X\), a cyclic action of \(C_n = \langle \sigma_n\rangle \) on \(X\) and a polynomial \(f(q)\). The phenomenon is said to be exhibited when the number of fixed points under the action of \(\sigma_n^j\) coincides with the root of unity evaluations \(f(\omega_n^j)\) for each \(j = 1,\dots, n\). Here \(\omega_n\) denotes a primitive \(n\)th root of unity.

Given an action of \(C_n = \langle \sigma_n\rangle \) on a set \(X\) one can always find a canonical polynomial, namely $$ f(q) = \sum_{\mathcal{O} \in \text{Orb}_{C_n}(X)} \frac{q^n-1}{q^{n/|\mathcal{O}|}-1} $$ completing the action to a CSP. Thus one would generally consider a CSP "interesting" if the polynomial \(f(q)\) is intrinsically related to the combinatorial set \(X\) on which \(C_n\) acts. This happens if e.g. $$ f(q) = \sum_{x \in X} q^{\text{stat}(x)} $$ for some combinatorial statistic \(\text{stat}:X \to \mathbb{N}\). There is no a priori reason why such a combinatorial statistic should exist, but interesting CSPs are widespread in combinatorics as witnessed by the growing literature on the topic.

In my joint research with Per Alexandersson we provide a new perspective on the phenomenon. Although a cyclic action always give rise to a (generally uninteresting) CSP polynomial \(f(q)\), the converse question is not equally trivial - Given a combinatorial polynomial \(f(q)\) generated by a natural statistic on \(X\), when can we find a (not necessarily combinatorial) cyclic action complementing it to a CSP? We give a necessary and sufficient condition for the existence of such an action.

The figure: The middle-left figure on the front page depicts an orbit in the set of standard Young tableaux of shape \(\lambda = (4,2) \) under the cyclic action of jeu-de-taquin promotion. For tableaux of rectangular shape \(\lambda = (n^m)\), Rhoades showed that Stanley's \(q\)-hook-length formula: $$ \frac{[n]_q!}{\prod_{(i,j)\in \lambda} [h_{i,j}]_q!} = q^{-n\binom{m}{2}} \sum_{T \in \text{STY}(\lambda)} q^{\text{maj}(T)} $$ is the natural combinatorial polynomial complementing promotion to a CSP. Is there a natural combinatorial polynomial complementing promotion for other shapes?

Back to top

Contact

Email
namini[at]kth.se
Phone
+46 8 790 66 85
Homepage
people.kth.se/~namini

Old Homepage
Address
Department of Mathematics
Royal Institute of Technology (KTH)
S-100 44 Stockholm, Sweden