Аннотация 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
Оценка количества остовных деревьев графа является одним из главных вопросов алгебраической теории графов. Его исследования берут начало в XIX веке, когда Г. Кирхгоф, изучая электрические цепи, получил формулу для количества остовных деревьев в терминах матричных элементов. В том же веке А. Кэли были получены формулы остовных деревьев в полном и полном двудольном графе(на самом деле числовая формула была получена Борхардтом, однако Кэли обобщил это равенство, доказав его для полиномиального перечислителя остовных деревьев). Также в XX веке Т. Остином были получены формулы для полных многодольных графов.
Наиболее интересным вопросом является гипотеза, сформулированная Эренбергом в 2004 году:
Гипотеза. Пусть G = (V1,V2,E) — двудольный граф, тогда верно следующее неравенство:
П dG(v) {(G Т(G) 6 |vi|.|V2|
Равенство доказано равенство для случая, когда G — граф, построенный по диаграмме Юнга. В дальнейшем были получены альтернативные доказательства этого утверждения, как, например, линейно-алгебраическое или по индукции с вычислением определителя.
В 2012 году схожая оценка была доказана Бозкуртом: если граф G двудолен, то спра-
ведлива оценка
П dG(v)
^(G< v2V(G) Т(G) 6 (r,x ;
e(G)
причём равенство достигается в том и только том случае, когда граф является полным двудольным.
Постановка задачи
В работе предлагается исследовать полиномиальный вариант гипотезы Эренборга:
Гипотеза. Пусть G = (Vi , V2, Е) — двудольный граф, X[1,,m] — переменные, соответствующие вершинам доли V1, У[1::П] — соответствующие вершинам доли V2. Тогда справедливо следующее неравенство:
Tpoi(G) ■ ^Xx^ ■ (хj 6 П@ X yfcA ■ П @ X XiA
Под неравенством подразуемваются следующие варианты:
• „сильное": для любого монома коэффициент в левой части не превосходит коэффициента в правой части;
• „по л усильное": существует многочлен с неотрицательными коэффициентами такой, что при домножении обеих частей неравенства на него будет выполняться сильное неравенство;
• „числовое": неравенство верно при подстановкелюбых неотрицательных чисел вместо каждой переменной.
Мы изучим это неравенство для класса дистанционно-наследственных графов, а также проверим её точность на графах Феррера-Юнга. Также мы найдём семейство графов, для которых сильное неравенство не выполняется, но при этом выполняются другие два.
В работе была доказана гипотеза Эренборга для класса дистанционно-наследственных графов, из неё выведено ещё одно доказательство формулы Эренборга для графов, построенных по диаграммам Юнга. Кроме того показано, что данная оценка точна в этом классе (т.е. равенство для дистанционно-наследственного графа достигается в том и только том случае, если граф является графом Феррера-Юнга).
Также приведены примеры графов, для которых „сильная " гипотеза Эренборга неверна — это чётные циклы длины хотя бы 6, а также графы, для которых гипотеза верна, но при этом они не являются дистанционно-наследственными — например, граф „домино “. Однако было доказано, что чётные циклы длины хотя бы 6 удовлетворяют „полусильному" неравенству Эренборга (и даже строгому), следовательно, все графы, получаемые из длинных циклов склеиваниями и размножениями, будут удовлетворять „полусильному " неравенству. Для числового неравенства аналогично.
Также показано, что склеивание графов по ребру сохраняет „полусильное" и „числовое" неравенства Эренборга.
