Research ArticlesNo Access

Vertex-colored graphs, bicycle spaces and Mahler measure

Department of Mathematics, University of Southern Mississippi Gulf Park, 730 East Beach Boulevard, Long Beach, MS 39560, USA

E-mail Address: kalyn.lamey@usm.edu

Search for more papers by this author

Daniel S. Silver

Department of Mathematics and Statistics, ILB 325, University of South Alabama, Mobile, AL 36608, USA

E-mail Address: silver@southalabama.edu

Search for more papers by this author

, and

Susan G. Williams

Department of Mathematics and Statistics, ILB 325, University of South Alabama, Mobile, AL 36608, USA

E-mail Address: swilliam@southalabama.edu

Search for more papers by this author

https://doi.org/10.1142/S0218216516500334Cited by:2 (Source: Crossref)

Abstract

The space $𝒞$ of conservative vertex colorings (over a field $𝔽$ ) of a countable, locally finite graph $G$ is introduced. When $G$ is connected, the subspace $𝒞^{0}$ of based colorings is shown to be isomorphic to the bicycle space of the graph. For graphs $G$ with a cofinite free $ℤ^{d}$ -action by automorphisms, $𝒞$ is dual to a finitely generated module over the polynomial ring $𝔽 [x_{1}^{\pm 1}, \dots, x_{d}^{\pm 1}]$ . Polynomial invariants for this module, the Laplacian polynomials $Δ_{k}, k \geq 0$ , are defined, and their properties are discussed. The logarithmic Mahler measure of $Δ_{0}$ is characterized in terms of the growth of spanning trees.

Keywords:

AMSC: 05C10, 37B10, 57M25, 82B20

References

1. C. P. Bonnington and R. B. Richter, Graphs embedded in the plane with a bounded number of accumulation points, J. Graph Theory 442 (2003) 132–147. Crossref, Web of Science, Google Scholar
2. D. Boyd, Speculations concerning the range of Mahler’s measure, Canad. Math. Bull. 24 (1981) 453–469. Crossref, Web of Science, Google Scholar
3. M. Braverman, R. Kulkarni and S. Roy, Parity problems in planar graphs, in Electronic Colloquium on Computational Complexity, Report No. 35 (2007), pp. 1–26. Google Scholar
4. H. Bruhn, S. Kosuch and M. W. Myint, Bicycles and left-right tours in locally finite graphs, European J. Combin. 30 (2009) 356–371. Crossref, Web of Science, Google Scholar
5. R. Burton and R. Pemantle, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Prob. 21 (1993) 1329–1371. Crossref, Web of Science, Google Scholar
6. J. S. Carter, D. S. Silver and S. G. Williams, Three dimensions of knot coloring, American Math. Monthly 121 (2014) 506–514. Crossref, Web of Science, Google Scholar
7. S.-C. Chang and R. Shrock, Tutte polynomials and related asymptotic limiting functions for recursive families of graphs, Adv. Appl. Math. 32 (2004) 44–87. Crossref, Web of Science, Google Scholar
8. S.-C. Chang and R. Shrock, Some exact results for spanning trees on lattices, J. Phys. A 39(20) (2006) 5653–5658. Crossref, Google Scholar
9. R. H. Crowell and R. H. Fox, Introduction to Knot Theory (Ginn and Company, Boston, 1963). Google Scholar
10. G. Everest and T. Ward, Heights of Polynomials and Entropy in Algebraic Dynamics (Springer, London, 1999). Crossref, Google Scholar
11. R. Forman, Determinants of Laplacians on graphs, Topology 32 (1993) 35–46. Crossref, Google Scholar
12. A. Garcia, M. Noy and J. Tejel, The asymptotic number of spanning trees in d-dimensional square lattices, J. Combin. Math. Combin. Comput. 44 (2003) 109–113. Google Scholar
13. C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001). Crossref, Google Scholar
14. M. J. Golin, X. Yong and Y. Zhang, The asymptotic number of spanning trees in circulant graphs, Discrete Math. 310 (2010) 792–803. Crossref, Web of Science, Google Scholar
15. G. R. Grimmett, An upper bound for the number of spanning trees of a graph, Discrete Math. 16 (1976) 323–324. Crossref, Web of Science, Google Scholar
16. A. J. Guttmann and M. Rogers, Spanning tree generating functions and Mahler measures, J. Phys. A 45(49) (2012) 494001, 24 pp. Crossref, Google Scholar
17. L. H. Kauffman, Formal Knot Theory (Princeton University Press, 1983). Google Scholar
18. R. Kenyon, Spanning forests and the vector bundle Laplacian, Ann. Probab. 39 (2011) 1983–2017. Crossref, Web of Science, Google Scholar
19. R. Kenyon, The Laplacian on planar graphs and graphs on surfaces, in Current Developments in Mathematics (International Press, 2011), pp. 1–68. Crossref, Google Scholar
20. D. A. Lind, K. Schmidt and T. Ward, Mahler measure and entropy for commuting automorphisms of compact groups, Invent. Math. 101 (1990) 593–629. Crossref, Web of Science, Google Scholar
21. Z. Lonc, K. Parol and J. M. Wojciechowski, On the asymptotic behavior of the maximum number of spanning trees in circulant graphs, Networks 30(1) (1997) 47–56. Crossref, Web of Science, Google Scholar
22. R. Lyons, Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005) 491–522. Crossref, Web of Science, Google Scholar
23. M. W. Myint, Bicycles and left-right tours in locally finite graphs, Ph.D. dissertation submitted to University of Hamburg (2009). Google Scholar
24. R. B. Richter and A. Vella, Cycle spaces in topological spaces, J. Graph Theory 59 (2008) 115–144. Crossref, Web of Science, Google Scholar
25. K. Schmidt, Dynamical Systems of Algebraic Origin (Birkhäuser, Basel, 1995). Google Scholar
26. H. Shank, The theory of left-right paths, in Combinatorial Mathematics III, Lecture Notes in Mathematics, Vol. 452 (Springer, 1975), pp. 42–54. Crossref, Google Scholar
27. R. Shrock and F. Y. Wu, Spanning trees on graphs and lattices in $d$ dimensions, J. Phys. A 33 (2000) 3881–3902. Crossref, Google Scholar
28. D. S. Silver and S. G. Williams, Mahler measure, links and homology growth, Topology 41 (2002) 979–991. Crossref, Web of Science, Google Scholar
29. D. S. Silver and S. G. Williams, On the component number of links from plane graphs, J. Knot Theory Ramification 24 (2015) 1520002, 5 pp. Link, Web of Science, Google Scholar
30. D. S. Silver and S. G. Williams, Spanning trees and Mahler measure, preprint (2015). Google Scholar
31. R. Solomyak, On coincidence of entropies for two classes of dynamical systems, Ergod. Theory Dynam. Systems 18 (1998) 731–738. Crossref, Web of Science, Google Scholar
32. E. Teufl and S. Wagner, On the number of spanning trees on various lattices, J. Phys. A 43 (2010) 415001. Crossref, Google Scholar
33. L. Traldi, On the Goeritz matrix of a link, Math. Z. 188 (1985) 203–213. Crossref, Web of Science, Google Scholar
34. F. Y. Wu, Number of spanning trees on a lattice, J. Phys. A 10(6) (1977) L113. Crossref, Google Scholar