The independent set sequence of regular bipartite graphs

DOI10.1016/J.DISC.2012.06.011MaRDI QIDQ449128zbMATH OpenOpenAlexFDO

Authors David Galvin

Publication date 12 September 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.3760

zbMATH Keywords

regular graphdiscrete hypercubeindependent set polynomialstable set polynomialunimodal sequence

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $i_t(G)$ be the number of independent sets of size $t$ in a graph $G$. Alavi, ErdH{o}s, Malde and Schwenk made the conjecture that if $G$ is a tree then the independent set sequence ${i_t(G)}_{tgeq0}$ 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):=su{m}_{tgeq0}{i}_t(G)lambd{a}^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 range $t(d)/2^{d-1}>1-1/sqrt2$, 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$.

Recommendations

• Two problems on independent sets in graphs
• An upper bound for the number of independent sets in regular graphs
• The number of independent sets in a regular graph
• Counting independent sets in regular hypergraphs
• scientific article; zbMATH DE number 5130736

Cites work

• scientific article; zbMATH DE number 3833857 (Why is no real title available?)
• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 5139526 (Why is no real title available?)
• scientific article; zbMATH DE number 4112649 (Why is no real title available?)
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• A threshold phenomenon for random independent sets in the discrete hypercube
• Matchings and independent sets of a fixed size in regular graphs
• On the numbers of independent k-sets in a claw free graph
• The number of independent sets in a regular graph
• The roots of the independence polynomial of a clawfree graph
• Theory of monomer-dimer systems
• Two problems on independent sets in graphs
• \(H\)-colouring bipartite graphs

Cited in

(3)

• Two problems on independent sets in graphs
• Independent sets of a given size and structure in the hypercube
• Sequences of radius \(k\) for complete bipartite graphs

This page was built for publication: The independent set sequence of regular bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q449128)