УДК 519.17
О производящих функциях и предельных теоремах, связанных с максимальными независимыми множествами в графах-решетках
Д. С. Талецкий1
| Аннотация | В настоящей работе рассматриваются количественные характеристики максимальных независимых множеств в графах-решетках. В ней используются методы комбинаторного анализа, перечислительной комбинаторики, математического анализа и линейной алгебры. Получен явный вид производящих функций количества максимальных независимых множеств в цилиндрических и тороидальных решетках ширины $4,5,6$. Доказано, что пределы корней $mn$-ой степени из количества (максимальных) независимых множеств в прямоугольных, цилиндрических и тороидальных $m\times n$-решетках существуют и равны. Количественные аспекты максимальных независимых множеств в графах-решетках применительно к цилиндрическим и тороидальным решеткам ранее не рассматривались. Кроме того, существование пределов корней $mn$-ой степени из количества максимальных независимых множеств в $m\times n$-решетках также не было доказано. Таким образом, настоящая работа является дальнейшим развитием перечислительной комбинаторики. |
|---|---|
| Ключевые слова | независимое множество, граф-решетка, производящая функция, предельная теорема |
1Талецкий Дмитрий Сергеевич, лаборант, кафедра алгебры, геометрии и дискретной математики ФГАОУ ВО "ННГУ им. Н. И. Лобачевского" (603950, Россия, г. Нижний Новгород, пр. Гагарина, д. 23), ORCID: http://orcid.org/ 0000-0003-0966-3903, dmitalmail@gmail.com
Цитирование: Талецкий Д. С. О производящих функциях и предельных теоремах, связанных с максимальными независимыми множествами в графах-решетках // Журнал Средневолжского математического общества. 2017. Т. 19, № 2. С. 105–116.
DOI 10.15507/2079-6900.19.201701.105-116
