Originator: Y. Alavi, P. Erdős, P. Malde, and A. Schwenk (presented by David Galvin - REGS 2011)
Definitions: A sequence $(a_i)_{i=0}^n$ is unimodal if $a_0 \leq a_1 \leq \ldots \leq a_k \geq a_{k+1} \geq \ldots \geq a_n$ for some $k\in\{0, \ldots, n\}$. Such an index $k$ is a mode of the sequence. The sequence is log-concave if $a_k^2 \geq a_{k-1}a_{k+1}$ for $1\le k\lt n$. Unimodal sequences need not be log-concave, but log-concave sequences of positive terms are unimodal.
The independent set sequence (or stable set sequence) of a graph $G$ is $(i_t(G))_{t=0}^{\alpha(G)}$, where $i_t(G)$ is the number of independent sets of size $t$ in $G$ and $\alpha(G)$ is the maximum size of an independent set in $G$.
Conjecture 1: [AEMS] If $G$ is a tree, then the independent set sequence of $G$ is unimodal.
Conjecture 2: [AEMS] If $G$ is a forest, then the independent set sequence of $G$ is unimodal.
Conjecture 3: [LM] If $G$ is bipartite, then the independent set sequence of $G$ is unimodal.
Comments: In all three conjectures, it may be possible to strengthen "unimodal" to "log-concave".
The largest class of graphs for which the independent set sequences are known to be unimodal (in fact, log-concave) is the class of claw-free graphs [CS]. (In fact, claw-free graphs have the even stronger "real roots" property, which implies log-concavity). In general, the independent set sequence can be made arbitrarily far from unimodal [AEMS].
Levit and Mandrescu [LM] proved that if $G$ is bipartite, then $(i_t(G))_{t=[2\alpha(G)/3]}^{\alpha(G)}$ is decreasing. This suggests the further question, if the unimodality conjectures are true, of where in the sequence the mode can occur.
Galvin [G] has studied the independent set sequence of the random bipartite graph $G(n,n,p)$ with partite sets of size $n$ and edge probability $p$. He showed that for fixed $p$, the independent set sequence of $G(n,n,p)$ is almost surely unimodal, and it is almost surely log-concave except perhaps for a vanishingly small initial seqment of the sequence. Similar results hold for $p=\Omega(n^{-1/2})$. This approach would provide evidence for Conjectures 1 and 2 if $p$ could be brought down to $\Theta(1/n)$.
Conjecture 4: For fixed positive $c$, the independent set sequence of $G(n,n,c/n)$ is almost surely unimodal.
References:
[AEMS] Y. Alavi, P. Erdős, P. Malde and A. Schwenk, The vertex
independence sequence of a graph is not constrained, Congr. Numer., 1987.
[CS] M. Chudnovsky and P. Seymour, The Roots of The Stable Set Polynomial of
a Claw-free Graph, J. Combin. Theory. Ser. B, 2007.
[G] D. Galvin, Two problems on independent sets in graphs, available at
http://nd.edu/~dgalvin1/pdf/ind-sets-two.pdf, retrieved June 28 2011.
[LM] V. Levit and E. Mandrescu, Partial unimodality for independence
polynomials of König-Egerváry graphs, Congr. Numer., 2006.