1. NCCU Academic Hub
  2. 學術產出
  3. College of Science
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

題名 謝爾賓斯基墊片上一般獨立集數量的漸近行為
Asymptotic enumeration of general independent sets on the Sierpinski gasket
作者 陳品樺
Chen, Pin-Hua
貢獻者 陳隆奇
Chen, Lung-Chi
陳品樺
Chen, Pin-Hua
關鍵詞 謝爾賓斯基墊片
獨立集
Sierpinski gasket
Independent sets
日期 2022
上傳時間 5-Jan-2023 15:13:27 (UTC+8)
摘要 計算獨立集的數量一直都是個重要且有趣的問題，在二維整數晶格中，
獨立集的數量上熵的極限存在，並估計其上下界，已被 [13] 探討。此外在
二維與三維謝爾賓斯基墊片獨立集的數量上熵的極限存在，並估計其上下
界也被 [32] 探討。
在本篇論文中，我們將推廣 [32] 二維的謝爾賓斯基墊片的獨立集個數
到機率分布，其解釋如下：令 A 是一個有限符號集合，並給定任意子集
S ⊂ A，假設 p ∈ (0, 1) 是二維的謝爾賓斯基墊片裡的每一個點屬於 S 的機率，又令 F = {ij : ij ∈ E, i, j ∈ S}，其中 E 是謝爾賓斯基墊片的邊，這是一種不被允許出現的情況。舉個特例，當 A = {0, 1}, S = {0} 而且 p = 1/2 (均勻分布) 在這種情況之下，就是 [32] 這篇文章的模型。這篇文章我們將研究這個分布模型 (p ∈ (0, 1)) 中熵的漸近行為。
Enumerate the number of independent sets or golden mean shift on the graph is a very interesting and important problem. For the square lattice, it was shown that the limit of the entropy of the number of independent sets exists and its upper and lower bounds were estimated [13], and its had been considered on various graphs [15]–[17]. Moreover, it is of interest to consider independent sets on self-similar fractal lattices which have scaling invariance rather than translational invariance [18]. Sierpinski gasket is a kind of self-similar fractal lattices, and the number of independent sets on Sierpinski gasket had been investigated in [32]. In
this thesis, we extend the independent sets in [32] to be more general model on the two-dimensional Sierpinski gasket. Let A is a set of symbol and given any S ⊂ A. Let p ∈ (0, 1) be the probability of each vertex of SG(n) with a symbol
that is in symbols S, and 1 − p be the probability of each vertex of SG(n) with a symbol that is not in symbols S where F = {ij : i, j ∈ S} is a forbidden blocks between nearest-neighbor vertices. In particular, it is so called a golden mean shift or independent set when A = {0, 1}, S = {0} and p = 1/2 . We will investigate the asymptotes behavior of the entropy in this general model.
參考文獻 [1] L. K. Runnels, Phase transitions of hard sphere lattice gases, Communications in Mathematical Physics 40 (1975) 37–48.
[2] G. R. Brightwell, O. Häggström, P. Winkler, Nonmonotonic behavior in hard-core and Widom-Rowlinson models, Journal of Statistical Physics 94 (1999) 415–435.
[3] J. R. Heringa, H. W. J. Blöte, E. Luijten, High-dimensional lattice gases, Journal of Physics
A-Mathematical and General 33 (2000) 2929–2941.
[4] W. Guo, H. W. Blöte, Finite-size analysis of the hard-square lattice gas, Physical Review E 66 (2002) 046140.
[5] I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Mathematica
24 (1983) 97–106.
[6] A. D. Scott, A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, Journal of Statistical Physics 118 (2005) 1151–1261.
[7] J. van den Berg, J. E. Steif, Percolation and the hard-core lattice gas model, Stochastic Processes and their Applications 49 (1994) 179–197.
[8] O. Häggström, Ergodicity of the hard-core model on Z
2 with parity-dependent activities,
Arkiv for Matematik 35 (1997) 171–184.
[9] J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics,
Probability and Computing 10 (2001) 219–237.
[10] M. Dyer, C. Greenhill, On Markov chains for independent sets, Journal of Algorithms 35
(2000) 17–49.

[11] H. Prodinger, R. F. Tichy, Fibonacci numbers of graphs, The Fibonacci Quarterly 20 (1982)
16–21.
[12] I. Kaplansky, Solution of the ”Problème des ménages”, Bulletin of the American
Mathematical Society 49 (1943) 784–485.
[13] N. J. Calkin, H. S. Wilf, The number of independent sets in a grid graph, SIAM Journal on Discrete Mathematics 11 (1998) 54–60.
[14] R. J. Baxter, Planar lattice gases with nearest-neighbor exclusion, Annals of Combinatorics
3 (1999) 191–203.
[15] V. Linke, Bipartite graphs can have any number of independent sets, Discrete Mathematics
76 (1989) 131–136.
[16] H. F. Law, On the number of independent sets in a tree, Electronic Journal of Combinatorics
17 (2010) #N18.
[17] Y. Zhao, The number of independent sets in a regular graph, Combinatorics, Probability
and Computing 19 (2010) 315–320.
[18] E. Teufl, S. Wagner, Enumeration problems for classes of self-similar graphs, Journal of
Combinatorial Theory Series A 114 (2007) 1254–1277.
[Mandelbrot(1982)] B. B. Mandelbrot, The Fractal Geometry of Nature, Freeman, San Francisco, 1982.
[Falconer(2003)] K. J. Falconer, Fractal Geometry: Mathematical Foundations and Applications (2nd edition), Wiley, Chichester, 2003.
[19] Y. Gefen, B. B. Mandelbrot, A. Aharony, Critical phenomena on fractal lattices, Physical Review Letters 45 (1980) 855–858.
[20] Y. Gefen, A. Aharony, B. B. Mandelbrot, S. Kirkpatrick, Solvable fractal family, and its
possible relation to the backbone at percolation, Physical Review Letters 47 (1981) 1771.
[21] R. Rammal, G. Toulouse, Spectrum of the Schrödinger equation on a self-similar structure,
Physical Review Letters 49 (1982) 1194–1197.

[22] S. Alexander, Superconductivity of networks. A percolation approach to the effects of
disorder, Physical Review B 27 (1983) 1541–1557.
[23] E. Domany, S. Alexander, D. Bensimon, L. P. Kadanoff, Solutions to the Schrödinger
equation on some fractal lattices, Physical Review B 28 (1983) 3110–3123.
[24] Y. Gefen, A. Aharony, B. B. Mandelbrot, Phase transitions on fractals: I. Quasi-linear
lattices, Journal of Physics A-Mathematical and General 16 (1983) 1267–1278.
[25] R. A. Guyer, Diffusion on the Sierpinski gaskets: A random walker on a fractally structured
object, Physical Review A 29 (1984) 2751–2755.
[26] K. Hattori, T. Hattori, S. Kusuoka, Self-avoiding paths on the pre-Sierpinski gasket,
Probability Theory and Related Fields 84 (1990) 1–26.
[27] D. Dhar, A. Dhar, Distribution of sizes of erased loops for loop-erased random walks,
Physical Review E 55 (1997) R2093–R2096.
[28] F. Daerden, C. Vanderzande, Sandpiles on a Sierpinski gasket, Physica A 256 (1998) 533–546.
[29] D. Dhar, Branched polymers on the Given-Mandelbrot family of fractals, Physical Review E 71 (2005) 031801.
[30] S.-C. Chang, L.-C. Chen, W.-S. Yang, Spanning trees on the Sierpinski gasket, Journal of Statistical Physics 126 (2007) 649–667.
[31] S.-C. Chang, L.-C. Chen, Spanning forests on the Sierpinski gasket, Discrete Mathematics
and Theoretical Computer Science 10 (2008) 55–76.
[32] S.-C. Chang, L.-C. Chen, Asymptotic enumeration of independent sets on the Sierpinski gasket, Flomat, 27:1 (2013).
[33] S.-C. Chang, L.-C. Chen, Number of connected spanning subgraphs on the Sierpinski
gasket, Discrete Mathematics and Theoretical Computer Science 11 (2009) 55–78.
[34] S.-C. Chang, L.-C. Chen, Dimer coverings on the Sierpinski gasket, Journal of Statistical Physics 131 (2008) 631–650.

[35] S.-C. Chang, L.-C. Chen, Dimer-monomer model on the Sierpinski gasket, Physica A 387
(2008) 1551–1566.
[36] S.-C. Chang, L.-C. Chen, Hamiltonian walks on the Sierpinski gasket, Journal of
Mathematical Physics 52 (2011) 023301.
[37] F. Harary, Graph Theory, Addison-Wesley, New York, 1969.
[38] N. L. Biggs, Algebraic Graph Theory (2nd edition) Cambridge University Press,
Cambridge, 1993.
描述 碩士
國立政治大學
應用數學系
108751010
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0108751010
資料類型 thesis
dc.contributor.advisor 陳隆奇zh_TW
dc.contributor.advisor Chen, Lung-Chien_US
dc.contributor.author (Authors) 陳品樺zh_TW
dc.contributor.author (Authors) Chen, Pin-Huaen_US
dc.creator (作者) 陳品樺zh_TW
dc.creator (作者) Chen, Pin-Huaen_US
dc.date (日期) 2022en_US
dc.date.accessioned 5-Jan-2023 15:13:27 (UTC+8)-
dc.date.available 5-Jan-2023 15:13:27 (UTC+8)-
dc.date.issued (上傳時間) 5-Jan-2023 15:13:27 (UTC+8)-
dc.identifier (Other Identifiers) G0108751010en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/142873-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 應用數學系zh_TW
dc.description (描述) 108751010zh_TW
dc.description.abstract (摘要) 計算獨立集的數量一直都是個重要且有趣的問題，在二維整數晶格中，
獨立集的數量上熵的極限存在，並估計其上下界，已被 [13] 探討。此外在
二維與三維謝爾賓斯基墊片獨立集的數量上熵的極限存在，並估計其上下
界也被 [32] 探討。
在本篇論文中，我們將推廣 [32] 二維的謝爾賓斯基墊片的獨立集個數
到機率分布，其解釋如下：令 A 是一個有限符號集合，並給定任意子集
S ⊂ A，假設 p ∈ (0, 1) 是二維的謝爾賓斯基墊片裡的每一個點屬於 S 的機率，又令 F = {ij : ij ∈ E, i, j ∈ S}，其中 E 是謝爾賓斯基墊片的邊，這是一種不被允許出現的情況。舉個特例，當 A = {0, 1}, S = {0} 而且 p = 1/2 (均勻分布) 在這種情況之下，就是 [32] 這篇文章的模型。這篇文章我們將研究這個分布模型 (p ∈ (0, 1)) 中熵的漸近行為。		zh_TW
dc.description.abstract (摘要) Enumerate the number of independent sets or golden mean shift on the graph is a very interesting and important problem. For the square lattice, it was shown that the limit of the entropy of the number of independent sets exists and its upper and lower bounds were estimated [13], and its had been considered on various graphs [15]–[17]. Moreover, it is of interest to consider independent sets on self-similar fractal lattices which have scaling invariance rather than translational invariance [18]. Sierpinski gasket is a kind of self-similar fractal lattices, and the number of independent sets on Sierpinski gasket had been investigated in [32]. In
this thesis, we extend the independent sets in [32] to be more general model on the two-dimensional Sierpinski gasket. Let A is a set of symbol and given any S ⊂ A. Let p ∈ (0, 1) be the probability of each vertex of SG(n) with a symbol
that is in symbols S, and 1 − p be the probability of each vertex of SG(n) with a symbol that is not in symbols S where F = {ij : i, j ∈ S} is a forbidden blocks between nearest-neighbor vertices. In particular, it is so called a golden mean shift or independent set when A = {0, 1}, S = {0} and p = 1/2 . We will investigate the asymptotes behavior of the entropy in this general model.		en_US
dc.description.tableofcontents Contents
致謝 ii
中文摘要 iii
Abstract iv
Contents v
List of Tables vi
List of Figures vii
1 Introduction 1
1.1 Preliminaries 2
2 Main Results 5
3 Proof of Theorem 2.0.3 13
4 Proof of Proposition 3.0.1 19
4.1 Proof of Lemma 4.0.1 22
4.2 Proof of lemma 4.0.2 25
5 Proof of Theorem 2.0.4 28
5.1 Proof of Proposition 5.0.1 33
Appendix A Experimental Results of Python 38
Bibliography 43		zh_TW
dc.format.extent 657094 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0108751010en_US
dc.subject (關鍵詞) 謝爾賓斯基墊片zh_TW
dc.subject (關鍵詞) 獨立集zh_TW
dc.subject (關鍵詞) Sierpinski gasketen_US
dc.subject (關鍵詞) Independent setsen_US
dc.title (題名) 謝爾賓斯基墊片上一般獨立集數量的漸近行為zh_TW
dc.title (題名) Asymptotic enumeration of general independent sets on the Sierpinski gasketen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) [1] L. K. Runnels, Phase transitions of hard sphere lattice gases, Communications in Mathematical Physics 40 (1975) 37–48.
[2] G. R. Brightwell, O. Häggström, P. Winkler, Nonmonotonic behavior in hard-core and Widom-Rowlinson models, Journal of Statistical Physics 94 (1999) 415–435.
[3] J. R. Heringa, H. W. J. Blöte, E. Luijten, High-dimensional lattice gases, Journal of Physics
A-Mathematical and General 33 (2000) 2929–2941.
[4] W. Guo, H. W. Blöte, Finite-size analysis of the hard-square lattice gas, Physical Review E 66 (2002) 046140.
[5] I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Mathematica
24 (1983) 97–106.
[6] A. D. Scott, A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, Journal of Statistical Physics 118 (2005) 1151–1261.
[7] J. van den Berg, J. E. Steif, Percolation and the hard-core lattice gas model, Stochastic Processes and their Applications 49 (1994) 179–197.
[8] O. Häggström, Ergodicity of the hard-core model on Z
2 with parity-dependent activities,
Arkiv for Matematik 35 (1997) 171–184.
[9] J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics,
Probability and Computing 10 (2001) 219–237.
[10] M. Dyer, C. Greenhill, On Markov chains for independent sets, Journal of Algorithms 35
(2000) 17–49.

[11] H. Prodinger, R. F. Tichy, Fibonacci numbers of graphs, The Fibonacci Quarterly 20 (1982)
16–21.
[12] I. Kaplansky, Solution of the ”Problème des ménages”, Bulletin of the American
Mathematical Society 49 (1943) 784–485.
[13] N. J. Calkin, H. S. Wilf, The number of independent sets in a grid graph, SIAM Journal on Discrete Mathematics 11 (1998) 54–60.
[14] R. J. Baxter, Planar lattice gases with nearest-neighbor exclusion, Annals of Combinatorics
3 (1999) 191–203.
[15] V. Linke, Bipartite graphs can have any number of independent sets, Discrete Mathematics
76 (1989) 131–136.
[16] H. F. Law, On the number of independent sets in a tree, Electronic Journal of Combinatorics
17 (2010) #N18.
[17] Y. Zhao, The number of independent sets in a regular graph, Combinatorics, Probability
and Computing 19 (2010) 315–320.
[18] E. Teufl, S. Wagner, Enumeration problems for classes of self-similar graphs, Journal of
Combinatorial Theory Series A 114 (2007) 1254–1277.
[Mandelbrot(1982)] B. B. Mandelbrot, The Fractal Geometry of Nature, Freeman, San Francisco, 1982.
[Falconer(2003)] K. J. Falconer, Fractal Geometry: Mathematical Foundations and Applications (2nd edition), Wiley, Chichester, 2003.
[19] Y. Gefen, B. B. Mandelbrot, A. Aharony, Critical phenomena on fractal lattices, Physical Review Letters 45 (1980) 855–858.
[20] Y. Gefen, A. Aharony, B. B. Mandelbrot, S. Kirkpatrick, Solvable fractal family, and its
possible relation to the backbone at percolation, Physical Review Letters 47 (1981) 1771.
[21] R. Rammal, G. Toulouse, Spectrum of the Schrödinger equation on a self-similar structure,
Physical Review Letters 49 (1982) 1194–1197.

[22] S. Alexander, Superconductivity of networks. A percolation approach to the effects of
disorder, Physical Review B 27 (1983) 1541–1557.
[23] E. Domany, S. Alexander, D. Bensimon, L. P. Kadanoff, Solutions to the Schrödinger
equation on some fractal lattices, Physical Review B 28 (1983) 3110–3123.
[24] Y. Gefen, A. Aharony, B. B. Mandelbrot, Phase transitions on fractals: I. Quasi-linear
lattices, Journal of Physics A-Mathematical and General 16 (1983) 1267–1278.
[25] R. A. Guyer, Diffusion on the Sierpinski gaskets: A random walker on a fractally structured
object, Physical Review A 29 (1984) 2751–2755.
[26] K. Hattori, T. Hattori, S. Kusuoka, Self-avoiding paths on the pre-Sierpinski gasket,
Probability Theory and Related Fields 84 (1990) 1–26.
[27] D. Dhar, A. Dhar, Distribution of sizes of erased loops for loop-erased random walks,
Physical Review E 55 (1997) R2093–R2096.
[28] F. Daerden, C. Vanderzande, Sandpiles on a Sierpinski gasket, Physica A 256 (1998) 533–546.
[29] D. Dhar, Branched polymers on the Given-Mandelbrot family of fractals, Physical Review E 71 (2005) 031801.
[30] S.-C. Chang, L.-C. Chen, W.-S. Yang, Spanning trees on the Sierpinski gasket, Journal of Statistical Physics 126 (2007) 649–667.
[31] S.-C. Chang, L.-C. Chen, Spanning forests on the Sierpinski gasket, Discrete Mathematics
and Theoretical Computer Science 10 (2008) 55–76.
[32] S.-C. Chang, L.-C. Chen, Asymptotic enumeration of independent sets on the Sierpinski gasket, Flomat, 27:1 (2013).
[33] S.-C. Chang, L.-C. Chen, Number of connected spanning subgraphs on the Sierpinski
gasket, Discrete Mathematics and Theoretical Computer Science 11 (2009) 55–78.
[34] S.-C. Chang, L.-C. Chen, Dimer coverings on the Sierpinski gasket, Journal of Statistical Physics 131 (2008) 631–650.

[35] S.-C. Chang, L.-C. Chen, Dimer-monomer model on the Sierpinski gasket, Physica A 387
(2008) 1551–1566.
[36] S.-C. Chang, L.-C. Chen, Hamiltonian walks on the Sierpinski gasket, Journal of
Mathematical Physics 52 (2011) 023301.
[37] F. Harary, Graph Theory, Addison-Wesley, New York, 1969.
[38] N. L. Biggs, Algebraic Graph Theory (2nd edition) Cambridge University Press,
Cambridge, 1993.		zh_TW
dc.identifier.doi (DOI) 10.6814/NCCU202201726en_US