Треугольник в ориентированном графе

[Sasha Rybak]

Придумал задачку, а решить не могу... :) Приветствую ссылки на внешние источники, а также частичные продвижения.

В ориентированном графе 3n вершин. Из каждой вершины выходит по n стрелок в ДРУГИЕ вершины. Каждую пару вершин соединяет максимум одна стрелка. Верно ли, что в графе обязательно найдётся ориентированный цикл длины 3?

[Руст]

Если разрешаются стрелки из вершины в саму вершину, то это не верно.

[maxal]

Sasha Rybak писал(а):

В ориентированном графе 3n вершин. Из каждой вершины выходит по n стрелок в ДРУГИЕ вершины. Каждую пару вершин соединяет максимум одна стрелка. Верно ли, что в графе обязательно найдётся ориентированный цикл длины 3?

Можно этой задаче придать "количественный" вид. Пусть $m(n)$ - минимальное число вершин в графе, где из каждой вершины выходит по $n$ стрелок в ДРУГИЕ вершины, каждую пару вершин соединяет максимум одна стрелка и нет ориентированных циклов длины 3. Ваша задача эквивалентна неравенству $m(n)>3n$.
Отсюда получается интересное следствие.

Легко можно доказать, что $m(n)\leq 3n+1$, что вместе с $m(n)>3n$ влечет $m(n)=3n+1$. Таким образом, исходная задача равносильна $m(n)=3n+1$.

[TOTAL]

Sasha Rybak писал(а):

Придумал задачку, а решить не могу... Приветствую ссылки на внешние источники, а также частичные продвижения.

В ориентированном графе 3n вершин. Из каждой вершины выходит по n стрелок в ДРУГИЕ вершины. Каждую пару вершин соединяет максимум одна стрелка. Верно ли, что в графе обязательно найдётся ориентированный цикл длины 3?

$n=2$
$1 - 2 - 3 - 4 - 5 - 6 - 1$
Нету треугольника.

[maxal]

TOTAL писал(а):

$n=2$
$1 - 2 - 3 - 4 - 5 - 6 - 1$
Нету треугольника.

И где тут стрелки?

[TOTAL]

maxal писал(а):

TOTAL писал(а):

$n=2$
$1 - 2 - 3 - 4 - 5 - 6 - 1$
Нету треугольника.

И где тут стрелки?

Если такой вопрос, то подозреваю, что я не понял условие.
Я подумал, что каждая вершина соединена ровно с $n$ другими.
Видимо, требуется, чтобы из каждой вершины исходило ровно $n$ стрелок,
и разрешается, чтобы в саму вершину, входило еще сколь угодно стрелок.

[maxal]

TOTAL писал(а):

Видимо, требуется, чтобы из каждой вершины исходило ровно $n$ стрелок, и разрешается, чтобы в саму вершину, входило еще сколь угодно стрелок.

Именно!

[maxal]

О! Подсказали тут в рассылке SeqFan:

Оказывается, рассматриваемая задача - это частный случай следующей гипотезы:

Caccetta-Häggvist Conjecture: В каждом простом ориентированном графе с $n$ вершинами, чьи полустепени исхода не меньше $r$, существует цикл длины как минимум $\lceil n/r\rceil$.

В общем виде гипотеза доказана для $r\leq\sqrt{n/2}$, но нас интересует случай $r=n/3$ - и это открытая проблема. Более того, вопрос также открыт в случае, когда снизу числом $n/3$ ограничены полустепени и исхода, и захода.

Ссылки по теме:
http://www.math.uiuc.edu/~west/openp/cacchagg.html
http://www.aimath.org/WWN/caccetta/caccetta.pdf

[maxal]

Предагаю к рассмотрению более простой вариант. Пусть граф трехдольный с долями $A, B, C$, причем доли равномощны ($|A|=|B|=|C|$) стрелки идут только из $A$ в $B$, из $B$ в $C$ и из $C$ в $A$. Как в этом случае связаны полустепень исхода вершин и их минимальное количество?

[maxal]

Или как насчет такого следствия:

Пусть $(G,+)$ абелева группа, $|G|=3n$. Тогда в любом подмножестве $S\subset G$, $|S|=n$ найдется не более трех элементов (возможно равных), дающих в сумме 0.

Можно ли его как-то просто доказать?

[Sasha Rybak]

Спасибо, maxal, за ссылки!!! Буду знать, с чем имею дело. :)

Только не понимаю, как последняя задача (о группе) может следовать из задач о графе???

Сама задача решается через теорему Кнезера, которая утверждает, что если $A_1, ..., A_k$ - непустые подмножества абелевой группы $G$, то их сумма $M=A_1+...+A_k=\{a_1+...+a_k\ |\ a_1 \in A_1, ..., a_k \in A_k\}$ удовлетворяет одному из следующих условий:
либо $|M| \ge min\{|A_1|+...+|A_k|-k+1,\ |G|\}$,
либо $M$ является объединением классов смежности по некоторой подгруппе $H$, содержащей более одного элемента.

Теорема Кнезера является обощением известной теоремы Коши-Дэвенпорта об аналогичной оценке для $G=Z_p$. Её доказательство сложно в техническом плане. Оно занимает страницы 29-37 (15-23 в авторской нумерации) в следующем источнике: http://etd.caltech.edu/etd/available/etd-08102005-190712/unrestricted/Dissertationv1.pdf
У меня были сложности при непосредственном открытии файла, поэтому легче выйти на него по ссылке: http://etd.caltech.edu/etd/available/etd-08102005-190712/, а затем загрузить файл Dissertationv1.pdf в левом нижнем углу.

Теперь к нашей задаче. Интересен случай $0 \notin S$. Применим теорему Кнезера к $A_1=A_2=S \cup \{0\},\ A_3=S$. Если $M=A_1+A_2+A_3$ - не объединение нетривиальных классов смежности, то $|M|=|G|$. В противном случае, пусть H - наибольшая группа, для
которой M - объединение классов смежности по H. (Несложно показать, что такая наибольшая группа существует.) Заменим каждый элемент на его класс смежности в G/H. Отметим, что $A_3/H$ НЕ БУДЕТ содержать 0/H (то есть самой H)!!! Иначе в M присутствовал бы элемент из H, а это означало бы $0 \in H \subset M$.
Пусть h=|H|. Тогда $|A_3/H| \ge n/h$, и $|A_1/H|=|A_2/H|=|A_3/H|+1 \ge n/h+1$. Следовательно, по теореме Кнезера для $G/H$: $|M/H| \ge |A_1/H|+|A_2/H|+|A_3/H|-2 \ge 3n/h=|G/H|$. В любом случае, $0 \in M$.

[maxal]

Sasha Rybak писал(а):

Только не понимаю, как последняя задача (о группе) может следовать из задач о графе???

Пусть $(G,+)$ - группа и $S$ - ее подмножество, где $|S|=|G|/3=n$. Рассмотрим граф, вершинами которого являются элементы $G$, а стрелки ведут из $x$ в $x+s$ для каждого $x\in G$ и каждого $s\in S$.
А теперь примените к этому графу ваше исходное утверждение о наличии ориентированных циклов длины 3...

[maxal]

maxal писал(а):

Пусть $(G,+)$ абелева группа, $|G|=3n$. Тогда в любом подмножестве $S\subset G$, $|S|=n$ найдется не более трех элементов (возможно равных), дающих в сумме 0.

А есть ли простое доказательство аналогичного утверждения для неабелевой группы?