The independent set sequence of regular bipartite graphs

DOI10.1016/J.DISC.2012.06.011zbMATH Open1248.05138arXiv1110.3760OpenAlexW2022733949MaRDI QIDQ449128FDOQ449128

Authors: David Galvin 

Publication date: 12 September 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

• Theory of monomer-dimer systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two problems on independent sets in graphs
• The number of independent sets in a regular graph
• On the numbers of independent \(k\)-sets in a claw free graph
• The roots of the independence polynomial of a clawfree graph
• Title not available (Why is that?)
• Matchings and independent sets of a fixed size in regular graphs
• \(H\)-colouring bipartite graphs
• A threshold phenomenon for random independent sets in the discrete hypercube

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)