کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8897718 | 1631040 | 2018 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices
ترجمه فارسی عنوان
مرزهای بالا بر نرخ رشد مجموعه های مستقل در دو بعد از طریق ماتریس انتقال سنگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
چکیده انگلیسی
We devise an algorithm to calculate upper bounds on the growth rates of the number of independent sets on a variety of regular two-dimensional lattices, using an amalgamation of techniques from linear algebra, combinatorics, and statistical mechanics. Our method uses Calkin and Wilf's transfer matrix eigenvalue upper bound together with the Collatz-Wielandt formula from linear algebra. To obtain a good bound, we need an approximate eigenvector, which we find using Baxter's corner transfer matrix ansatz and Nishino and Okunishi's corner transfer matrix renormalisation group method. This results in an algorithm for computing upper bounds which is far faster in practice than all other known methods. It is also the first algorithm for this problem with a polynomial, rather than exponential, memory requirement, and it is extremely parallelisable. This allows us to make dramatic improvements to the previous best known upper bounds. We apply our algorithm to five models, including independent sets on the square lattice (also known as the hard squares lattice gas from statistical mechanics). In all cases we extend the number of rigorously known digits of the growth rate by 4-6 digits.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 555, 15 October 2018, Pages 139-156
Journal: Linear Algebra and its Applications - Volume 555, 15 October 2018, Pages 139-156
نویسندگان
Yao-ban Chan, Andrew Rechnitzer,