The number of independent sets in hexagonal graphs

Zhun Deng, Jie Ding, Kathryn Heal, Vahid Tarokh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We derive the tightest known bounds on η = 2ν, where ν is the growth rate of the logarithm of the number of independent sets on a hexagonal lattice. To obtain these bounds, we generalize a method proposed by Calkin and Wilf. Their original strategy cannot immediately be used to derive bounds for η, due to the difference in symmetry between square and hexagonal lattices, so we propose a modified method and an algorithm to derive rigorous bounds on η. In particular, we prove that 1.546440708536001 ≤ η ≤ 1.5513, which improves upon the best known bounds of 1.5463 ≤ η ≤ 1.5527 given by Nagy and Zeger. Our lower bound matches the numerical estimate of Baxter up to 9 digits after the decimal point, and our upper bound can be further improved by following our method.

Original languageEnglish (US)
Title of host publication2017 IEEE International Symposium on Information Theory, ISIT 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2910-2914
Number of pages5
ISBN (Electronic)9781509040964
DOIs
StatePublished - Aug 9 2017
Externally publishedYes
Event2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany
Duration: Jun 25 2017Jun 30 2017

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2017 IEEE International Symposium on Information Theory, ISIT 2017
CountryGermany
CityAachen
Period6/25/176/30/17

Keywords

  • Hexagonal lattice
  • Independent set
  • Transfer matrix

Fingerprint Dive into the research topics of 'The number of independent sets in hexagonal graphs'. Together they form a unique fingerprint.

  • Cite this

    Deng, Z., Ding, J., Heal, K., & Tarokh, V. (2017). The number of independent sets in hexagonal graphs. In 2017 IEEE International Symposium on Information Theory, ISIT 2017 (pp. 2910-2914). [8007062] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8007062