Skip to main content

The number of independent sets in hexagonal graphs

Publication ,  Conference
Deng, Z; Ding, J; Heal, K; Tarokh, V
Published in: IEEE International Symposium on Information Theory - Proceedings
August 9, 2017

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.

Duke Scholars

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

ISBN

9781509040964

Publication Date

August 9, 2017

Start / End Page

2910 / 2914
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Deng, Z., Ding, J., Heal, K., & Tarokh, V. (2017). The number of independent sets in hexagonal graphs. In IEEE International Symposium on Information Theory - Proceedings (pp. 2910–2914). https://doi.org/10.1109/ISIT.2017.8007062
Deng, Z., J. Ding, K. Heal, and V. Tarokh. “The number of independent sets in hexagonal graphs.” In IEEE International Symposium on Information Theory - Proceedings, 2910–14, 2017. https://doi.org/10.1109/ISIT.2017.8007062.
Deng Z, Ding J, Heal K, Tarokh V. The number of independent sets in hexagonal graphs. In: IEEE International Symposium on Information Theory - Proceedings. 2017. p. 2910–4.
Deng, Z., et al. “The number of independent sets in hexagonal graphs.” IEEE International Symposium on Information Theory - Proceedings, 2017, pp. 2910–14. Scopus, doi:10.1109/ISIT.2017.8007062.
Deng Z, Ding J, Heal K, Tarokh V. The number of independent sets in hexagonal graphs. IEEE International Symposium on Information Theory - Proceedings. 2017. p. 2910–2914.

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

ISBN

9781509040964

Publication Date

August 9, 2017

Start / End Page

2910 / 2914