Download

MSC2010 05C30

On generating functions and limit theorems connected with maximal independent sets in grid graphs

D. S. Taletskii1

AnnotationIn 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.
Keywordsindependent 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