"Записки научных семинаров ПОМИ"
Том 464, стр. 112-131
Турановские оценки для дистанционных графов в тонкой слойке
Л. Э. Шабанов
Московский Физико-технический институт (государственный унверситет), ФИВТ, Лаборатории продвинутой комбинаторики и сетевых приложений МФТИ, Институтский пер. д. 9, 141700 Долгопрудный, Россия
shabanovlev94@gmail.com
- Аннотация:
В данной работе нами получена нижняя оценка количества ребер в
дистанционном графе $\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 назв.
- Ключевые слова: дистанционный граф, число независимости, Турановские оценки
[distance graph, independence number, Tur\'an type bounds]
Полный текст(.pdf)