% !TeX program = pdfLaTeX
%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{38}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{bm}
\usepackage{braket}
\usepackage{tikz-cd}

\newcommand{\C}{\mathbb{C}}
\newcommand{\Cstar}{\C^*}
\newcommand{\F}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\calB}{\mathcal{B}}

\newcommand{\gerg}{\mathfrak{g}}
\newcommand{\gergl}{\mathfrak{gl}}

\newcommand\rank{\mathop{\mathrm{rank}}\nolimits}
\newcommand{\tr}{\operatorname{tr}}
\newcommand\Ann{\mathop{\mathrm{Ann}}\nolimits}
\newcommand\Hom{\mathop{\mathrm{Hom}}\nolimits}
\newcommand\Ker{\mathop{\mathrm{Ker}}\nolimits}
\newcommand{\Sym}{\operatorname{Sym}}

\newcommand{\fr}{}
\def\fr<#1/#2>{\frac{#1} {#2}}

\theoremstyle{plain} 
\newtheorem{thm}{Theorem}[section]
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{conjecture}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{obs}[thm]{Key Observation}
\newtheorem{remark}[thm]{Remark}
\newtheorem{example}[thm]{Example}



%% define your title in the usual way
\title[Strict log-concavity of the Kirchhoff polynomial and its applications]{Strict log-concavity of the Kirchhoff polynomial and its applications}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Takahiro Nagaoka and Akiko Yazawa]{Takahiro Nagaoka\thanks{\href{mailto:tnagaoka@math.kyoto-u.ac.jp}{tnagaoka@math.kyoto-u.ac.jp}. Supported by Grant-in-Aid for JSPS Fellows 19J11207. 
}\addressmark{1}
\and Akiko Yazawa\thanks{\href{mailto:yazawa@math.shinshu-u.ac.jp}{yazawa@math.shinshu-u.ac.jp}.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}
	Department of Mathematics,
	Graduate School of Science,
	Kyoto University,
	Kyoto, Japan
\\ 
\addressmark{2}
	Department of Science and Technology,
	Graduate School of Medicine, Science and Technology,
	Shinshu University, Nagano, Japan
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
Anari, Gharan, and Vinzant showed that the basis generating functions for all matroids are log-concave. 
In this paper, we show that Kirchhoff polynomials, i.e. the basis generating functions for simple graphic matroids, are strictly log-concave. 
Our key observation is that the Kirchhoff polynomial of a complete graph can be seen as the irreducible relative invariant of a certain prehomogeneous vector space. 
Furthermore, we prove that an algebra associated to a graphic matroid satisfies the strong Lefschetz property and  Hodge--Riemann bilinear relation at degree one. 
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{the complete graph, graphic matroids, Artinian Gorenstein algebras, the strong Lefshcetz property, Hodge--Riemann relation, prehomogeneous vector spaces}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\addbibresource{mrbib.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}\label{sec:Intro}
Recently, in \cite{MR3899575}, Anari, Gharan, and Vinzant showed that, for any matroid $M$, the basis generating function $F_M$
satisfies log-concavity (more precisely, complete log-concavity) on $\R_{\geq0}^n$. 
In other words, $\log F_M$ 
is concave on $\R^n_{\geq0}$, 
that is the Hessian matrix $H_{F_M}$ 
and the gradient vector $\nabla F_M$ 
of $F_M$ satisfy 
\begin{equation*}%\tag{*}
\left.\left(-F_MH_{F_M}+(\nabla F_M)^\top\nabla F_M\right)\right|_{\bm{x}=\bm{a}} \ \text{is positive semidefinite} 
\end{equation*} 
for any $\bm{a}\in\R_{\geq0}^n$. 

The basis generating functions for graphic matroids are called Kirchhoff polynomials. 
In our main theorem, we show that, the Kirchhoff polynomial $F_\Gamma$ 
is strictly log-concave on $(\R_{>0})^n$ 
for any simple graph $\Gamma$ 
with  $n$ edges. 
In other words, for any $\bm{a}\in(\R_{>0})^n$, 
$\log F_\Gamma$ 
is strictly concave at $\bm{a}$. 
In particular, the Hessian matrix $H_{F_\Gamma}|_{\bm{x}=\bm{a}}$ 
is non-degenerate with $n-1$ negative eigenvalues and one positive eigenvalue (see \cref{mainresult}). 

Our main theorem is proved in two steps. 
First, we reduce our claim to the following determinantal identity of the Hessian of the Kirchhoff polynomial $F_{K_{r+1}}$ of complete graphs $K_{r+1}$ (cf.\ \cref{maintheorem2}):
\begin{equation*}%\tag{**}
\det H_{F_{K_{r+1}}}=(-1)^{n-1}c_r(F_{K_{r+1}})^{n-r-1},
\end{equation*}
where $c_r>0$
is a constant, and $n:=\binom{r+1}{2}$. 
Second, we show the above equality not through direct computation, but rather by identifying $F_{K_{r+1}}$ 
with the unique irreducible polynomial associated to a special $GL_r(\C)$ representation 
or the so-called prehomogeneous vector space. 
Then, based on the general theory of prehomogeneous vector spaces \cite{MR0430336}, 
the Hessian $\det H_F$ 
of the relative invariant $F$ is also a relative invariant of the same representation.  
Hence it follows from the uniqueness of the relative invariant that 
\[\exists c \in \C \ \text{such that} \ \det H_F=cF^m. \]

We also apply the main theorem to the strong Lefschetz property and the Hodge--Riemann bilinear relation of the graded Artinian Gorenstein algebra $R_\Gamma^*=\bigoplus_{\ell=0}^r{R_\Gamma^\ell}=\R[x_1, \ldots, x_n]/\Ann(F_\Gamma)$ 
associated to any simple graph $\Gamma$. 
This algebra is defined for any matroid $M$ by Maeno and Numata. 
They conjectured that $R^*_M$ 
has the strong Lefschetz property for any matroid $M$ 
in an extended abstract \cite{MR2985388} of the paper \cite{MR3566530}. 
As an application of our main theorem, we prove that this conjecture at degree one when $M$ is a graphic matroid. 
Since the Hodge--Riemann bilinear form of $R^1_\Gamma$ 
is given by the Hessian $H_{F_\Gamma}$, we show that the Hodge--Riemann relation holds at degree one (see \cref{appthm}). 

This paper is organized as follows. In \cref{Preliminaries}, 
we introduce some concepts to give our main theorem. 
In \cref{sec:Main result}, 
we define the Kirchhoff polynomials of simple graphs, and then prove our main result. 
In the last half of this section, 
we see that the connection between the Kirchhoff polynomials of complete graphs and certain prehomogeneous vector spaces. 
Finally, in \cref{sec:Applications}, 
we conclude that our main result applies to algebras associated to graphic matroids. 

This article is a research announcement or extended abstract for the paper \cite{NY}. 
We omit proofs and details that can be found in the main paper. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Preliminaries}\label{Preliminaries}

In this section, 
we introduce some concepts that will be useful for our main theorem. 
In \cref{Strict log-concavity and Hessian}, 
we define the strict log-concavity of a homogeneous polynomial. 
Then, we recall a relationship between strict log-concavity and the Hessian of the polynomial. 
Next, in \cref{Prehomogeneous vector spaces}, we introduce prehomogeneous vector spaces  as a way of computing the Hessian. 
Finally, in \cref{Matroids}, we introduce the matroids, which are the main objects of our theorem.   

\subsection{Strict log-concavity and Hessians}\label{Strict log-concavity and Hessian}

Let $F$ 
be a homogeneous polynomial of degree $r$ 
in $n$ 
variables with real coefficients, where $r\geq3$. 
For $F$, $H_{F}$ 
denotes the Hessian matrix of $F$, 
and $\nabla F$ 
denotes the gradient vector of $F$. 
We call $\det H_{F}$ 
the Hessian of $F$. 

\begin{definition}[Strictly log-concave/log-concave]
We say that $F$ 
is \emph{log-concave} (\emph{resp. strict\-ly log-concave}) at $\bm{a}\in\R^n$ if 
\[(-FH_F+(\nabla F)^\top\nabla F)|_{\bm{x}=\bm{a}} \]
is positive semidefinite (\emph{resp.\ }positive definite). 
\end{definition}

The relation between strict log-concavity and the Hessian can be seen as follows.   

\begin{remark}\label{remark}
By easy arguments, we obtain 
\begin{align*}\label{The Hessian of a homogeneous polynomial}
\det\left(-FH_{F}+(\nabla F)^{\top}\nabla F\right)=(-1)^{n-1}\frac{1}{r-1}F^n\det H_F. 
\end{align*}
Therefore $F$ 
is strictly log-concave at $\bm{a}$ if and only if 
$F(\bm{a})\neq 0$, $\det H_{F}\big|_{\bm{x}=\bm{a}}\neq 0$, 
and $F$ 
is log-concave at $\bm{a}$.  
\end{remark}


We assume that $F$ is a polynomial with positive coefficients. 
Then $\tr H_{F}\geq 0$.  
If $F$ is strictly log-concave, 
then its Hessian is non-degenerate.
It follows from Cauchy's interlacing theorem that
its Hessian has only one positive eigenvalue. 

\begin{thm}[Cauchy's interlacing theorem {\cite[Corollary 4.3.9]{MR2978290}}]\label{thm:Cauchy}
For a real symmetric $n\times n$ matrix $A$ 
with eigenvalues $\alpha_1\geq\cdots\geq\alpha_n$, 
a vector $\bm{v}\in\R^n$, 
and the eigenvalues $\beta_1\geq\cdots\geq\beta_n$ 
of $-A+\bm{v}^{\top}\bm{v}$, 
they satisfy  
\[\beta_1\geq-\alpha_n\geq\beta_2\geq\cdots\geq-\alpha_{2}\geq\beta_n\geq-\alpha_1.\] 
\end{thm}

\begin{corollary}\label{cor:eigen}
If $F$ 
is strictly log-concave at $\bm{a}\in(\R_{>0})^n$, 
then $H_F\big|_{\bm{x}=\bm{a}}$ 
has exactly $n-1$ negative eigenvalues and exactly one positive eigenvalue. 
In particular, 
\begin{align*}
(-1)^{n-1}(\det H_F)|_{\bm{x}=\bm{a}}>0. 
\end{align*}
\end{corollary}

A \emph{multi-affine polynomial} is a linear combination of square-free monomials. 
The following is used for our main theorem: 

\begin{lemma}\label{cor:van}
Let $F\in\R[x_1, \ldots, x_n]$ 
be a multi-affine homogeneous polynomial of $\deg F=r\geq3$ with positive coefficients. 
For a subset $I$ 
of $[n]$ 
and $0\leq k \leq n$, we define
\begin{align*}
C^{n-k}_{I>0}=\Set{(z_{k+1}, \ldots, z_n)\in\R^{n-k}_{\geq0} \ |  \ z_j\geq0 \ (j\notin I), \ z_i>0 \ (i\in I)}. 
\end{align*}
We assume that $F$ 
is strictly log-concave on $C^n_{I>0}$. 
If  
\begin{align*}
\fr<\partial F/\partial x_{1}>\not\equiv0, \fr<\partial F|_{x_{1}=0}/\partial x_{2}>\not\equiv0, \ldots ,\fr<\partial F|_{x_{1}=\cdots=x_{{k-1}}=0}/\partial x_{k}>\not\equiv0
\end{align*}
holds for some $0\leq k\leq n-r$, 
then $F|_{x_{1}=\cdots=x_{k}=0}\in\R[x_{k+1}, \ldots, x_n]$ 
is strictly log-concave on $C^{n-k}_{I>0}$. 
\end{lemma}

%%%%%%%%%%%
\subsection{Prehomogeneous vector spaces}\label{Prehomogeneous vector spaces}
For a special polynomial, we have the following identity:  
\begin{align*}\label{The Hessian in the case of the relative invariant}
\det H_{F}=cF^{\frac{n(r-2)}{r}}, 
\end{align*}
where $c$ is non-zero (see \cref{cor:reg}). 
To prove this identity, 
we introduce the concept of prehomogeneous vector spaces (cf. \cite{MR0430336}). 

Let $(G, \rho ,V)$ be a triplet of 
a connected linear algebraic group $G$,  
a finite dimensional vector space $V$, 
and a rational representation $\rho$ 
of $G$ 
on $V$, 
all defined over $\C$.  
We call $(G, \rho, V)$ a \emph{prehomogeneous vector space} 
if there exists an algebraic $G$-invariant 
proper subset $S\subset V$ 
such that $V\setminus S$ is a single open dence  $G$-orbit. 
Then, we say that $S$ 
is the \emph{singular set} of $(G, \rho, V)$, 
and that $(G, \rho, V)$ 
is \emph{irreducible} when $\rho$ is an irreducible representation. 

Let $(G, \rho ,V)$ be a prehomogeneous vector space.
A not identically zero rational function $F\in\C(V)$ 
is called a \emph{relative invariant (with respect to $\chi$) 
of $(G, \rho ,V)$} 
if there exists a rational character $\chi \in \Hom(G, \Cstar)$ which satisfies the following:  
\[F(\rho(g)\bm{x})=\chi(g)F(\bm{x}) \ \ \ (g\in G, \bm{x}\in V).\]
If $F$ 
is a relative invariant  corresponding to some character $\chi$, 
then $\det H_F$ 
is a relative invariant corresponding to the character $\chi^N\cdot (\det)^{-2}$, where $N=\dim V$ and $\det : G\to\Cstar : g\mapsto\det(\rho(g))$. 

The following is a fundamental proposition. 

\begin{proposition}[cf.\ {\cite[Proposition 12 in Section 4]{MR0430336}}]\label{prop:therelative}
Let $(G, \rho, V)$ be an irreducible prehomogeneous vector space. 
Then, there is at most one irreducible relative invariant polynomial $F$ up to constant multiple. 
In particular, any  relative invariant has the form $cF^m$ 
for $c\in\C$ 
and $m\in\Z$. 
\end{proposition}

We say that a prehomogeneous vector space $(G, \rho ,V)$ 
is \emph{regular} if there exists a relative invariant $F\in\C(V)$ 
such that its Hessian $\det H_F$ 
is not identically zero on $V$. 
Then, we have the following key identity of the Hessian of the relative invariant when $(G, \rho, V)$ is regular. 

\begin{corollary}\label{cor:reg}
Let $(G, \rho, V)$ 
be a regular {irreducible} prehomogeneous vector space of dimension $n$. 
If the degree of the relative invariant $F$ 
is $r$, 
then, there exists a constant $c\in\Cstar$ such that 
\[\det H_F=cF^{\fr<n(r-2)/r>}. \]
\end{corollary}


%%%%%%%%%%%
\subsection{Matroids}\label{Matroids}

Here, we provide the basic terms of a matroid. 
A \emph{matroid} $M$ 
is a pair $(E, \calB)$ 
of a finite set $E$ 
and a nonempty collection $\calB$ 
of subsets of $E$ satisfying the so-called basis exchange axioms: 
If $B_1$ 
and $B_2$ 
are in $\calB$ 
and $x\in B_1\setminus B_2$, 
then there is an element $y\in B_2\setminus B_1$ 
such that $\{y\}\cup(B_1\setminus\{x\})\in\calB$. 
See \cite{MR2849819} for details.  
In this case, we call each $B\in\calB$ a \emph{basis} 
of $M$, and 
each subset of a basis of $M$ 
an \textit{independent set} of $M$. 
We call $e\in E$ a \emph{loop} (\emph{resp.\ }\emph{coloop}) if 
every basis does not contain $e$ 
(\emph{resp.\ }every basis contains $e$). 
We say that a matroid $M$ is \textit{simple} 
if every subset of $E$ with cardinality less than or equal to two is independent. 


\begin{example}[Graphic matroid]\label{Graphic matroid}
For any finite connected graph $\Gamma=(V, E)$ 
with the vertex set $V$ 
and the edge set $E$, 
we call a subgraph $T\subseteq \Gamma$ 
a \emph{spanning tree} in $\Gamma$ 
if $T$ 
does not contain any cycles and $T$ 
passes through all vertices of $\Gamma$. 
Let $\calB_\Gamma$ 
be the set of all spanning trees in $\Gamma$. 
Then $M(\Gamma)=(E, \calB_\Gamma)$ is a matroid. 
These matroids are called \emph{graphic matroids}.  

Note that if $M$ 
is a graphic matroid, then there exists a connected graph $\Gamma$ 
such that $M(\Gamma)$ 
is isomorphic to $M$.  
\end{example}

\begin{example}[Submatroid]
Let $M=(E, \calB)$ be a matroid. 
For $E'\subset E$, 
we define $\calB'$ 
by $\calB'=\Set{B\in\calB|B\subset E'}$. 
Then $M'=(E', \calB')$ is a matroid. 
We call $M'$ a submatroid of $M$. 
\end{example}

\begin{definition}[Basis generating function]\label{def:basispoly}
For any matroid $M=(E, \calB)$, 
we define the \emph{basis generating function} $F_M(\bm{x})$ 
of $M$ by 
\[F_M(\bm{x})=\sum_{B\in\calB}{\prod_{i\in B}{x_i}}.\]
\end{definition}

\begin{example}[Kirchhoff polynomial]\label{Kirchhoff polynomial}
The basis generating function $F_{M(\Gamma)}$ for a graphic matroid $M(\Gamma)$ 
is called the Kirchhoff polynomial of $\Gamma$. 
In this case, we write $F_{\Gamma}=F_{M(\Gamma)}$.  
\end{example}

By basis exchange axioms, if $B$ 
and $B'$ 
are bases of $M$, 
then $|B|=|B'|$. 
We say that a matroid $M$ 
has \textit{rank} $r$ 
if the number of elements of a basis of $M$ is $r$.  
%The rank of $M$ is denoted by $\rank M$. 
For a matroid $M=(E, \calB)$ of rank $r$, 
its basis generating function $F_M(\bm{x})$ 
is a multi-affine homogeneous polynomial of degree $r$ in $|E|$ variables with coefficients equal to one. 
Hence, we have 
\begin{align*}
F_{M}(\bm{x})=F_{M}(\bm{x})\big|_{x_{e}=0}+x_{e}\frac{\partial}{\partial x_{e}}F_{M}(\bm{x}). 
\end{align*}
Moreover
\begin{align*}
F_{M}(\bm{x})\big|_{x_{e}=0}&=
\begin{cases}
0 & \text{if $e$ is a coloop}, \\
F_{M\setminus e}(\bm{x}) & \text{otherwise}, 
\end{cases}\\
\frac{\partial}{\partial x_{e}}F_{M}(\bm{x})&=
\begin{cases}
0 & \text{if $e$ is a loop}, \\
F_{M/e}(\bm{x}) & \text{otherwise},  
\end{cases}
\end{align*}
where $M\setminus e$ ($M/e$) 
is the deletion (contraction) of $M$ 
with respect to $e$. 
Hence, for any $e\in E$ that is not a loop or a coloop, we have 
\[F_M(\bm{x})=F_{M\setminus e}(\bm{x})+x_eF_{M/e}(\bm{x}). \]
Let $B\in \calB$. 
Every element $e\in E\setminus B$ is not a coloop.  
Hence, for the matroid $M_0$ 
obtained by deleting some elements $e_1, \ldots, e_k\in E\setminus B$ from $M$, 
we have 
\begin{align*}
F_{M_0}=F_M|_{x_{e_1}=\cdots=x_{e_k}=0}. 
\end{align*}

\begin{example}\label{subKir}
Every Kirchhoff polynomial is obtained from the Kirchhoff polynomial of the complete graph with the same number vertices by substituting zero for some variables. 
In other words, every simple graphic matroid is a submatroid of the simple graphic matroid of the complete graph. 
\end{example}

Note that, for any matroid $M$ on $[n]=\Set{1,2, \ldots, n}$, 
log-concavity of $F_M(\bm{x})$ on $\R_{\geq0}^n$ is already known in \cite[Theorem 4.2]{MR3899575}. 

\begin{thm}[{\cite[Theorem 4.2]{MR3899575}}]\label{thm:AGVs}
For any matroid $M$, $F_M(\bm{x})$ 
is log-concave on $\R^n_{\geq0}$. 
\end{thm}

If $M$ is not simple, 
then $\det (-F_MH_{F_M}+(\nabla F_M)^T(\nabla F_M))$ 
is identically zero, in particular, it cannot be positive definite at any point in $\R^n$. See \cite{NY} for more details. 

Below, we prepare some lemmas for our main theorem. 

\begin{lemma}\label{lem:star}
Let $M$ 
be a matroid on $E$. 
Fix a basis $B\in\calB$ of $M$. 
For $S=\Set{j_1, \ldots ,j_k}\subset E\setminus B$, 
and $j\in E\setminus(B\cup S)$, 
\begin{equation}\label{partial differentiation of the basis generating function for a matroid which is obtained from deletion}
\fr<\partial F_{M}|_{x_{j_1}=\cdots=x_{j_{k}}=0}/\partial x_{j}>=F_{(M\setminus S)/j}\neq0
\end{equation}
if $j$ is not a loop. 
\end{lemma}

Since the basis generating function $F_M(\bm{x})$ 
of any simple matroid $M$ satisfies the condition \eqref{partial differentiation of the basis generating function for a matroid which is obtained from deletion} by \cref{cor:van,lem:star}, we have the following. 

\begin{lemma}\label{cor:matroidver}
Let $M$ 
be a simple matroid on $[n]$ 
of rank $r\geq3$. 
For any basis $B$, 
we assume that $F_M$ 
is strictly log-concave on $C_{B>0}^n$, %$(\supset(\R_{>0})^n)$.
where $C_{B>0}^n$ is the same as \cref{cor:van}. 
Then for any submatroid $M_0:=M\setminus\{j_1, \ldots, j_k\}$ of rank $r$, $F_{M_0}$ 
is strictly log-concave on $C_{B_0>0}^{n-k}$ %$(\supset(\R_{>0})^{n-k})$ 
for any basis $B_0$ of $M_0$. 
\end{lemma}

Let $\Gamma=(V, E)$ be a simple graph with $|E|=n$. 
For a spanning tree $T$, we define
\begin{align*}
C^n_{T>0}=\Set{\bm{a}\in\R^n_{\geq0} \ | \ z_i>0 \ (i\in T), \ z_j\geq0 \ (j\notin T)} \ (\supset(\R_{>0})^n). 
\end{align*}
Then we can find the following corollary to \cref{cor:matroidver}.  

\begin{corollary}\label{maintheorem1}
Let $\Gamma=(V, E)$ 
be a simple connected graph with $|V|=r+1\geq3$ and $|E|=n\geq3$. 
For each spanning tree $T$ 
in $\Gamma$, 
we assume that $F_\Gamma$ 
is strictly log-concave on $C^n_{T>0} \ (\supset(\R_{>0})^n)$. 
Then for any connected subgraph $\Gamma'=(V', E')$ 
with $|V'|=r+1$ 
and $|E'|=n-k$, $F_{\Gamma'}$ 
is strictly log-concave on $C_{T'>0}^{n-k} \ (\supset(\R_{>0})^{n-k})$ 
for any spanning tree $T'$ in $\Gamma'$. 
\end{corollary}


%%%%%%%%
\section{Main result}\label{sec:Main result}

In this section, we will prove our main result that the Kirchhoff polynomial of each simple graph is strictly log-concave on $\R^{n}_{>0}$ (see \cref{mainresult}). 

\subsection{Main result}

First, we consider the Kirchhoff polynomial of the complete graph. 
As stated in \cref{Prehomogeneous vector spaces},  
for the relative invariant of an irreducible prehomogeneous vector space, 
its Hessian has the form $cF^{m}$. 
We can show that the Kirchhoff polynomial of the complete graph can be realized as the relative invariant. 
We will prove \cref{maintheorem2} in \cref{proofpart}. 

\begin{thm}\label{maintheorem2}
Let $n=\binom{r+1}{2}$. 
We have 
\[\det H_{F_{K_{r+1}}}=(-1)^{n-1}c_r(F_{K_{r+1}})^{n-r-1}, \]
where $c_{r}=2^{n-r}(r-1)$. 
\end{thm}

The Kirchhoff polynomial is the basis generating function for a graphic matroid by \cref{Kirchhoff polynomial}.  
By \cref{thm:AGVs}, 
we know that the Kirchhoff polynomial is log-concave. 
Note that $F_{\Gamma}(\bm{x})>0$ 
on $C^n_{T>0}$ 
for each spanning tree $T$. 
Based on \cref{remark}, 
the Kirchhoff polynomial is strictly log-concave on $C^n_{T>0}$ 
if and only if its Hessian does not vanish on $C^n_{T>0}$. 
Hence \cref{maintheorem2} tells us that, for any spanning tree $T$, 
the Kirchhoff polynomial of the complete graph is strictly log-concave on $C_{T>0}^n$.  
By \cref{subKir} and \cref{maintheorem1}, we obtain the following. 

\begin{thm}[Main result]\label{mainresult}
For any simple connected graph $\Gamma=(V, E)$ 
with $|V|=r+1\geq3$ 
and $|E|=n\geq3$, 
the Kirchhoff polynomial $F_\Gamma(\bm{x})$ 
is strictly log-concave on $(\R_{>0})^n$. 
In other words, 
\[(-F_\Gamma H_{F_\Gamma}+(\nabla F_{\Gamma})^T\nabla F_\Gamma)|_{\bm{x}=\bm{a}}\] 
is positive definite at any $\bm{a}\in(\R_{>0})^n$. 
In particular, $H_{F_\Gamma}|_{\bm{x}=\bm{a}}$ 
is non-degenerate, with $n-1$ negative eigenvalues and exactly one positive eigenvalue. 
Thus, 
\begin{align*}
(-1)^{n-1}(\det H_{F_\Gamma})|_{\bm{x}=\bm{a}}>0. 
\end{align*}
Moreover, for each spanning tree $T$ in $\Gamma$, $F_\Gamma$ 
is strictly log-concave on $C^n_{T>0} \ (\supset(\R_{>0})^n)$. 
\end{thm}


%%%%%%%%%%%
\subsection{Proof of \cref{maintheorem2}}\label{proofpart}

Here we study the Kirchhoff polynomials more precisely, and give a proof of \cref{maintheorem2}. 

We see that the Kirchhoff polynomial is realized as the determinant of some matrix. 
This is called the matrix-tree theorem (cf. \cite[Theorem VI.29]{MR1813436}):
Let $E_{ij}$ 
be the $r\times r$ matrix such that the $(i, j)$-component is one and the others are zero. 
For a graph $\Gamma=(V, E)$ 
with $|V|=r$, 
we associate a variable $x_e$ 
to each edge $e\in E$, 
and define the \emph{Laplacian $L_{\Gamma}$ of $\Gamma$} indexed by vertices as 
\[L_\Gamma=\sum_{e=\{i, j\}\in E}{x_e(E_{ii}-E_{ij}-E_{ji}+E_{jj})}.\]
Then the Kirchhoff polynomial $F_\Gamma$ 
is equal to any cofactor of its Laplacian $L_\Gamma$. 
In other words, for a graph $\Gamma=(V, E)$ 
and any $1\leq i, j\leq |V|$,  
\[F_\Gamma=(-1)^{i+j}\det (L_{\Gamma}^{(ij)}), \]
where $L_{\Gamma}^{(ij)}$ 
denotes the submatrix of $L_{\Gamma}$ 
obtained by removing the $i$th 
row and $j$th column. 

For a graph, we associate $x_{ij}=x_{ji}=x_e$ 
to each edge $e=\{i, j\}$. 
For the complete graph $K_{r+1}$, 
the entries in Laplacian $L_{K_{r+1}}=\left(\ell_{ij}\right)_{1\leq i, j\leq r+1}$ are
\[\ell_{ij}=
\begin{cases}
\left(\sum_{k=1}^{r+1}x_{ik}\right)-x_{ii}&(\text{if \ $i=j$}), \\
-x_{ij}&(\text{otherwise}). 
\end{cases}\]
One can see that $L_{K_{r+1}}^{(11)}$ 
is a symmetric matrix and $\{x_{ij}\}_{1\leq i<j\leq r+1}$ 
gives a coordinate of the vector space $\Sym(r, \C)$, 
which consists of all $r\times r$ 
symmetric matrices over $\C$. 

\begin{proposition}\label{rem:completegraph}
We have
\begin{align*}
\Set{L_{K_{r+1}}^{(11)} \bigr|_{\bm{x}=\bm{a}}|\bm{a}=(a_{ij})_{i<j}, a_{ij} \in\C}=\Sym(r, \C). 
\end{align*}
Therefore the Kirchhoff polynomial $F_{K_{r+1}}$ 
can be regarded as a function from $\Sym(r, \C)$ to $\C$. 
In other words, we can regard the Kirchhoff polynomial as the following function: 
\begin{align*}
F_{K_{r+1}}=\det: \Sym(r, \C)\to\C. 
\end{align*} 
\end{proposition}


\begin{example}\label{ex:laplacian}
{The Laplacian matrix $L_{K_{4}}$ of the complete graph $K_{4}$ is
\begin{align*}
L_{K_{4}}=
\begin{pmatrix}
x_{12}+x_{13}+x_{14}&-x_{12}&-x_{13}&-x_{14} \\
-x_{21}&x_{21}+x_{23}+x_{24}&-x_{23}&-x_{24} \\
-x_{31}&-x_{32}&x_{31}+x_{32}+x_{34}&-x_{34} \\
-x_{41}&-x_{42}&-x_{43}&x_{41}+x_{42}+x_{43} 
\end{pmatrix}. 
\end{align*}
The $(1,1)$ minor $L_{K_{4}}^{(11)}$ of $L_{K_{4}}$ is
\begin{align*}
L_{K_{4}}^{(11)}=
\begin{pmatrix}
x_{21}+x_{23}+x_{24}&-x_{23}&-x_{24} \\
-x_{32}&x_{31}+x_{32}+x_{34}&-x_{34} \\
-x_{42}&-x_{43}&x_{41}+x_{42}+x_{43} 
\end{pmatrix}. 
\end{align*}
Note that $L_{K_{4}}^{(11)}$ is a symmetric matrix and $\{x_{ij}\}_{1\leq i<j\leq r+1}$ 
gives a coordinate of $\Sym(3, \C)$. 
Hence we have
\begin{align*}
\Set{L_{K_{4}}^{(11)}\bigr|_{\bm{x}=\bm{a}}|\bm{a}=(a_{ij})_{i<j}, a_{ij} \in\C}=\Sym(3, \C). 
\end{align*}}
\end{example}

In \cite{MR0430336}, irreducible prehomogeneous vector spaces have already been classified. 
Here, we focus on the following prehomogeneous vector space, whose relative invariant is given by the Kirchhoff polynomial of the complete graphs.  
See \cite[Proposition 3 in Section 5]{MR0430336} or \cite[Section 7, I-(2)]{MR0430336} for details on \cref{KSSymtherelative}. 

\begin{proposition}[cf. \cite{MR0430336}]\label{KSSymtherelative}
Let $\rho$ 
be the representation of $GL_r(\C)$ on $\Sym(r, \C)$ such that
\[\rho(P)X=PXP^T \ \ (P\in GL_r(\C)).\]
Then $(GL_r(\C), \rho, Sym(r, \C))$ is a regular irreducible prehomogeneous vector space. 
Moreover, the relative invariant is given by $\det: \Sym(r, \C)\to\C$.   
\end{proposition}

As stated in \cref{rem:completegraph}, the Kirchhoff polynomial $F_{K_{r+1}}(\bm{x})$ 
of the complete graph $K_{r+1}$ is the relative invariant of the prehomogeneous vector space in \cref{KSSymtherelative}. 
Evaluation of $(\det H_{F_{K_{r+1}}})\bigr|_{\bm{x}=(1,1,\ldots,1)}$ was performed the second author \cite{Y2018}. 
Note that we used Cayley's theorem $F_{K_{r+1}}(1, 1, \ldots, 1)=(r+1)^{r-1}$ at the  second equality in \cref{yazawa} (see \cite[Theorem VI. 30]{MR1813436} for details). 


\begin{proposition}[{\cite[Theorem 3.3]{Y2018}}]\label{yazawa}
For the complete graph $K_{r+1}$, 
\begin{align*}
(\det H_{F_{K_{r+1}}})\bigr|_{\bm{x}=(1,1,\ldots,1)}&={(-1)}^{n-1}{2}^{n-(r+1)}(r+1)^{r+1+n(r-3)}(r-1)\\
&=(-1)^{n-1}2^{n-r}(r-1)(F_{K_{r+1}}(1, 1, \ldots ,1))^{n-r-1}, 
\end{align*}
where $n=\binom{r+1}{2}$. 
\end{proposition}

By \cref{cor:reg} and \cref{KSSymtherelative,yazawa}, we have \cref{maintheorem2}. 


%%%%%%%%
\section{Applications}\label{sec:Applications}

In this section, 
we define a graded Artinian Gorenstein algebra $R_\Gamma$ 
associated to a graph $\Gamma$ (more generally, to a matroid), as introduced by Maeno--Numata \cite{MR3566530}. 
Then, using strict log-concavity of $F_\Gamma$ 
at any $\bm{a}\in(\R_{>0})^n$, 
we prove that $L_{\bm{a}}:=a_1x_1+\cdots+a_nx_n\in R_{F_\Gamma}^1$ 
satisfies the strong Lefschetz property at $R^1_{F_\Gamma}$. 

First, we define an Artinian Gorenstein algebra associated to each homogeneous polynomial.  
For a homogeneous polynomial $F\in \R[x_1, \ldots, x_n]$ 
of degree $r$,  
define an ideal $\Ann(F)$ and a quotient algebra $R^*_F$ by
\begin{align*}
\Ann(F)&=\Set{P\in \R[x_1, \ldots, x_n]  |  P\left(\fr<\partial/\partial x_1>, \ldots, \fr<\partial/\partial x_n>\right)F=0}, \\
R^*_F&={\bigoplus_{\ell=0}^r{R_{F}^\ell}}=\R[x_1, \ldots, x_n]/\Ann(F). 
\end{align*}
Then $R^*_F$ is a graded Artinian Gorenstein algebra. 
Conversely, every graded Artinian Gorenstein algebra can be represented as above  by some homogeneous polynomial.   
See \cite[Proposition 2.1, Theorem 2.1 and Remark 2.3]{MR2594646} for more details. 


We recall the concepts of the strong Lefschetz property and the Hodge--Riemann bilinear relation. 

\begin{definition}[Strong Lefschetz property]\label{SLP}
We say that $L\in R_{F}^1$ 
satisfies the \emph{strong Lefschetz property} at degree $\ell$  
if the following multiplication map is bijective:   
\begin{align*}
\times L^{r-2\ell} : R_{F}^\ell &\to R_{F}^{r-\ell}, \\
f&\mapsto L^{r-2\ell}f. 
\end{align*}
\end{definition}

\begin{definition}[Hodge--Riemann relation]\label{HRR}
We say that $L\in R_{F}^1$ 
satisfies the \emph{Hodge--Riemann relation} at degree $\ell$  
if the Hodge--Riemann bilinear form 
\begin{align*}
Q_{L}^{\ell}:R_{F}^{\ell}\times R_{F}^{\ell}&\to {\R}, \\
(\xi_1, \xi_2)&\mapsto{[\xi_1L^{r-2\ell}\xi_2]}
\end{align*}
is negative definite on $\Ker(L^{r-1})$, 
where ${[-]} : R^r_F\xrightarrow{\sim} {\R}$ is the isomorphism as
\begin{align*}
P \mapsto P\left(\fr<\partial/\partial x_1>, \ldots, \fr<\partial/\partial x_n>\right)F. 
\end{align*}
\end{definition}

We note that, 
for a graded Artinian Gorenstein algebra {$R_F^*$} 
associated to a homogeneous polynomial $F$, 
the Hodge--Riemann bilinear form $Q_{L}^1$ at degree one is non-degenerate if and only if 
$L$ satisfies the strong Lefschetz property at degree one. 
We also note that if $F(\bm{a})>0$, 
then $L_{\bm{a}}$ 
satisfies the Hodge--Riemann relation at $R^1_F$ 
if and only if $Q_{L_{\bm{a}}}^1$ is non-degenerate and has only one positive eigenvalue. 
See the proof of \cite[Theorem 3.1]{MR2594646} for more details.


We will use the following criterion, which is a special case of the general criterion in \cite[Theorem 3.1]{MR2594646} and \cite[Theorem 4]{W2000}. 

\begin{thm}[{\cite[Theorem 3.1]{MR2594646}}, {\cite[Theorem 4]{W2000}}]\label{The Hessian criterion}
Assume that $x_1, \ldots, x_n\in R_F^1$ is a basis. 
An element $L_{\bm{a}}:=a_1x_1+\cdots+a_nx_n\in R_F^1$ 
satisfies the strong Lefschetz property at degree one if and only if $F(a_1, \ldots, a_n)\neq0$ and 
$\det H_{F}|_{\bm{x}=\bm{a}}\neq0$, 
where $H_F$ 
is the Hessian matrix of $F$. 
\end{thm}

Next, we consider the Artinian Gorenstein algebra $R^*_{F_M}$ 
associated to the basis generating function $F_M$ 
of a matroid $M$, 
in particular, the Kirchhoff polynomial $F_\Gamma$ 
of a simple graph $\Gamma$. 
Let $R^*$ be $R^*_{F_{\Gamma}}$. 

By our main result \cref{mainresult}, we have the following.

\begin{thm}\label{appthm}
Consider a simple graph $\Gamma=(V, E)$ with $|V|=r+1\geq3$ and $|E|=n\geq3$. 
For $\bm{a}=(a_1, \ldots, a_n)\in(\R_{>0})^n$, 
we define $L_{\bm{a}}=a_1x_1+\cdots+a_nx_n\in R^1$. 
Then we have the following:  
\begin{enumerate}
\item The linear form $L_{\bm{a}}$ satisfies the strong Lefschetz property at degree one. 
\item The Hodge--Riemann bilinear form
\[{Q_{L_{\bm{a}}}^1} : R^1\times R^1 \to \R, \ \ \ (\xi_1, \xi_2) \to {[\xi_1 L_{\bm{a}}^{r-2}\xi_2]}\]
is non-degenerate. 
Moreover, ${Q_{L_{\bm{a}}}^1}$ has $n-1$ negative eigenvalues and one positive eigenvalue. 
\end{enumerate}
\end{thm}

\begin{remark}
Related topics are studied in \cite{MR3733101}. 
Huh and Wang study another class of algebras associated to matroids in the paper. 
\end{remark}

\begin{remark}
Recently, strict log-concavity of the basis generating functions for simple matroids has been proven in \cite{MNY}.  
Murai, Nagaoka, and Yazawa use relations between strong Lefschetz property and Hodge--Riemann relation to prove. 
\end{remark}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

\printbibliography



\end{document}

