RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2017, том 464, страницы 132–168 (Mi znsl6526)

Эта публикация цитируется в 6 статьях

Турановские оценки для дистанционных графов в тонкой слойке

Л. Э. Шабанов

Московский Физико-технический институт (государственный унверситет), ФИВТ, Лаборатории продвинутой комбинаторики и сетевых приложений МФТИ, Институтский пер. д. 9, 141700 Долгопрудный, Россия

Аннотация: В данной работе нами получена нижняя оценка количества ребер в дистанционном графе $\Gamma$ в слойке $\mathbb R^2\times[0,\varepsilon]^d$, которая связывает между собой количество ребер $e(\Gamma)$, число вершин $\nu(\Gamma)$ и число независимости $\alpha(\Gamma)$, а именно доказано, что $e(\Gamma)\ge\frac{19\nu\Gamma)-50\alpha(\Gamma)}3$. Этот результат является обобщением предыдущей аналогичной оценки для дистанционных графов на плоскости и существенным улучшением Турановской оценки в случае, когда $\frac15\le\frac{\alpha(\Gamma)}{\nu(\Gamma)}\le\frac27$. Библ. – 18 назв.

Ключевые слова: дистанционный граф, число независимости, Турановские оценки.

УДК: 519.173

Поступило: 03.11.2017


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2019, 236:5, 554–578


© МИАН, 2024