\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P11}{20(4)}{2013}

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}



% ignore
\newcommand{\ignore}[1]{}



\author{Arnab Bhattacharyya\\
\small DIMACS \& Dept. of Computer Science\\[-0.8ex]
\small Rutgers University\\[-0.8ex]
\small New Jersey, U.S.A.\\
\small\tt arnabb@dimacs.rutgers.edu\\
\and
Jeff Kahn \\
\small Dept. of Mathematics\\[-0.8ex]
\small Rutgers University\\[-0.8ex]
\small New Jersey, U.S.A.\\
\small\tt jkahn@math.rutgers.edu
}

\title{\bf A bipartite graph with non-unimodal independent set sequence}

\date{\dateline{Apr 7, 2013}{Oct 16, 2013}{Oct 28, 2013}\\
\small Mathematics Subject Classifications: 05C69, 05C31}

\begin{document}
\maketitle

\begin{abstract}
We show that the independent set sequence of a bipartite graph need not
be unimodal.
\end{abstract}


\section{Introduction}

For a graph $G = (V,E)$ and an integer $t \geq 0$, let $i_t(G)$ denote
the number of independent sets of size $t$ in $G$.
(Recall that an independent set is a set of vertices spanning no edges.)
The {\em independent set sequence} of $G$ is the sequence
$i(G)=(i_t(G))_{t=0}^{\alpha(G)}$, where $\alpha(G)$ is the size of a largest
independent set in $G$.

It was conjectured by Levit and Mandrescu \cite{Levit} that for any
bipartite graph $G$, $i(G)$ is unimodal; that is,
that there is a $k$ for which
$$i_0(G) \leq i_1(G) \leq \cdots \leq i_k(G) \geq i_{k+1}(G) \geq
\cdots \geq i_{\alpha(G)}(G).
$$
Evidence in favor of this was given by Levit and Mandrescu
\cite{Levit} and by Galvin (in \cite{Galvin}, which got us interested
in the problem, and in \cite{Galvin2}).

In this note, we disprove the conjecture:
\begin{theorem}\label{main}
There are bipartite graphs $G$ for which $i(G)$ is not unimodal.
\end{theorem}
\noindent
Still open and very interesting is the possibility, first suggested by
Alavi,  Malde, Schwenk and Erd\H os \cite{Alavi}, that trees and
forests have unimodal independent set sequences.
 See also \cite{Stanley} for a general survey of unimodality and the
 stronger notion of log-concavity.



\section{Counterexample}

Given positive integers $a$ and $b>a$, let
$G=G(a,b) = (V,E)$ with:
$V = V_1 \cup V_2\cup V_3$, where $V_1,V_2,V_3$ are disjoint;
$|V_1|=b-a$ and $|V_2|=|V_3|=a$; and
$E$ consists of a complete bipartite
graph between $V_1$ and $V_2$ and a perfect matching between $V_2$ and
$V_3$.
\begin{lemma}
For every $t  \geq0$, $i_t(G) = (2^t - 1) {a \choose t} + {b \choose t}.$
\end{lemma}
\begin{proof}
Each independent set in $G$ is a subset of
either $V_1 \cup V_3$ or $V_2 \cup V_3$. Among independent sets of size $t$,
the number of the first type is ${b \choose t}$,
the number of the second type is $2^t {a \choose t}$, and the number that are of
both types (that is, that are subsets of $V_3$) is
${a \choose t}$.
\end{proof}

We now assert that $i(G)$ is not unimodal if $a$ is large and (say)
$b=\lfloor a \log_23\rfloor$.
In this case, the expressions
${b \choose t}$
and $2^t {a \choose t}$ are maximized at $t_1=b/2$ and $t_2=2a/3+O(1)$
respectively (the overlap ${a \choose t}$ is negligible),
with each maximum on the order of $3^a/\sqrt{a}$.
On the other hand, each expression
is $o(3^a/\sqrt{a})$ if $t$ is at least $\omega(\sqrt{a})$ from the maximizing value.
In particular, $i_t(G)$ is much smaller for $t= (t_1+t_2)/2$ than for $t\in\{t_1,t_2\}$,
so $i(G)$ is not unimodal.



For a concrete example, we may take $a = 95$ and $b = 151$, for which explicit calculation gives
\begin{align*}
&i_{70}(G) = 189874416016052359845764115146202643360315069,\\
&i_{71}(G) = 187958904435447560369145399619337946363249075,\\
&i_{72}(G) = 188299580501161488791208803278091384597416875.
\end{align*}
In fact, we find that $95$ is the minimum value of $a$ for which the
above construction produces a counterexample.


\section{Remarks}

The construction above can be generalized to show that  (for bipartite $G$)
$i(G)$ can have
arbitrarily many local maxima.
Given (positive) integers $k$ and $a,a_1,\ldots, a_k$,
let $G=G(a,a_1,\ldots,a_k)=(A\cup B,E)$ be the bipartite graph where:
$A=\cup_{i=0}^kA_i$ and
$B=\cup_{j=1}^kB_j$, with all $A_i$'s and $B_j$'s disjoint;
$|A_0| = |B_1| = |B_2| = \cdots =|B_k| = a$
and $|A_i| = a_i$ for $i > 0$;
and $E$ consists of a perfect matching between $A_0$ and $B_j$
for each $j > 0$,
together with a complete bipartite graph between $A_i$
and $B_j$ for all $(i,j)$ with $j \leq i$.
Then for $a,a_1, \dots, a_k$ large with all the $k+1$ expressions
$2^{a_1+\cdots +a_i}(1+2^{k-i})^a$ roughly equal,
an analysis similar to the one above shows that $i(G)$ has
$k+1$ local maxima.


\begin{thebibliography}{AMSE87}

\bibitem[AMSE87]{Alavi}
Y.~Alavi, P.J. Malde, A.J. Schwenk, and P.~Erd{\H o}s.
\newblock The vertex independence sequence of a graph is not constrained.
\newblock {\em Congressus Numerantium}, 58:15--23, 1987.

\bibitem[Gal11]{Galvin2}
D.~Galvin.
\newblock Two problems on independent sets in graphs.
\newblock {\em Discrete Mathematics}, 311(20):2105--2112, 2011.

\bibitem[Gal12]{Galvin}
D.~Galvin.
\newblock The independent set sequence of regular bipartite graphs.
\newblock {\em Discrete Mathematics}, 312:2881--2892, 2012.

\bibitem[LM06]{Levit}
V.E. Levit and E.~Mandrescu.
\newblock Partial unimodality for independence polynomials of
  {K}\"onig-{E}gerv\'ary graphs.
\newblock {\em Congressus Numerantium}, 179:109--119, 2006.

\bibitem[Sta89]{Stanley}
R.P. Stanley.
\newblock Log-concave and unimodal sequences in algebra, combinatorics, and
  geometry.
\newblock {\em Annals of the New York Academy of Sciences}, 576:500--535, 1989.

\end{thebibliography}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: