RUS  ENG
Полная версия
ЖУРНАЛЫ // Журнал Средневолжского математического общества // Архив

Журнал СВМО, 2017, том 19, номер 2, страницы 105–116 (Mi svmo665)

Математика

О производящих функциях и предельных теоремах, связанных с максимальными независимыми множествами в графах-решетках

Д. С. Талецкий

Нижегородский государственный университет им. Н. И. Лобачевского

Аннотация: В настоящей работе рассматриваются количественные характеристики максимальных независимых множеств в графах-решетках. В ней используются методы комбинаторного анализа, перечислительной комбинаторики, математического анализа и линейной алгебры. Получен явный вид производящих функций количества максимальных независимых множеств в цилиндрических и тороидальных решетках ширины 4, 5, 6. Доказано, что пределы корней $mn$-ой степени из количества (максимальных) независимых множеств в прямоугольных, цилиндрических и тороидальных $m\times n$-решетках существуют и равны. Количественные аспекты максимальных независимых множеств в графах-решетках применительно к цилиндрическим и тороидальным решеткам ранее не рассматривались. Кроме того, существование пределов корней $mn$-ой степени из количества максимальных независимых множеств в $m\times n$-решетках также не было доказано. Таким образом, настоящая работа является дальнейшим развитием перечислительной комбинаторики.

Ключевые слова: независимое множество, граф-решетка, производящая функция, предельная теорема.

УДК: 519.17

MSC: 05C30

DOI: 10.15507/2079-6900.19.201701.105-116



Реферативные базы данных:


© МИАН, 2024