%% 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]{FPSAC2023}
\articlenumber{87}
%% 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}

\newtheorem{lem}{Lemma}

\usepackage{tikz-cd}
\usepackage{amsfonts, amsxtra, mathrsfs, mathtools}

\newtheorem{thm}{Theorem}[section]
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{remark}[thm]{Remark}
\newtheorem{conditions}{Conditions}
\newtheorem{notation}[thm]{Notation}
\newtheorem{convention}[thm]{Convention}
\newtheorem{observation}[thm]{Observation}
\newtheorem{question}[thm]{Question}

%% define your title in the usual way
\title[Equivariant log-concavity of independence sequences of claw-free graphs]{Equivariant log-concavity of independence sequences of claw-free graphs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Shiyue Li]{Shiyue Li\thanks{\href{mailto:shiyue_li@brown.edu}{shiyue\_li@brown.edu}.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Brown University, Providence, RI 02912, USA}

%% put the date of submission here
\received{November 15, 2022}

%% 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{We show that the graded vector space spanned by independent vertex sets of any claw-free graph is strongly equivariantly log-concave, viewed as a graded permutation representation of the graph automorphism group. Our proof reduces the problem to the equivariant hard Lefschetz theorem on the cohomology of a product of projective lines, inspired by a combinatorial map of Krattenthaler. Both the result and the proof generalize our previous result on graph matchings. This also gives a strengthening and a new proof of results of Hamidoune, and Chudnovsky--Seymour. 
}

%% put your French abstract here, or comment this out if you don't have one

%% put your keywords here, or comment this out if you don't have them yet
\keywords{equivariant log-concavity, claw-free graphs, independence sequence}

%% 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; i.e., [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
\usepackage[backend=bibtex]{biblatex}
\addbibresource{87.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}
A graph $G$ is claw-free if no induced subgraph is the bipartite graph $K_{1, 3}$. An independent set of a graph $G$ is a set of nonadjacent vertices. The independence sequence of a claw-free graph is \textit{log-concave}: for all $1 \le k \le \ell$, the numbers $I_j$ of independent sets of size $j$ satisfies that 
\[
I_{k-1} I_{\ell+1} \le I_k I_{\ell}. 
\] This was first proven by Hamidoune \cite{hamidoune1990}. Then, Chudnovsky and Seymour \cite{Chudnovsky2007TheRO} proved it by showing that the generating polynomial has only real roots, which is well-known to imply log-concavity with no internal zeros.

It is often interesting to ask if a certain behavior of a mathematical object respects the underlying symmetry. The notion of equivariant log-concavity was introduced by Gedeon, Proudfoot and Young \cite{gedeon2017equivariant} as a natural categorification of logarithmic concavity. Recently, it is used to study various log-concavity behaviors with respect to a natural group action in the contexts of topology, geometry and combinatorics. 

Let $\Gamma$ be a finite group, a $\Gamma$-representation $V_{\bullet}$ is \textbf{strongly equivariantly log-concave} if for all $1 \le k \le \ell$, 
\[
V_{k-1} \otimes V_{\ell + 1} \subseteq V_{k} \otimes V_{\ell}
\] as a $\Gamma$-subrepresentation. 

We highlight some known equivariantly log-concave graded representations that are of combinatorial, geometric, and topological interests in the literature:
\begin{thm}
    \begin{enumerate}
        \item[(A)] The $V^{n}_{\bullet}$ given by the $q$-binomial coefficients for a fixed $n$ as a $\textrm{GL}_n(\mathbb{F}_q)$-representation is strongly equivariantly log-concave \cite[Proposition 6.7]{Proudfoot2018Z}.
        \item[(B)] The rational cohomology $H^{\ast}(\textup{Conf}(n, \mathbb{C}), \mathbb{Q})$ of the configuration space of $n$ points in $\mathbb{C}$ as an $S_{n}$-representation is strongly equivariantly log-concave for degrees $\le 14$ \cite{matherne2021equivariant}.
        \item[(C)] The rational cohomology $H^{\ast}(\textup{Conf}(n, \mathbb{R}^3), \mathbb{Q})$ of the configuration space of $n$ points in $\mathbb{C}$ as an $S_{n}$-representation is strongly equivariantly log-concave for degrees $\le 14$ \cite{matherne2021equivariant}.
        \item[(D)] The $V^n_{\bullet}$ of even degrees of the intersection homology of the complex affine hypertoric variety of the root system of $\frak{sl}_n$, viewed as an $S_n$-representation is strongly equivariantly log-concave for degrees $\le 14$ \cite{matherne2021equivariant}. 
        \item[(E)] The $V^{G}_{\bullet}$ given by matchings in a graph $G$ as an $\textup{Aut}(G)$-representation is strongly equivariantly log-concave \cite{li2022equivariant}. 
        \item[(F)] The $V^{n}_{\bullet}$ given by $k$-subsets in $[n]$ as an $S_n$-representation is strongly equivariantly log-concave (as a special case of \cite{li2022equivariant}). 
    \end{enumerate}
\end{thm}

The aim of this paper is to study the equivariant log-concavity of the following graded representation. Let $G$ be a claw-free graph. Let $\mathbb{I}_k$ denote the set of independent vertex sets of size $k$. The automorphism group $\textup{Aut}(G)$ naturally acts on all independent vertex sets, and each $\mathbb{I}_k$ is invariant under this action. 
Define the graded representation of $\textup{Aut}(G)$ 
\[
V_{\bullet}^{G} = \bigoplus_{k \ge 0, I \in \mathbb{I}_k} \mathbb{C} I,
\] and it admits a grading given by cardinalities. We have the following theorem. 

\begin{thm}
\label{thm:main}
    For any claw-free graph $G$, the graded $\textup{Aut}(G)$-representation $V^{G}_{\bullet}$ is strongly equivariantly log-concave. 
\end{thm}

\begin{remark}
    Our proof uses combinatorics inspired by the work of Krattenthaler \cite{Krattenthaler} to reduce the problem to the equivariant hard Lefschetz theorem on a Boolean algebra, or the cohomology of a product of projective lines, a generalization of the method in the author's previous work on graph matchings \cite{li2022equivariant}. 
    The result specializes to our previous result on graph matchings by taking the line graph $L(G)$ of a graph $G$: The line graph $L(G)$ of a graph $G$ consists of vertices each for every edge in $G$ and edges each for every common vertex shared by two edges in $G$. For example, every cycle graph $C_n$ with $n$ edges has its line graph isomorphic to itself, and the line graph of $K_4$ is the $1$-skeleton of the hypersimplex $\Delta(2, 4)$. A matching on $G$ of size $k$ yields an independent vertex set in $L(G)$ of size $k$. Line graphs are claw-free, by construction, but not all claw-free graphs are line graphs. 
\end{remark}



\begin{remark}
    Taking dimensions immediately covers the previous results of Hamidoune, and Chudnovsky--Seymour, thus giving new proofs to these results. 
\end{remark}

\begin{remark}
    Communicated by Eric Ramos and Nick Proudfoot, the group consisting of Melody Chan, Chris Eur, Dane Miyata, Nick Proudfoot, Eric Ramos, Lorenzo Vecchi, Claudia Yun, was studying if the graded $\textup{Aut}(T)$-representation of the independence sequence of a tree $T$ is strongly equivariantly log-concave. They provided a counterexample, the star graph with $6$ leaves, to disprove the statement. Note that this counterexample is ``claw-ful", quite the opposite of ``claw-free". Morally speaking, the enigmatic ``claw" structure seems to be an obstruction to the equivariant log-concavity of independence sequence of a tree, but the lack thereof turns out to be crucial in our proof of \cref{thm:main}. 
\end{remark}

\begin{remark}
    During FPSAC 2023, an audience member and later the FPSAC committee chairs pointed out a third proof, prior to this paper, of log-concavity of the independence sequences of claw-free graphs by \cite{wagner2001logarithmic}, of which we were not aware. The construction is similar to our construction in the reduction to the injectivity of the raising operator of an $\mathfrak{sl}_2(\mathbb{C})$-representation. One of the standard proofs of the hard Lefschetz theorem for a compact K\"{a}hler manifold is by exhibiting an $\mathfrak{sl}_2(\mathbb{C})$-action on the relevant vector space, where the hard Lefschetz operator coincides with the raising operator of the $\mathfrak{sl}_2(\mathbb{C})$-action. See, for example, Chern's proof \cite{chern1957generalization}. Our setup features the presence of a group action on the graded vector space, which naturally arises from the underlying objects, and is respected by the hard Lefschetz operator. A priori, the raising operator of a $\mathfrak{sl}_2(\mathbb{C})$-representation or the hard Lefschetz operator needs not be equivariant with respect to the natural group action. For example, at the end of \cite{wagner2001logarithmic}, Wagner recovers the well-known log-concavity of Stirling numbers of the second kind by constructing a claw-free graph for each $n$. However, we have shown, in an unpublished joint work with Siddarth Kannan, that the graded permutation representation of $S_n$ spanned by partitions of the set $[n]$ is not $S_n$-equivariantly log-concave. The $S_n$-equivariant embeddings fail when $n = 7, 8$.\footnote{Explicit computations are available at our GitHub repository: \url{https://github.com/shiyue-li/eqStir/blob/main/eqStir.sage}} It would be fascinating to see if there exist other natural categorifications of the Stirling numbers of the second kind, perhaps inspired by Wagner's construction, that are $S_n$-equivariantly log-concave. 
\end{remark}


\section{Proof of the main theorem}
In this section, we prove the main theorem. The main idea is to construct a family of $\textup{Aut}(G)$-equivariant injections 
\[
    V_{k-1} \otimes V_{\ell+1} \hookrightarrow V_{k} \otimes V_{\ell} 
\] for all $1 \le k \le \ell$ by reducing to the equivariant hard Lefschetz operator on a Boolean algebra, or the cohomology of a product of projective lines, via the combinatorics of the independent vertex sets. This method is inspired by Krattenthaler's combinatorial proof of the log-concavity of graph matching sequence \cite{Krattenthaler}. 

Fix a graph $G$ and $1 \le k \le \ell$, for each pair $I, J$ in $\mathbb{I}_{k-1} \times \mathbb{I}_{\ell + 1}$, consider the induced subgraph on the symmetric difference of $I$ and $J$, i.e., $(I \smallsetminus J) \cup (J \smallsetminus I)$, denoted by $G_{I, J}$. The components in $G_{I, J}$ can only be either a path or a cycle, because $G$ is claw-free and $I, J$ are independent vertex sets. Consider all the components in $G_{I, J}$ that are paths of even lengths, i.e., paths that contain odd number of vertices in $I \cup J$, denoted as $C_{I, J}$. ("C" for "chains".) Color vertices from $I$ with blue, and $J$ with pink. Note that each path in $C_{I, J}$ has both endpoints colored blue or pink. Now we do some counting: Let $P_{I, J}$ resp. $B_{I, J}$ be the number of paths with pink resp. blue endpoints in $C_{I, J}$. We have that 
\[
P_{I, J} + B_{I, J} = |C_{I, J}|, \textrm{ and } P_{I, J} - B_{I, J} = (\ell + 1) - (k - 1) \ge 2.
\]
From these, we know 
\begin{equation}
2 B_{I, J} \le B_{I, J} + P_{I, J} - 2 = |C_{I, J}| - 2, \textrm{ and therefore, } B_{I, J} \le \frac{|C_{I, J}|}{2} - 1. 
\end{equation}

Our next step is to decompose each of $V_{k-1} \otimes V_{\ell + 1}$ and $V_{k} \otimes V_{\ell}$ into a direct sum of Boolean algebras on certain partitions in $\mathbb{I}_{k-1} \times \mathbb{I}_{\ell + 1}$ and $\mathbb{I}_{k-1} \times \mathbb{I}_{\ell + 1}$.
\begin{definition}
    Two pairs $(I, J), (I', J')$ of independent vertex sets are equivalent if $I \cup J = I' \cup J'$ and $I$ resp. $J$ agrees with $I'$ resp. $J'$ outside of $C_{I, J}$ or $C_{I', J'}$. 
\end{definition}
One verifies using arguments in \cite{li2022equivariant} that this indeed gives partitions $\Pi_{k-1, \ell+1}$ and $\Pi_{k, \ell}$ on $\mathbb{I}_{k-1} \times \mathbb{I}_{\ell + 1}$ and $\mathbb{I}_{k} \times \mathbb{I}_{\ell}$ respectively.  

For any part $P \in \Pi_{k-1, \ell+1}$ and each pair $(I, J)$ in $P$, we associate a set of pairs of independent vertex sets in $\mathbb{I}_{k-1} \times \mathbb{I}_{\ell + 1}$ as follows. For each path in $C_{I, J}$ with endpoints colored blue, we swap the colors on all the vertices in this path from pink to blue and from blue to pink. This swapping produces a path in $C_{I, J}$ with endpoints colored pink. Now collect all the blue resp. pink vertices in $G_{I, J}$ and record that as $I'$ resp. $J'$. Since $I'$ resp. $J'$ now has $k$ resp. $\ell$ vertices, the pair $(I', J')$ is in $\mathbb{I}_{k} \times \mathbb{I}_{\ell}$. Repeat for every path in $C_{I, J}$, we obtain a subset $N_{I, J}$ in $\mathbb{I}_{k} \times \mathbb{I}_{\ell}$. See \cref{fig:new-pairs} for an example on the $6$-cycle graph for $k = \ell = 2$. 
\begin{figure}[h!]
    \centering
    \input{example.tex}
    \caption{}
    \label{fig:new-pairs}
\end{figure}
Using a similar argument as in \cite[Section 2.2]{li2022equivariant}, we verify that $N_{I, J}$ is a part of $\Pi_{k, \ell}$, denoted as $P'$. 
Now define a map
\[
\Phi_{k, \ell} \colon V_{k-1} \otimes V_{\ell+1} \to V_{k} \otimes V_{\ell}, \quad I \otimes J \mapsto \frac{1}{|N_{I, J}|}\sum_{(I', J') \in N_{I, J}} I' \otimes J'.
\]
Using similar argument as in \cite[Section 2.2]{li2022equivariant}, one verifies that $\Phi_{k, \ell}$ is $\textup{Aut}(G)$-equivariant. 

To show injectivity, we consider the following vector space for any part $P$ in $\Pi_{k-1, \ell+1}$ 
\[
    V_{k-1, \ell+1}(P) := \textup{Span}_{\mathbb{F}}\{I \otimes J \mid (I, J) \in P\}. 
\]
We now realize $V_{k-1, \ell+1}(P)$ as a categorification of the $B_{P}$th level of the Boolean lattice on $C_P$.
Consider the map 
\[
\beta_P \colon P \to \binom{C_P}{B_P}, \quad (I, J) \mapsto \textrm{the set of paths with blue endpoints in $C_{I, J}$}.
\]\\
It is well-defined by the construction of paths of blue endpoints in $C_{P}$ and bijective using a similar argument in \cite{li2022equivariant}. 
Next, we consider the vector space 
\[
V_{C_P, B_P} := \textup{Span}_{\mathbb{F}} \bigg\{B \mid B \in \binom{C_P}{B_P}\bigg\}, 
\] and define
\[
\underline{\beta_P} \colon V_{k-1, \ell+1}(P) \to V_{C_P, B_P}, \quad I \otimes J \mapsto \textrm{the set of paths with blue endpoints in $C_{I, J}$}.
\]
It is an isomorphism of vector spaces, because $\beta_P$ is a bijection on the bases. 


Then, we do the same procedure for $\mathbb{I}_{k} \times \mathbb{I}_{\ell}$. We define vector spaces $V_{k, \ell}(P')$, $V_{C_P, B_{P'}}$ and the maps $\beta_{P'}$ and $\underline{\beta_{P'}}$ similar to those for $P$. Note that, by construction, \[B_{P'} = B_P + 1 \quad \textrm{and} \quad C_{P'} = C_P.\]

Finally, for each $P$ in $\Pi_{k-1, \ell+1}$, define the linear map 
\[
L_{P} \colon V_{C_P, B_P} \to V_{C_{P'}, B_P+1}, \quad B \mapsto \frac{1}{|C_P| - B_P} \sum_{B \subseteq B' \in \binom{C_P}{B_P + 1}} B'.
\]
Crucially, $L_P$ is a hard Lefschetz operator on the Boolean algebra spanned by all subsets of $C_P$, where the grading is given by cardinality. It is injective for degrees \[{B_P \le |C_P|/2 - 1}.\] This operator and its injectivity on the lower half graded pieces have been studied in various contexts. We invite the reader to see proofs of various flavors: \cite{stanley1980weyl}, \cite[The hard Lefschetz theorem]{stanley1983combinatorial}, \cite[Proposition 7]{hara2008determinants}, \cite{harima2013lefschetz}, \cite[Theorem 4.7]{stanley2013algebraic} and \cite[{Theorem 1.1(3)}]{braden2020singular}. 

By construction, the following diagram commutes: 
\begin{center}
\begin{tikzcd}
    V_{k-1, \ell+1}(P) \ar{r}{\beta_P} \ar[swap]{r}{\cong}\ar{d}{\Phi_{k, \ell}} & V_{C_P, B_P} \ar{d}{L_P} \\
    V_{k, \ell}(P') \ar{r}{\beta_{P'}} \ar[swap]{r}{\cong}& V_{C_{P'}, B_P + 1}.
\end{tikzcd}
\end{center}
Therefore, $\Phi_{k, \ell}$ is injective from $V_{k-1, \ell+1}(P)$ to $V_{k, \ell}(P')$.

Note that by construction, 
\[
    V_{k-1} \otimes V_{\ell+1} = \bigoplus_{P \in \Pi_{k-1, \ell+1}} V_{k-1, \ell+1}(P) \cong \bigoplus_{P \in \Pi_{k-1, \ell+1}} V_{C_P, B_P}.
\]  
Then the last sentence of the previous paragraph implies that $\Phi_{k, \ell}$ is injective on the tensor product ${V_{k-1} \otimes V_{\ell+1}}$. 




\acknowledgements{The author is thankful to Eric Ramos for bringing up this direction of generalization of the author's previous work. This work benefited hugely from conversations with Nick Proudfoot during the author's short-term visit to the University of Oregon. This work is supported by a Coline M. Makepeace Fellowship at Brown University and the travel to Oregon was made possible by a Focused Research Group grant NSF DMS-2053221.}

%% 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}
