\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{fullpage}
\usepackage{mathtools}

%\DeclarePairedDelimiter \ceil {\left \lceil} {\right \rceil}
%\DeclarePairedDelimiter \floor{\left \lfloor}{\right \rfloor}

\def\lc{\left\lceil}   
\def\rc{\right\rceil}
\def\lf{\left\lfloor}   
\def\rf{\right\rfloor}
%\newtheorem{theorem}{Теорема}[section]



\title{Идеи по гиперграфам}
\author{Данила Черкашин}
\date{July 2016}

\begin{document}

\maketitle

\begin{abstract}
Хочется плюнуть на все эти новомодные оценки на функции от трех переменных и нечисть из компутер сциенце, и ВЕРНУТЬСЯ К ИСТОКАМ.
Хочется, да не можется.
\end{abstract}


\section{Введение}
В статье Эрдеша и Ловаса (приложена к проекту) сформулировано огромное количество базовых вопросов, по которым нет никакого прогресса.
Я приведу здесь наиболее перпективные из них с комментариями, а также немного поговорю о старом. Мы всегда будем говорить об $n$-однородных гиперграфах.


\section{Из Эрдеша-Ловаса}

\subsection{Пример недвуцветной клики}

Очевидно, хроматическое число клики равно двум или трем, интересна верхняя оценка на число ребер в клике с хроматическим числом 3.
Никаких вероятностых методов строить клику я не знаю, у Эрдеша и Ловаса пример получается итерированием плоскости Фано (конкретного гиперграфа на 7 вершинах).
У любителей побаловаться программированием есть хорошая возможность строить случайный $k$-однородный гиперграф-клику при $k \in \{6, 7\}$ и с неплохой вероятностью побеждать, итерируя новый граф.


\subsection{Минимальное количество ребер в нетривиальной клике}

Возможно, можно, скажем, показать, что в ней не очень много 2-цепей, тогда будет оценка нетривиальнее, чем в на $m(n)$.
Но что-то пока ничего не получается. Единственное, что удается доказать, что либо 2 ребра сильно пересекаются, либо ребер побольше, либо вершин не невероятно много. Но все это очень жалко выглядит.


\subsection{Максимальное количество ребер в нетривиальной клике}

Не будем отбирать хлеб у Андрюши, захочет -- сам расскажет. 


\subsection{Пересечение ребер в нетривиальной клике}

Я поискал и не нашел вообще никаких результатов по этой теме. Есть вопрос про множество мощностей пересечений пар ребер. Каким оно может быть? Эрдеш и Ловас показали, что
в нем всегда есть единица, что оно не может иметь мощность 2 при растущем $n$. Но неясно даже растет ли мощность с ростом $n$ (оценка сверху $n/2$, пример --- снова перемножение плоскостей Фано).

Также, ясно, что максимальное пересечение хотя бы $n/\log(n)$. Но примеров, где нет пересечений размера больше чем $n-2$ никто не видел (снова привет программистам).
При этом тут возможен какой-то вагон результатов. 

У меня есть какие-то идеи про это, но я думаю, что понадобится принципиально новый метод. 

Попробую изложить идеи. Пусть мощность множества мощностей пересечений пар ребер меньше какой-то константы $m$.
Можно писать что-то в духе
$$|E| < \#monoms < C^m_n |E|.$$
Первая оценка --- линал, вторая --- если посмотреть на полиномы, то видно, что там появляются только мономы, 
являющиеся подмножествами ребер.
Кажется, это неплохое основание для Фурье.

\textbf{Вообще, про все эти клики есть несколько принцпиальных возможностей: либо проблемы чисто технические, что не работает вероятностный метод, но можно как-то обойти; либо можно придумать пару идей и все решится; либо это гробак. В последнее я не верю.}


\section{СТАРЫЕ ПЕСНИ О ГЛАВНОМ}

А теперь хочется пооценивать $m(n, r)$ снизу при $r$ стремящемся к бесконечности. Все лучшие оценки рано или поздно оценивают сверху количество $r$-цепей.
\begin{itemize}
\item Очевидная оценка $|E|^r/r!$.
\item Простая оценка $|E|^r/(r-1)^{r-1}$.
\item Вырожденый пример на $(|E|/r)^r$.
\end{itemize}

Простая оценка дает итоговый апгрейд всех оценок в константу раз при $r > 2$. Например, при $n = 3, r \rightarrow \infty$ верхняя и нижняя оценка различаются в константу раз, так что и это не совсем глупо.

Есть мнение, что можно придумать несложную идею, которая показывает, что либо $r$-цепи сильно зависимы в плохую сторону, либо их меньше. Возможно, это даже сработает при $r = 2$.
Может быть имеет смысл с группировать $r$-цепи по вершинам из пересечений ребер, а дальше как-то сказать, что если распределение
по соответствующим множествам из $r-1$ вершины равномерное, то цепей мало, а если нет --- оценка на вероятность не сумма, а получше. И это снова очень напоминает Фурье.


\input{India/small_n.tex}

\end{document}