АННОТАЦИЯ 2
1 Введение 2
2 Постановка задачи 2
3 Основные определения и обозначения 3
4 Изучение гипотезы Эренборга (и её обобщённого варианта) 6
4.1 Случай дистанционно-наследственного графа 6
4.1.1 Точность оценки 9
4.2 Случай, когда граф не дистанционно-наследственный 9
5 Полусильный вариант неравенства для других графов 11
6 Заключение 17
7 Дальнейшие планы 17
Список литературы 19
Оценка количества остовных деревьев графа является одним из главных вопросов алгебраической теории графов. Его исследования берут начало в XIX веке, когда Г. Кирхгоф, изучая электрические цепи, получил формулу для количества остовных деревьев в терминах матричных элементов [1]. В том же веке А. Кэли были получены формулы остовных деревьев в полном и полном двудольном графе [2] (на самом деле числовая формула была получена Борхардтом, однако Кэли обобщил это равенство, доказав его для полиномиального перечислителя остовных деревьев). Также в XX веке Т. Остином [3] были получены формулы для полных многодольных графов.
Наиболее интересным вопросом является гипотеза, сформулированная Эренбергом [4] в 2004 году:
Гипотеза. Пусть G = (V1,V2,E) — двудольный граф, тогда верно следующее неравенство:
τ (G) < ∏
v∈V (G) dG(v)/|V1| · |V2|
Равенство доказано равенство для случая, когда G — граф, построенный по диаграмме Юнга. В дальнейшем были получены альтернативные доказательства этого утверждения, как, например, линейно-алгебраическое [5] или по индукции с вычислением определителя [6].
В 2012 году схожая оценка была доказана Бозкуртом [7]: если граф G двудолен, то справедлива оценка
τ (G) <∏
v∈V (G) dG(v)/e(G),
причём равенство достигается в том и только том случае, когда граф является полным двудольным.
В работе была доказана гипотеза Эренборга для класса дистанционно-наследственных графов, из неё выведено ещё одно доказательство формулы Эренборга для графов, построенных по диаграммам Юнга. Кроме того показано, что данная оценка точна в этом классе (т.е. равенство для дистанционно-наследственного графа достигается в том и только том случае, если граф является графом Феррера-Юнга).
Также приведены примеры графов, для которых „сильная " гипотеза Эренборга неверна — это чётные циклы длины хотя бы 6, а также графы, для которых гипотеза верна, но при этом они не являются дистанционно-наследственными — например, граф „домино “. Однако было доказано, что чётные циклы длины хотя бы 6 удовлетворяют „полусильному" неравенству Эренборга (и даже строгому), следовательно, все графы, получаемые из длинных циклов склеиваниями и размножениями, будут удовлетворять „полусильному " неравенству. Для числового неравенства аналогично.
Также показано, что склеивание графов по ребру сохраняет „полусильное" и „числовое" неравенства Эренборга.
