\documentclass[11pt]{article}

% корректная обработка переносов, в том числе при поиске и копировании
\defaulthyphenchar=127
\lccode`\-=`\-
\usepackage{cmap}
\newcommand\softhyphen{\char127\relax}
% также в локальную копию файла t2a.cmap внесено изменение:
%  <7F> <002D>   заменено на   <7F> <00AD>

\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{ifthen}

\pagestyle{plain}
\advance\textwidth40mm
\advance\textheight75mm
\advance\voffset-34mm
\advance\hoffset-25mm
\footskip=8mm

%%%%% NEW THEOREMS %%%%%
\newtheorem{thm}{Теорема}[section]
\newtheorem{cor}[thm]{Следствие}
\newtheorem{df}{Определение}
\newtheorem{lm}[thm]{Лемма}
\newtheorem{prop}[thm]{Предложение}

\makeatletter
\renewcommand{\abstractname}{Аннотация}

\newcommand\txt[2]{{#1{\ifthenelse{\equal {#2}{}}{}{ #2}}. }}
\def\example#1.{\txt{\bf Пример}{#1}}
\makeatother

\def\itref#1{{\it (#1)}}

\let\emp\varnothing
\let\emptyset\varnothing
\newcommand\eps\varepsilon
\newcommand\ov\widetilde
\let\ds\displaystyle

\newcommand\eop{\unskip\hfill\penalty150\hfill$\square$\par\smallskip}
\newcommand{\NN}{{\mathbb N}}

\renewcommand\refname{Список литературы}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\Remark#1.{\par\smallskip
\textbf{Замечание\ifx#1\relax\else\ #1\fi.}}


\newcounter{prob}[section]

\makeatletter
\long\def\itemm{%
  \par\medskip\noindent\refstepcounter{prob}%
  \protected@edef\@currentlabel{\thesection.\theprob}%
  \textbf{\thesection.\theprob.} }

\long\def\itemtr{%
  \par\medskip\noindent\refstepcounter{prob}%
  \protected@edef\@currentlabel{\thesection.\theprob}%
  \textbf{\thesection.\theprob.$^\triangledown$} }

\long\def\itemmstar{%
  \par\medskip\noindent\refstepcounter{prob}%
  \protected@edef\@currentlabel{\thesection.\theprob}%
  \textbf{\boldmath$\thesection.\theprob^*.$} }
\makeatother

\def\cF{{\mathcal F}}
\def\cG{{\mathcal G}}

\def\cC{{\mathcal C}}
\def\cO{{\mathcal O}}
\def\cN{{\mathcal N}}


\begin{document}

\title{Числа Хелли--Галлаи для конечных и квазиконечных множеств}
\author{И.И.~Богданов, В.Л.~Дольников, Г.Р.~Челноков }
\date{}
\maketitle

\section{Вместо введения.}

\textbf{Типичная задача.} {\it В городе работают несколько автобусных маршрутов.
Любые два маршрута имеют не более двух общих остановок. Также известно, что для
любых десяти маршрутов найдутся такие две остановки~$A$ и~$B$, что каждый из
этих десяти маршрутов проходит через хотя бы одну из~$A$ и~$B$. Докажите, что
есть такие две остановки, что каждый из маршрутов проходит через одну из них.

Докажите, что число 10 нельзя заменить на меньшее.} (См. задачу \ref{expl}б).)

\smallskip
\textbf{Если вам понятно условие этой задачи и нравятся задачи такого типа
--- вы можете при желании пропустить дальнейший вводный текст и
смело переходить к задачам.}

\medskip

В комбинаторике часто встают вопросы, при каких условиях для некоторого набора
множеств можно выбрать не очень много элементов так, чтобы каждое множество
набора содержало хотя бы один из них (такая система элементов называется
{\em трансверсалью} набора). Такие вопросы появляются, например, при изучении раскрасок
(гипер)графов (которые применяются в самых различных областях), а также во
многих связанных разделах комбинаторной геометрии. Несмотря на внимание к этой
области, многие вопросы, даже выглядящие как вполне школьные, до сих пор
являются открытыми проблемами.

{\footnotesize\smallskip

В качестве примера приведём до сих пор не доказанную (и не опровергнутую)
гипотезу Ловаса--Фабера--Эрдёша.

\textbf{Гипотеза.} \textit{В городе $n$ автобусных остановок, а любые два
автобусных маршрута имеют не более одной общей автобусной остановки (каждый
маршрут проходит хотя бы через две остановки). Докажите, что автобусные
маршруты можно так покрасить в $n$ цветов, что автобусные маршруты одного цвета
не имеют общих остановок.}

}

\smallskip

Естественно, для того, чтобы трансверсаль заданного размера для нашего набора
множеств существовала, надо, чтобы она существовала для всех его поднаборов.
Оказывается, что при некоторых условиях на семейство бывает достаточным
проверить это свойство для поднаборов фиксированного размера. Общеизвестным
примером утверждения такого типа является классическая теорема Хелли для
выпуклых множеств (см. задачу~\ref{Helly}).

\smallskip

Первая из основных целей нашего проекта --- изучение аналогичных
вопросов сначала для множеств из ограниченного числа элементов
(раздел 4). Дальнейшие разделы посвящены исследованию близких
ситуаций, когда ограничена не мощность множества, а мощность
пересечения нескольких различных множеств. Такие вопросы также
возникают, например, при исследовании пересечений алгебраических
множеств (т.е. множеств, заданных системой алгебраических
уравнений).

\medskip

Многие задачи в этом проекте являются исследовательскими, ибо ответ на них в
настоящее время неизвестен (или очень сложен). В таких случаях мы ставим вопрос
типа ``Насколько хорошую оценку вам удастся получить?'' и принимаем любые
достаточно хорошие {\bf серийные} (т.е. проходящие для бесконечного числа
значений параметров) оценки. Естественно, любые серьёзные улучшения известных
оценок в этой области достойны публикации.

\textit{\large Задачи, выданные после промежуточного финиша, отмечены треугольничком$^\triangledown$.}

\section{Введение в числа Хелли}

\itemm \label{first}
Дан конечный набор отрезков на прямой. Известно, что пересечение всех отрезков
набора пусто. Докажите, что в наборе есть два непересекающихся отрезка.

\itemm
Дано дерево (т.е. связный граф без циклов) и конечный набор его поддеревьев
(т.е. подграфов, каждый из которых --- тоже дерево). Известно, что пересечение
всех поддеревьев набора пусто. Докажите, что в наборе есть два непересекающихся
поддерева.

\itemm
Рассмотрим конечный набор дуг фиксированной окружности. Пусть любые 1000 из
этих дуг пересекаются. Докажите, что все дуги набора не обязаны пересекаться.

\bigskip
Во всех трёх задачах речь идёт об одном и том же свойстве некоторой системы
множеств (например, для задачи~\ref{first} --- это множество отрезков на
прямой). Дадим определение этого свойства.

\begin{df}
  Пусть $\cF$ --- произвольное (возможно, бесконечное) семейство множеств.
  Натуральное число $k$ называется {\em числом Хелли семейства $\cF$}, если верно следующее утверждение:

  Пусть $\cG$ --- конечный набор множеств из~$\cF$, причём пересечение всех
  множеств из~$\cG$ пусто. Тогда найдутся не более, чем $k$ множеств из~$\cG$
  такие, что уже их пересечение пусто.
\end{df}

Иначе говоря, $k$ является числом Хелли семейства~$\cF$, если выполняется
следующее ``утверждение типа Хелли'':

{\em Пусть $\cG$ --- конечный набор множеств из~$\cF$, такой, что любые $k$
множеств из~$\cG$ имеют непустое пересечение. Тогда и все множества из~$\cG$
имеют непустое пересечение.}

\medskip
В терминах этого определения первые две задачи утверждали, что число 2 является
числом Хелли для семейств отрезков на прямой и поддеревьев фиксированного
дерева. Третья же задача по сути утверждает, что что для семейства дуг
фиксированной окружности число Хелли не существует.

\begin{df}
  Пусть $\cF$ --- семейство множеств. Если для $\cF$ существует число Хелли, то
  минимальное из всех этих чисел мы будем обозначать через $H(\cF)$. Если же
  числа Хелли для~$\cF$ не существует, то мы будем писать $H(\cF)=\infty$.
\end{df}

Чтобы лучше понять определение, мы предлагаем порешать следующие задачи.

\itemm ({\sc Теорема Хелли для плоскости}) Пусть $\mathcal C$ --- семейство всех выпуклых множеств на плоскости.
Докажите, что $H({\mathcal C})=3$.
\label{Helly}

\Remark. В предыдущей задаче условие конечности набора~$\cG$ из определения можно заменить на условие, что все
множества из~$\mathcal C$ замкнуты и ограничены.

\itemm Докажите, что для семейства бесконечных возрастающих арифметических прогрессий, состоящих из натуральных чисел, число 2 является числом
Хелли.

\itemm Найдите $H(\cO)$, где $\cO$ --- семейство всех окружностей на плоскости.
(\textbf{Напоминание.} Окружность --- это не круг, а его граница!)


\section{Введение в числа Хелли--Галлаи}

Следующие определения дают естественное обобщение числа Хелли.

\begin{df}
  Пусть $\cF$ --- семейство множеств. Множество $X$ называется {\em трансверсалью} семейства $\cF$,
  если $X \cap A \neq \emptyset$ для любого $A \in F$.
  Если $|X|=t$, то $X$ называется {\em $t$-трансверсалью}.
\end{df}

\Remark. Семейство имеет 1-трансверсаль тогда и только тогда, когда все его
множества пересекаются.

\begin{df}
  Пусть $\cF$ --- семейство множеств.
  Натуральное число $k$ называется {\em $t$-числом Хелли--Галлаи семейства $\cF$}, если верно следующее утверждение:

  Пусть $\cG$ --- конечный набор множеств из~$\cF$, не имеющее $t$-трансверсали.
  Тогда найдутся не более, чем $k$ множеств из~$\cG$, не имеющие $t$-трансверсали.

  Если для $\cF$ существует $t$-число Хелли--Галлаи, то
  минимальное из всех этих чисел мы будем обозначать через $HG_t(\cF)$. Если же
  $t$-числа Хелли--Галлаи для~$\cF$ не существует, то мы будем писать $HG_t(\cF)=\infty$.
\end{df}

\Remark. Числа Хелли--Галлаи действительно являются обобщениями чисел Хелли,
ибо $H(\cF)=HG_1(\cF)$ для любого семейства~$\cF$.

\medskip
Следующие задачи опять же дают возможность разобраться с числом Хелли--Галлаи
на примерах.


\itemm Пусть $\mathcal S$ --- множество отрезков на фиксированной прямой.

а) Докажите, что 3 является 2-числом Хелли--Галлаи для~$\mathcal S$.

б) Докажите, что $t+1$ является $t$-числом Хелли--Галлаи для~$\mathcal S$.

\itemm а) Постройте пример семейства множеств~$\cF$, для которого $H(\cF)=2$, но
$HG_2(\cF)\geq 1000$.

б) Докажите, что существует такое семейство множеств~$\cF$, для которого
$H(\cF)=2$, но $HG_2(\cF)=\infty$.

\itemm \label{convHG} Докажите, что $HG_2(\cC)=\infty$. (Напомним, что $\cC$ --- семейство всех выпуклых множеств на плоскости.)

\itemmstar Пусть $\mathcal L$ --- множество всех прямых на плоскости.

а) Докажите, что $HG_t({\mathcal L})\leq t^2+1$ при $t\geq 3$.

б) Насколько можно улучшить эту оценку?


\section{Числа Хелли--Галлаи для конечных множеств}

В прошлом разделе мы видели, что числа Хелли--Галлаи не зависят напрямую от
чисел Хелли. Для того, чтобы такая зависимость имела место, нужны некоторые
дополнительные условия на рассматриваемое семейство. Одним из таких условий
является ограниченность мощности множеств в семействе. Этому посвящен данный
раздел.

\begin{df}
  Мы обозначаем через $\cN_d$ семейство множеств, состоящих из не более, чем~$d$
  элементов.
\end{df}

\itemm Пусть $\cG$ --- конечный набор множеств, каждое имеет не более~$d$
элементов. Докажите, что если любые $d+1$ множеств из~$\cG$ имеют общий
элемент, то и все множества из~$\cG$ имеют общий элемент. Докажите, что число
$d+1$ нельзя заменить на меньшее.

({\bf Упражнение на понимание.} Переформулируйте эту задачу,
используя терминологию, введённую выше.)

\itemm Докажите, что все числа виде $HG_t(\cN_d)$ конечны.

\itemm а) Докажите, что $HG_t(\cN_2)\geq C_{t+2}^2$.

б) Докажите, что $HG_t(\cN_2)= C_{t+2}^2$.

\itemm Докажите, что $HG_t(\cN_d)\geq C_{d+t}^t$.

\itemmstar ({\sc Основная задача для конечных множеств})
  \label{gen-fin}
  Докажите, что $HG_t(\cN_d)= C_{d+t}^t$.

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

\itemm а) ({\sc Задача Катоны})
  Пусть множества $A_1,A_2,\dots,A_n,B_1,\dots,B_n$ таковы, что $|A_i|=d$, $B_i=t$,
  множество $A_i$ пересекается со всеми $B_j$ при $j\neq
  i$, но $A_i\cap B_i=\emptyset$ (при произвольных индексах $1\leq i,j\leq n$).
  Докажите, что $n \le C_{d+t}^t$.

\newcounter{catona}
\setcounter{catona}{\theprob}

б) Выведите задачу \ref{gen-fin} из задачи Катоны.

\itemtr
  Пусть множества $A_1,A_2,\dots,A_n,B_1,\dots,B_n$ удовлетворяют {\em условиям Катоны},
  т.е. $A_i\cap B_i=\emp$ и $A_i\cap B_j\neq \emp$ при любых $i\neq j$.
  Положим $a_i=|A_i|$, $b_i=|B_i|$. Докажите, что
  $\displaystyle {\sum_{i=1}^n \frac1{C_{a_i+b_i}^{a_i}} \le 1}$.

\medskip
Необходимое условие на мощности множеств из предыдущей задачи не является
достаточным. Это демонстрирует следующая задача.

\itemtr Докажите, что существуют такие натуральные числа $a_1,\dots,
a_n,b_1,\dots,b_n$, что \\$\displaystyle {\sum_{i=1}^n
\frac1{C_{a_i+b_i}^{a_i}} <\frac1{10^{100}}}$, но множеств
$A_1,A_2,\dots,A_n,B_1,\dots,B_n$, удовлетворяющих условиям Катоны и таких, что
$|A_i|=a_i$, $|B_i|=b_i$, не существует.




\section{Числа Хелли--Галлаи для квазиконечных множеств}

В этом пункте мы ослабим условия конечности, накладываемые на наше
семейство~$\cF$.

\begin{df}
  Пусть $\cF$ --- семейство множеств.
  Будем говорить, что $\cF$ есть {\em семейство степени~$d$},
  если $|A\cap B|\le d$ для любых различных $A,B \in F$.

  Зафиксируем теперь произвольные натуральные числа~$d$ и~$t$.
  Для каждого семейства $\cF$ степени~$d$, рассмотрим его (минимальное) $t$-число Хелли--Галлаи~$HG_t(\cF)$.
  Обозначим через $a(d;t)$ наибольшее из всех этих чисел.
\end{df}

Иначе говоря, $a(d;t)$ --- это минимальное число, являющееся $t$-числом
Хелли--Галлаи для любого семейства~$\cF$ степени~$d$.

Этот раздел посвящён оценкам чисел~$a(d;t)$.


\itemm Дано семейство множеств~$\cF$. Пусть $|A\cap B|=1$ для любых различных $A,B \in \cF$
  (в частности, $\cF$ --- семейство степени~1).
  Пусть, кроме того, среди любых 4 множеств из $\cF$ найдутся три, имеющих непустое пересечение. Докажите,
  что из~$\cF$ можно выбросить 1 множество так, что все остальные имеют непустое пересечение.

\itemm Дано семейство множеств~$\cF$. Пусть $|A\cap B|=1$ для любых различных $A,B \in \cF$, причем в $\cF$ есть хотя бы 17 множеств.
  Пусть, кроме того, среди любых 5 множеств из $\cF$ найдутся три, имеющих непустое пересечение.
  Докажите, что $\cF$ имеет 2-трансверсаль.

\itemm Докажите, что $a(d;1)=d+2$.

\itemm а) Докажите, что $a(1;2)=6$.

б) Докажите, что $a(2;2)=10$. \label{expl}

в) Докажите, что $a(3;2)=15$.

  г) Докажите, что $a(4;2)=21$.

  д$)^*$ Для каких значений $d$ вам удастся доказать аналогичные утверждения про $a(d;2)$?

\itemm а) Докажите, что $a(d;2) \ge C_{d+3}^2$.

б) Докажите, что $a(d;2) \le 2d^2+3$ при $d\geq 2$.

в$)^*$ Насколько вам удастся улучшить эти оценки?

\Remark. В предыдущей задаче авторы умеют улучшать верхнюю оценку (т.е. оценку из части б)), но разрыв между ней и
нижней по-прежнему велик. Интересно было бы получить асимптотически одинаковые
верхнюю и нижнюю оценки, то есть оценки, отношение которых стремится к~1 при
$d\to\infty$.

\itemm а) Докажите, что $a(1;3)=10$.

б) Докажите, что $a(1;4)=15$.

в$)^*$ Для каких значений $t$ вам удастся доказать аналогичные
утверждения?

\itemm а) Докажите, что $a(1;t) \ge C_{t+2}^2$.

б) Докажите, что $a(1;t) \le t^2+1$ при $t\geq 3$.

в$)^*$ Насколько вам удастся улучшить эти оценки?

\itemm \label{genq1} а) Докажите, что $a(d;t) \ge C_{d+t+1}^t$.

б$)^{**}$ Существуют ли значения $d$, $t$, при которых неравенство в предыдущем
пункте строгое?

\Remark. Авторы не знают ответа на вопрос \ref{genq1}б).

\itemm а) Докажите, что число $a(d;t)$ конечно при любой паре $(d,t)$.

б) Насколько хорошую оценку сверху на $a(d;t)$ вам удастся получить?

\bigskip
\textit{\large Вся дальнейшая часть условий была выдана после промежуточного финиша.}

\bigskip
Следующее понятие для квазиконечных множеств аналогично условиям Катоны.

\begin{df}
  Назовём конечное семейство множеств $\cG$ {\em $(d;t)$-исключительным}, если (i) $\cG$ является
  семейством степени~$d$, и (ii) для любого $A\in\cG$ существует такое
  $t$-элементное множество~$X_A$, что $X_A\cap A=\emp$, но $X_A\cap B\neq \emp$
  для любого $B\in\cG$, отличного от~$A$.

  Обозначим через~$b(d;t)$ наибольшую мощность $(d;t)$-исключительного семейства.
  Будем говорить, что $b(d;t)=\infty$, если существуют $(d;t)$-исключительные
  семейства сколь угодно большой мощности.
\end{df}

\itemtr Докажите, что $b(d;t)\geq a(d;t)$.

\itemtr Докажите, что $b(d;t)$ конечно при всех $d$ и $t$.

\bigskip
Следующие задачи этого раздела посвящены изучению исключительных множеств.

Зафиксируем на время некоторые числа $d$, $t$, а также $(d;t)$-исключительное
семейство~$\cG$. Напомним, что для каждого $A\in\cG$ зафиксировано одно
$t$-элементное множество~$X_A$ такое, что $X_A\cap A=\emp$, но $X_A\cap B\neq
\emp$ для любого $B\in\cG$, отличного от~$A$.

\begin{df}
  Пусть $x$ "--- некоторый элемент. Обозначим через $g(x)$ количество таких множеств
  $A\in\cG$, что $x\in A$. Далее, обозначим через $h(x)$ количество таких множеств
  $A\in\cG$, что $x\in X_A$.
\end{df}

\itemtr а) Пусть $t=2$. Докажите, что $h(x)\leq d+2$ для любого $x$.

б) Пусть $t$ произвольно. Докажите, что $h(x)\leq b(d;t-1)$.

\itemtr Докажите, что $g(x)\leq b(d-1;t)$ для любого~$x$.

\itemtr Пусть $t=2$; предположим, что $h(x)\leq d$. Докажите, что $|\cG|\leq g(x)+h(x)+b(d-h(x);2)$.

\section{Числа Хелли--Галлаи для квазиконечных множеств размерности~2}

Семейства из предыдущего раздела можно рассматривать как {\em одномерные}:
пересечение любых двух из них конечно. В частности, полагая $t=1$, мы получаем
комбинаторный аналог семейства прямых. В этой связи естественно определить {\em
двумерные} семейства следующим образом.

\begin{df}
  Пусть $\cF$ --- семейство множеств. Рассмотрим семейство $\cF'$, состоящее из
  всех попарных пересечений различных множеств из~$\cF$, то есть
  $$
    \cF'=\{A\cap B\;:\; A,B\in\cF,\;A\neq B\}.
  $$
  Будем говорить, что $\cF$ есть {\em двумерное семейство степени~$d$},
  если~$\cF'$ --- (одномерное) семейство степени~$d$.

  Зафиксируем теперь произвольные натуральные числа~$d$ и~$t$.
  Для каждого двумерного семейства $\cF$ степени~$d$, рассмотрим его (минимальное) $t$-число Хелли--Галлаи~$HG_t(\cF)$.
  Обозначим через $a_2(d;t)$ наибольшее из всех этих чисел.
\end{df}

Мы не предлагаем настолько же развёрнутую программу, как для одномерных
множеств. Вместо этого мы предлагаем всем желающим поисследовать значения
$a_2(d;t)$ самостоятельно. Мы готовы принимать любые результаты об этих числах.
Задачи ниже лишь намечают возможные естественные направления исследования.

\itemtr Докажите, что все числа $a_2(d;t)$ конечны.

\itemtr Пусть $d=0$. Дайте самостоятельно требуемые определения и докажите, что $g(x)\leq t+1$.

\itemtr ({\sc исследовательская, <<без вторичных пересечений>>}) Выясните как можно больше о числах
$a_2(0;t)$ при различных значениях~$t$.

\itemtr ({\sc исследовательская, <<случай плоскостей>>}) Выясните как можно больше о числах
$a_2(1;t)$ при различных значениях~$t$.

\itemtr ({\sc исследовательская, общий случай}) Выясните как можно больше о числах
$a_2(d;t)$ при различных значениях параметров~$d$ и~$t$.

\Remark. В последних трёх задачах предпочтение отдаётся серийным оценкам (т.е. оценкам, справедливым
для бесконечного множества значений параметра~$t$). Тем не менее, мы
настоятельно рекомендуем вам начать с рассмотрения достаточного количества
частных случаев.

\end{document}


