MSC2010 05C30
On generating functions and limit theorems connected with maximal independent sets in grid graphs
D. S. Taletskii1
| Annotation | In this paper we study some quantitative characteristics of maximal independent sets in grid graphs using methods of combinatorial analysis, enumerative combinatorics, mathematical analysis and linear algebra. We obtain the explicit generation functions for the number of maximal independent sets in cylindrical and toroidal lattices of width $4,5,6$. We prove that the limits of $mn$-th root of the number of (maximal) independent sets in rectangular, cylindrical and toroidal $m\times n$-lattices exist and are equal. Nobody studied the quantitative characteristics of maximal independent sets in grid graphs in respect to cylindrical and toroidal lattices before. Also nobody proved the existence of the limits of $mn$-th root of the number of maximal independent sets in grid graphs. Thus, our paper is a further development of enumerative combinatorics. |
|---|---|
| Keywords | independent set, grid graph, generating function, limit theorem |
1Dmitry S. Taletskii, laboratory assistant, Department of Algebra, Geometry and Discrete Mathematics, National Research Lobachevsky University of Nizhny Novgorod (23 Gagarina avenue, Nizhny Novgorod, 603950, Russia), ORCID: http://orcid.org/ 0000-0003-0966-3903, dmitalmail@gmail.com
Citation: D. S. Taletskii, "[On generating functions and limit theorems connected with maximal independent sets in grid graphs]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,19:2 (2017) 105–116 (In Russian)
DOI 10.15507/2079-6900.19.201701.105-116
