Article ID Journal Published Year Pages File Type
4647696 Discrete Mathematics 2012 12 Pages PDF
Abstract

Let it(G)it(G) be the number of independent sets of size tt in a graph GG. Alavi, Erdős, Malde and Schwenk made the conjecture that if GG is a tree then the independent set sequence {it(G)}t≥0{it(G)}t≥0 of GG is unimodal; Levit and Mandrescu further conjectured that this should hold for all bipartite GG.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,λ)≔∑t≥0it(G)λtP(G,λ)≔∑t≥0it(G)λt for these graphs, we obtain partial unimodality results in these cases.We then focus on the discrete hypercube QdQd, the graph on vertex set {0,1}d{0,1}d with two strings adjacent if they differ on exactly one coordinate. We obtain asymptotically tight estimates for it(d)(Qd)it(d)(Qd) in the range t(d)/2d−1>1−1/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 QdQd.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,