Изменения

Перейти к: навигация, поиск

Гипотеза Хивуда

450 байт добавлено, 20:40, 31 декабря 2019
Теорема о нижней границе хроматического числа поверхности
|proof=
В качестве доказательства воспользуемся теоремой Рингеля и Янгса о минимальном роде поверхности, Воспользуемся формулой Эйлера <tex>V + F - E = 2 - 2n</tex>. Давайте докажем нижнюю границу на которую можно уложить <tex>E</tex>. Максимизируем число граней: каждая из них может быть треугольником. Тогда для <tex>E</tex> существует неулучшаемая нижняя граница: <tex>E \geqslant 3 \left( V - 2 + 2n \right)</tex> <tex>n \geqslant \dfrac{1}{6} E - \dfrac{1}{2} \left( V - 2 \right)</tex>. Рассмотрим полный граф <tex>K_p</tex>, а именно тогда получаем, что <tex>\gamma \left( K_p \right) \geqslant \dfrac{1}{6} \dfrac{p (p - 1)}{2} - \dfrac{p - 2}{2}</tex> <tex>n = \gamma \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>.
}}
Анонимный участник

Навигация