The number of independent sets in hexagonal graphs

Zhun Deng; Jie Ding; Kathryn Heal; Vahid Tarokh

doi:10.1109/ISIT.2017.8007062

The number of independent sets in hexagonal graphs

Zhun Deng
, Jie Ding
, Kathryn Heal
, Vahid Tarokh

Statistics (Twin Cities)

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	2017 IEEE International Symposium on Information Theory, ISIT 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2910-2914
Number of pages	5
ISBN (Electronic)	9781509040964
DOIs	https://doi.org/10.1109/ISIT.2017.8007062
State	Published - Aug 9 2017
Event	2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany Duration: Jun 25 2017 → Jun 30 2017

Publication series

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

Other

Other	2017 IEEE International Symposium on Information Theory, ISIT 2017
Country/Territory	Germany
City	Aachen
Period	6/25/17 → 6/30/17

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

Keywords

Hexagonal lattice
Independent set
Transfer matrix

Publisher link

10.1109/ISIT.2017.8007062

Find It

Find It at U of M Libraries

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). Article 8007062 (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8007062

The number of independent sets in hexagonal graphs. / Deng, Zhun; Ding, Jie; Heal, Kathryn et al.
2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 2910-2914 8007062 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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., 8007062, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 2910-2914, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 6/25/17. https://doi.org/10.1109/ISIT.2017.8007062

@inproceedings{380169cef23d4d24a5f3aa167d983001,

title = "The number of independent sets in hexagonal graphs",

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.",

keywords = "Hexagonal lattice, Independent set, Transfer matrix",

author = "Zhun Deng and Jie Ding and Kathryn Heal and Vahid Tarokh",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 2017 IEEE International Symposium on Information Theory, ISIT 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

year = "2017",

month = aug,

day = "9",

doi = "10.1109/ISIT.2017.8007062",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2910--2914",

booktitle = "2017 IEEE International Symposium on Information Theory, ISIT 2017",

}

TY - GEN

T1 - The number of independent sets in hexagonal graphs

AU - Deng, Zhun

AU - Ding, Jie

AU - Heal, Kathryn

AU - Tarokh, Vahid

PY - 2017/8/9

Y1 - 2017/8/9

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

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

KW - Hexagonal lattice

KW - Independent set

KW - Transfer matrix

UR - https://www.scopus.com/pages/publications/85034117793

UR - https://www.scopus.com/pages/publications/85034117793#tab=citedBy

U2 - 10.1109/ISIT.2017.8007062

DO - 10.1109/ISIT.2017.8007062

M3 - Conference contribution

AN - SCOPUS:85034117793

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2910

EP - 2914

BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017

Y2 - 25 June 2017 through 30 June 2017

ER -

The number of independent sets in hexagonal graphs

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this