學術產出-Theses
Article View/Open
Publication Export
-
題名 謝爾賓斯基墊片上一般獨立集數量的漸近行為
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]. Inthis 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 symbolthat 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 PhysicsA-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 Mathematica24 (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 Z2 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 AmericanMathematical 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 Combinatorics3 (1999) 191–203.[15] V. Linke, Bipartite graphs can have any number of independent sets, Discrete Mathematics76 (1989) 131–136.[16] H. F. Law, On the number of independent sets in a tree, Electronic Journal of Combinatorics17 (2010) #N18.[17] Y. Zhao, The number of independent sets in a regular graph, Combinatorics, Probabilityand Computing 19 (2010) 315–320.[18] E. Teufl, S. Wagner, Enumeration problems for classes of self-similar graphs, Journal ofCombinatorial 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 itspossible 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 ofdisorder, Physical Review B 27 (1983) 1541–1557.[23] E. Domany, S. Alexander, D. Bensimon, L. P. Kadanoff, Solutions to the Schrödingerequation 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-linearlattices, 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 structuredobject, 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 Mathematicsand 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 Sierpinskigasket, 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 ofMathematical 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-Chi en_US dc.contributor.author (Authors) 陳品樺 zh_TW dc.contributor.author (Authors) Chen, Pin-Hua en_US dc.creator (作者) 陳品樺 zh_TW dc.creator (作者) Chen, Pin-Hua en_US dc.date (日期) 2022 en_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) G0108751010 en_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 (描述) 108751010 zh_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]. Inthis 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 symbolthat 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中文摘要 iiiAbstract ivContents vList of Tables viList of Figures vii1 Introduction 11.1 Preliminaries 22 Main Results 53 Proof of Theorem 2.0.3 134 Proof of Proposition 3.0.1 194.1 Proof of Lemma 4.0.1 224.2 Proof of lemma 4.0.2 255 Proof of Theorem 2.0.4 285.1 Proof of Proposition 5.0.1 33Appendix A Experimental Results of Python 38Bibliography 43 zh_TW dc.format.extent 657094 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0108751010 en_US dc.subject (關鍵詞) 謝爾賓斯基墊片 zh_TW dc.subject (關鍵詞) 獨立集 zh_TW dc.subject (關鍵詞) Sierpinski gasket en_US dc.subject (關鍵詞) Independent sets en_US dc.title (題名) 謝爾賓斯基墊片上一般獨立集數量的漸近行為 zh_TW dc.title (題名) Asymptotic enumeration of general independent sets on the Sierpinski gasket en_US dc.type (資料類型) thesis en_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 PhysicsA-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 Mathematica24 (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 Z2 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 AmericanMathematical 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 Combinatorics3 (1999) 191–203.[15] V. Linke, Bipartite graphs can have any number of independent sets, Discrete Mathematics76 (1989) 131–136.[16] H. F. Law, On the number of independent sets in a tree, Electronic Journal of Combinatorics17 (2010) #N18.[17] Y. Zhao, The number of independent sets in a regular graph, Combinatorics, Probabilityand Computing 19 (2010) 315–320.[18] E. Teufl, S. Wagner, Enumeration problems for classes of self-similar graphs, Journal ofCombinatorial 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 itspossible 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 ofdisorder, Physical Review B 27 (1983) 1541–1557.[23] E. Domany, S. Alexander, D. Bensimon, L. P. Kadanoff, Solutions to the Schrödingerequation 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-linearlattices, 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 structuredobject, 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 Mathematicsand 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 Sierpinskigasket, 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 ofMathematical 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/NCCU202201726 en_US