Mathematics – Combinatorics
Scientific paper
2011-10-17
Mathematics
Combinatorics
17 pages
Scientific paper
Let $i_t(G)$ be the number of independent sets of size $t$ in a graph $G$. Alavi, Erd\H{o}s, Malde and Schwenk made the conjecture that if $G$ is a tree then the independent set sequence $\{i_t(G)\}_{t\geq 0}$ of $G$ is unimodal; Levit and Mandrescu further conjectured that this should hold for all bipartite $G$. We consider the independent set sequence of finite regular bipartite graphs, and graphs obtained from these by percolation (independent deletion of edges). Using bounds on the independent set polynomial $P(G,\lambda):=\sum_{t \geq 0} i_t(G)\lambda^t$ for these graphs, we obtain partial unimodality results in these cases. We then focus on the discrete hypercube $Q_d$, the graph on vertex set $\{0,1\}^d$ with two strings adjacent if they differ on exactly one coordinate. We obtain asymptotically tight estimates for $i_{t(d)}(Q_d)$ in the case where $\lim t(d)/2^{d-1}$ is greater than $1-1/\sqrt{2}$, and nearly matching upper and lower bounds otherwise. We use these estimates to obtain a stronger partial unimodality result for the independent set sequence of $Q_d$.
No associations
LandOfFree
The independent set sequence of regular bipartite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The independent set sequence of regular bipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The independent set sequence of regular bipartite graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-319150