Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/142873
|
| Title: | 謝爾賓斯基墊片上一般獨立集數量的漸近行為
Asymptotic enumeration of general independent sets on the Sierpinski gasket |
| Authors: | 陳品樺
Chen, Pin-Hua |
| Contributors: | 陳隆奇
Chen, Lung-Chi
陳品樺
Chen, Pin-Hua |
| Keywords: | 謝爾賓斯基墊片
獨立集
Sierpinski gasket
Independent sets |
| Date: | 2022 |
| Issue Date: | 2023-01-05 15:13:27 (UTC+8) |
| 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)) 中熵的漸近行為。
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. |
| 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. |
| Description: | 碩士
國立政治大學
應用數學系
108751010 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0108751010 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU202201726 |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 101001.pdf | 641Kb | Adobe PDF2 | 25 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
