Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs

Shu Chiuan Chang, Robert Shrock

研究成果: Article

摘要

We calculate exponential growth constants describing the asymptotic behavior of several quantities enumerating classes of orientations of arrow variables on the bonds of several types of directed lattice strip graphs G of finite width and arbitrarily great length, in the infinite-length limit, denoted {G}. Specifically, we calculate the exponential growth constants for (i) acyclic orientations, α({G}), (ii) acyclic orientations with a single source vertex, α0({G}), and (iii) totally cyclic orientations, β({G}). We consider several lattices, including square (sq), triangular (tri), and honeycomb (hc). From our calculations, we infer lower and upper bounds on these exponential growth constants for the respective infinite lattices. To our knowledge, these are the best current bounds on these quantities. Since our lower and upper bounds are quite close to each other, we can infer very accurate approximate values for the exponential growth constants, with fractional uncertainties ranging from O(10−4) to O(10−2). Further, we present exact values of α(tri), α0(tri), and β(hc) and use them to show that our lower and upper bounds on these quantities are very close to these exact values, even for modest strip widths. Results are also given for a nonplanar lattice denoted sqd. We show that α({G}), α0({G}), and β({G}) are monotonically increasing functions of vertex degree for these lattices. A comparison is given of these exponential growth constants with the corresponding exponential growth constant τ({G}) for spanning trees. Our results are in agreement with inequalities following from the Merino–Welsh and Conde–Merino conjectures.

原文English
文章編號123059
期刊Physica A: Statistical Mechanics and its Applications
540
DOIs
出版狀態Published - 2020 二月 15

指紋

Exponential Growth
Asymptotic Behavior
Graph in graph theory
Acyclic Orientation
Triangular
Upper and Lower Bounds
Honeycomb
Strip
strip
apexes
Calculate
Vertex Degree
Increasing Functions
Spanning tree
Square Lattice
Fractional
Uncertainty
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Condensed Matter Physics

引用此文

@article{71bcf4f3599c4d76bc8287fe455c0f13,
title = "Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs",
abstract = "We calculate exponential growth constants describing the asymptotic behavior of several quantities enumerating classes of orientations of arrow variables on the bonds of several types of directed lattice strip graphs G of finite width and arbitrarily great length, in the infinite-length limit, denoted {G}. Specifically, we calculate the exponential growth constants for (i) acyclic orientations, α({G}), (ii) acyclic orientations with a single source vertex, α0({G}), and (iii) totally cyclic orientations, β({G}). We consider several lattices, including square (sq), triangular (tri), and honeycomb (hc). From our calculations, we infer lower and upper bounds on these exponential growth constants for the respective infinite lattices. To our knowledge, these are the best current bounds on these quantities. Since our lower and upper bounds are quite close to each other, we can infer very accurate approximate values for the exponential growth constants, with fractional uncertainties ranging from O(10−4) to O(10−2). Further, we present exact values of α(tri), α0(tri), and β(hc) and use them to show that our lower and upper bounds on these quantities are very close to these exact values, even for modest strip widths. Results are also given for a nonplanar lattice denoted sqd. We show that α({G}), α0({G}), and β({G}) are monotonically increasing functions of vertex degree for these lattices. A comparison is given of these exponential growth constants with the corresponding exponential growth constant τ({G}) for spanning trees. Our results are in agreement with inequalities following from the Merino–Welsh and Conde–Merino conjectures.",
author = "Chang, {Shu Chiuan} and Robert Shrock",
year = "2020",
month = "2",
day = "15",
doi = "10.1016/j.physa.2019.123059",
language = "English",
volume = "540",
journal = "Physica A: Statistical Mechanics and its Applications",
issn = "0378-4371",
publisher = "Elsevier",

}

TY - JOUR

T1 - Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs

AU - Chang, Shu Chiuan

AU - Shrock, Robert

PY - 2020/2/15

Y1 - 2020/2/15

N2 - We calculate exponential growth constants describing the asymptotic behavior of several quantities enumerating classes of orientations of arrow variables on the bonds of several types of directed lattice strip graphs G of finite width and arbitrarily great length, in the infinite-length limit, denoted {G}. Specifically, we calculate the exponential growth constants for (i) acyclic orientations, α({G}), (ii) acyclic orientations with a single source vertex, α0({G}), and (iii) totally cyclic orientations, β({G}). We consider several lattices, including square (sq), triangular (tri), and honeycomb (hc). From our calculations, we infer lower and upper bounds on these exponential growth constants for the respective infinite lattices. To our knowledge, these are the best current bounds on these quantities. Since our lower and upper bounds are quite close to each other, we can infer very accurate approximate values for the exponential growth constants, with fractional uncertainties ranging from O(10−4) to O(10−2). Further, we present exact values of α(tri), α0(tri), and β(hc) and use them to show that our lower and upper bounds on these quantities are very close to these exact values, even for modest strip widths. Results are also given for a nonplanar lattice denoted sqd. We show that α({G}), α0({G}), and β({G}) are monotonically increasing functions of vertex degree for these lattices. A comparison is given of these exponential growth constants with the corresponding exponential growth constant τ({G}) for spanning trees. Our results are in agreement with inequalities following from the Merino–Welsh and Conde–Merino conjectures.

AB - We calculate exponential growth constants describing the asymptotic behavior of several quantities enumerating classes of orientations of arrow variables on the bonds of several types of directed lattice strip graphs G of finite width and arbitrarily great length, in the infinite-length limit, denoted {G}. Specifically, we calculate the exponential growth constants for (i) acyclic orientations, α({G}), (ii) acyclic orientations with a single source vertex, α0({G}), and (iii) totally cyclic orientations, β({G}). We consider several lattices, including square (sq), triangular (tri), and honeycomb (hc). From our calculations, we infer lower and upper bounds on these exponential growth constants for the respective infinite lattices. To our knowledge, these are the best current bounds on these quantities. Since our lower and upper bounds are quite close to each other, we can infer very accurate approximate values for the exponential growth constants, with fractional uncertainties ranging from O(10−4) to O(10−2). Further, we present exact values of α(tri), α0(tri), and β(hc) and use them to show that our lower and upper bounds on these quantities are very close to these exact values, even for modest strip widths. Results are also given for a nonplanar lattice denoted sqd. We show that α({G}), α0({G}), and β({G}) are monotonically increasing functions of vertex degree for these lattices. A comparison is given of these exponential growth constants with the corresponding exponential growth constant τ({G}) for spanning trees. Our results are in agreement with inequalities following from the Merino–Welsh and Conde–Merino conjectures.

UR - http://www.scopus.com/inward/record.url?scp=85073727776&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073727776&partnerID=8YFLogxK

U2 - 10.1016/j.physa.2019.123059

DO - 10.1016/j.physa.2019.123059

M3 - Article

AN - SCOPUS:85073727776

VL - 540

JO - Physica A: Statistical Mechanics and its Applications

JF - Physica A: Statistical Mechanics and its Applications

SN - 0378-4371

M1 - 123059

ER -