\documentclass[11pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english]{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}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{df}{Definition}
\newtheorem{lm}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}


\makeatletter
\renewcommand{\abstractname}{Abstract}

\newcommand\txt[2]{{#1{\ifthenelse{\equal {#2}{}}{}{ #2}}. }}
\def\example#1.{\txt{\bf Example}{#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{References}

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

\def\Remark#1.{\par\smallskip
\textbf{Remark\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}}
\def\cP{{\mathcal P}}


\begin{document}

\title{The Helly--Gallai numbers for the families of finite and quasi-finite sets}
\author{I.I.~Bogdanov, G.R.~Chelnokov, V.L.~Dolnikov}
\date{}
\maketitle

\section{Introduction}

\textbf{Typical problem.} {\it In a city there are some bus routes. Every
two routes have at most two common bus stops. Moreover, for each 10~routes
there exist two stops $A$ and $B$ such that each among out ten routes passes
through at least one of the stops~$A$ and~$B$. Prove that there exist two stops
such that each route in the city passes through at least one of them.

Also show that the problem statement does not remain valid after replacing the
number~10 by a smaller number.} (See problem \ref{expl}b).)

\smallskip
\textbf{If you are familiar with this type of problems (and you like them) you may skip
the preliminary text and just start working on the problems.}

\medskip
One of the widespread types of questions in combinatorics is the following one.
Given a family~$\cF$ of sets, we need to determine whether it is possible to
select few elements (usually a prescribed number of them) so that each set
in~$\cF$ contains at least one selected element. (Such selection is called a
{\em transversal} for~$\cF$.) Such questions are important, for instance,
in investigating the colorings of (hyper)graphs (and thus have applications in
many areas of mathematics); also such questions are very popular in convex
geometry. Despite the popularity of this type of questions, many of them are
still unsolved, sometimes even those looking quite innocent.

{\footnotesize\smallskip

As an example, we present a known Erd\"os--Faber--Lovasz conjecture which is
neither proved nor disproved at the present moment.

\textbf{Conjecture.} \textit{In a city there are some bus routes and $n$ bus
stops. Suppose that each route passes through at least two stops, and each two
routes have at most one stop in common. Then all the routes can be colored
in$n$ colors so that no two routes of the same color have a common station.}

}

\smallskip
Obviously, the necessary condition for the certain family of set to have a
transversal of fixed size is that each its subfamily also has such a
transversal. For some special kinds of families, it is sufficient to verify
this condition for all the subfamilies of a certain size. The famous result of
this type is Helly's theorem for planar convex sets (see problem~\ref{Helly});
it deals with the 1-transversals.

\smallskip
The first our principal goal is to investigate this type of questions for the
families of sets of bounded finite cardinality (section 4). The next goal is to
generalize these results for the case of families of sets with some finiteness
conditions for their intersections. This type of families is important, e.g.,
since the conditions of such kind hold for the {\em algebraic} sets (i.e. the
sets of solutions of certain systems of algebraic equations).


\medskip

The solution of some problems in this project is not known at the present
moment. In this case we ask the question of the type ``How far can you improve
the estimate?''. For such type of problems, we accept any
{\bf serial} bound (that is, a bound that works for infinite
number of values of parameters). Please keep in mind that serious improvement
of known results in this area is worth being published.

\textit{\large The problems marked by the triangle sign$^\triangledown$ were
given at the semifinal.}

\section{Introduction to the Helly numbers}

\itemm \label{first}
Consider a family of segments in a line. Suppose that the intersection of all
segments of this family is empty. Prove that there exist two segments in this
family, such that their intersection is empty.

\itemm
Consider a tree~$G$ (i.e. a connected graph without cycles). Consider the
finite family of connected subgraphs of $G$ such that the intersection of all
these subgraphs is empty. Prove that there exist two subgraphs in this family,
such that their intersection is empty.

\itemm
Consider a finite family of arcs of some fixed circle. Suppose that every 1000
arcs of this family have a nonempty intersection. Show that all the arcs of the
family do not necessarily have a nonempty intersection.

\bigskip
All the three problems above deal with the same property of some family of
sets; for instance, in problem~\ref{first} we work with the family of all
segments in the line. Now we define the property.

\begin{df}
    Let $\cF$ be some  (not necessarily finite) family of sets. A
    positive integer $k$ is called a {\em Helly number} for the family
    $\cF$ if the following statement holds:

  Let $\cG$ be an arbitrary finite subfamily of~$\cF$. Suppose that the
  intersection of all sets in~$\cG$ is empty. Then there exist at most $k$~sets
  in~$\cG$ such that their intersection is empty.
\end{df}

In other words, $k$ is a Helly number of the set $\cF$ if the following ``Helly
type statement'' takes place:

{\em Let $\cG$ be an arbitrary finite subfamily of~$\cF$. Assume that for
every $k$ sets in~$\cG$, their intersection is nonempty. Then the intersection
of all the sets in~$\cG$ is also nonempty.}

\medskip
Using the introduced notation, one can reformulate the problems 1.1--1.2 as
follows: number~2 is a Helly number for both the family of the segments in a
line and the family of all subtrees of some fixed tree. The statement of
problem~1.3, after a similar reformulation, claims that there is no Helly
number for the family of all he arcs of a fixed circle.

\begin{df}
  Let~$\cF$ be a family of sets. We write $H(\cF)=k$ if $k$ is the minimal
  Helly number for the family~$\cF$ (provided that there exists some Helly number
  for~$\cF$). If there is no Helly number for~$\cF$, then we write
  $H(\cF)=\infty$.
\end{df}

The next problems will help you to get acquainted with the Helly numbers.

\itemm
({\sc Helly's theorem for the convex sets in the plane.}) Let $\mathcal C$ be
the family of all convex sets in the plane. Prove that $H({\mathcal C})=3$.
\label{Helly}

\Remark. For the problem above,
the condition that the family $\cG
\subset {\mathcal C}$ is finite (in Definition~1) may be replaced
with the condition that all sets of ${\mathcal C}$ are closed and bounded.


\itemm
Let $\cP$ be the family of all infinite increasing arithmetic progressions
consisting of positive integers. Prove that $H(\cP)=2$.

\itemm Let $\cO$ be the set of all the circumferences in the plane. Find
$H(\cO)$. (\textbf{Reminder.} A circumference is a boundary of a disk in the
plane.)


\section{Introduction to the Helly--Gallai numbers}

We need a bit more general concept than the Helly numbers.

\begin{df}
   Let $\cF$ be a family of sets. A set $X$ is {\em a
   transversal} for the family $\cF$ if $X \cap A \neq \emptyset$ for
   all $A \in \cF$. A transversal~$X$ is called a {\em $t$-transversal} if $|X|=t$.
\end{df}

\Remark. For any family $\cF$, the existence of a 1-transversal is equivalent to the condition that the intersection of
all sets of~$\cF$ is nonempty.

\begin{df}
  Let $\cF$ be a family of sets. A positive integer $k$ is called a {\em $t$-Helly--Gallai number} for~$\cF$  if the following statement holds:

  Let $\cG$ be an arbitrary finite subfamily of~$\cF$. Suppose that there is no $t$-transversal for $\cG$.
  Then there exists a subfamily of at most $k$~sets in~$\cG$ also admitting no $t$-transversal.

  Next, if there exists a $t$-Helly--Gallai number for a family~$\cF$, then we will denote by $HG_t(\cF)$ the minimal such number.
  Otherwise we write $HG_t(\cF)=\infty$.
\end{df}

\Remark. Note that by definition we have $H(\cF)=HG_1(\cF)$, so the new concept is a generalization
of the Helly numbers introduced above..

\medskip
Again, the next problems aim to help to get acquainted with a new notion.

\itemm Let $\mathcal S$ be the family of segments in the line.

a) Prove that $HG_2(\mathcal S)=3$

b) Prove that $HG_t(\mathcal S)=t+1$.

\itemm а) Construct a family~$\cF$ such that $H(\cF)=2$
but $HG_2(\cF)\geq 1000$.

b) Prove that there exists a family~$\cF$ such that $H(\cF)=2$ but
$HG_2(\cF)=\infty$.


\itemm \label{convHG} Prove that $HG_2(\cC)=\infty$. (Recall that $\cC$ is the family of all convex sets in the plane.)

\itemmstar Denote by~$\mathcal L$ the family of all the lines in the plane.

a) Prove that $HG_t({\mathcal L})\leq t^2+1$ for all $t\geq 3$.

b) How far can you improve this bound?

\section{Families of sets of bounded cardinality and their Helly--Gallai numbers}

One can see from the previous section that the existence of a finite Helly number for
some family $\cF$ does not necessarily imply that the Helly--Gallai numbers
of this family are finite. Thus, one needs some additional conditions on the family~$\cF$.
One of such natural conditions is the boundedness of all the cardinalities of the sets in~$\cF$.

\begin{df}
  Denote by $\cN_d$ the family of all sets having at most $d$~elements each.
\end{df}

\itemm Let $\cG$ be some finite family of sets having at most $d$~elements each.
Suppose that every $d+1$ sets of $\cG$ have a nonempty
intersection. Prove that the intersection of all the sets of $\cG$ is
nonempty.

Moreover, show that in the previous statement, the number $d+1$ can not be replaced with $d$.

{Comprehension exercise.} Reformulate this problem with the use of
terminology introduced above.

\itemm Prove that all the numbers of the form $HG_t(\cN_d)$ are finite.

\itemm a) Prove that $HG_t(\cN_2)\geq C_{t+2}^2$.

b) Prove that $HG_t(\cN_2)= C_{t+2}^2$.

\itemm Prove that $HG_t(\cN_d)\geq C_{d+t}^t$.

\itemmstar ({\sc The principal result of this section})
\label{gen-fin} Prove that $HG_t(\cN_d)= C_{d+t}^t$.

\medskip
The problem above is tough. The next problem may be used as a hint.

\itemm a) ({Katona's problem})
  Assume that the sets $A_1,A_2,\dots,A_n,B_1,\dots,B_n$ are chosen so that
  $|A_i|=d$, $|B_i|=t$, for $i\neq j$ the set $A_i$ has at least one common element with the set~$B_j$,
  but $A_i\cap B_i=\emptyset$.  Prove that $n \le C_{d+t}^t$.

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

b) Assuming that Katona's problem is solved, prove the problem~\ref{gen-fin}.

\itemtr
  Assume that the sets $A_1,A_2,\dots,A_n,B_1,\dots,B_n$ satisfy {\em Katona's
  conditions}, i.e. $A_i\cap B_i=\emp$ and $A_i\cap B_j\neq \emp$ for all $i\neq j$.
  Let  $a_i=|A_i|$, $b_i=|B_i|$. Prove that
  $\displaystyle \sum_{i=1}^n \frac1{C_{a_i+b_i}^{a_i}} \le 1$.

\medskip
The previous problem presents the constraints for the cardinalities of the sets
satisfying Katona's conditions. The next problem shows that this constraint is
far from being sufficient.

\itemtr Prove that there exist positive integers $a_1,\dots,
a_n,b_1,\dots,b_n$ such that (i) $\displaystyle \sum_{i=1}^n
\frac1{C_{a_i+b_i}^{a_i}} <\frac1{10^{100}}$, but (ii) there are no sets
$A_1,A_2,\dots,A_n,B_1,\dots,B_n$ satisfying Katona's conditions such that
${|A_i|=a_i}$, $|B_i|=b_i$.

\section{The Helly--Gallai numbers for the quasi-finite sets}

In this section we weaken the conditions for the families considered.

\begin{df}
  Let~$\cF$ be a family of sets. We say that $\cF$ is a {family of degree~$d$}
  if for every two distinct sets~$A,B \in F$ we have $|A\cap B|\le d$.

  Now let us fix arbitrary positive integers~$d$ and~$t$.
  Next, for every family $\cF$ of degree~$d$ let us find its (minimal)
  $t$-Helly--Gallai number~$HG_t(\cF)$.
  Denote by~$a(d;t)$ the maximal among these numbers.
\end{df}

In other words, $a(d;t)$ is a minimal number which is a Helly--Gallai number
for every family~$\cF$ of degree~$d$.

This section is devoted to different bounds for the numbers~$a(d;t)$;

\itemm
  Let~$\cF$ be a family of sets. Suppose that $|A\cap B|=1$ for every distinct~$A,B \in \cF$
  (in particular, this condition implies that $\cF$ is a family of degree~1).
  Suppose, in addition, that among any four sets in~$\cF$,  there exists three
  sets having a nonempty intersection. Prove that one can delete
  one of the sets from~$\cF$ so that all the remaining sets will have a nonempty
  intersection.

\itemm Let~$\cF$ be a family of sets. Suppose that $\cF$ contains at least 17~sets, and
  for every distinct $A,B\in\cF$ we have $|A\cap B|=1$.
  Moreover, suppose that among any 5 sets in~$\cF$, there are three sets
  with a nonempty intersection. Prove that there exists a 2-transversal
  for~$\cF$.

\itemm Prove that $a(d;1)=d+2$.

\itemm a) Prove that $a(1;2)=6$.

b) Prove that $a(2;2)=10$. \label{expl}

c) Prove that $a(3;2)=15$.

d) Prove that $a(4;2)=21$.

e$)^*$ Try to prove the analogous statement for some larger values
of~$n$.

\itemm a) Prove that $a(d;2) \ge C_{d+3}^2$.

b) Prove that $a(d;2) \le 2d^2+3$ for all $d\geq 2$.

c$)^*$ How far can you improve these bounds?

\Remark. In the problem above, the authors can improve the upper bound (that
from part b)), but still there is a substantial gap between the upper and the
lower bounds. It would be very interesting to obtain upper and lower bounds
which are asymptotically the same; that is, their ratio should tend to~1 as
$d\to\infty$.

\itemm a) Prove that $a(1;3)=10$.

b) Prove that $a(1;4)=15$.

c$)^*$ For which values of~$t$ you can prove the analogous
statement?

\itemm a) Prove that $a(1;t) \ge C_{t+2}^2$.

b) Prove that $a(1;t) \le t^2+1$ for all $t\geq 3$.

c$)^*$ How far can you improve these bounds?

\itemm \label{genq1} a) Prove that $a(d;t) \ge C_{d+t+1}^t$.

b$)^{**}$ Do there exist the values of~$d$ and~$t$ such that the
inequality in a) is strict?

\Remark. The authors do not know the answer for~\ref{genq1}б).

\itemm a) Prove that the number~$a(d;t)$ is finite for every pair~$(d,t)$.

b) Try to obtain a good\footnote{as good as possible\dots} bound for
the number~$a(d;t)$.

\textit{\large The remaining part of the text was given at the semifinal.}

\bigskip
The next notion for the quasi-finite sets is analogous to Katona's conditions.

\begin{df}
  Let $\cG$ be a finite family of sets. We say that $\cG$ is {\em $(d;t)$-exceptional}
  if (i) $\cG$ is a family of degree~$d$, and (ii) for every $A\in\cG$ there exists a
  set~$X_A$ with $|X_A|=t$ such that $X_A\cap A=\emp$ but $X_A\cap B\neq \emp$
  for all $B\in\cG$ different from~$A$.

  Denote by~$b(d;t)$ the maximal cardinality of a $(d;t)$-exceptional family.
  (We set $b(d;t)=\infty$ if there exist $(d;t)$-exceptional families of an
  arbitrary large cardinality.)
\end{df}

\itemtr Prove that $b(d;t)\geq a(d;t)$.

\itemtr Prove that the number $b(d;t)$ is finite for all $d$ and~$t$.

\bigskip
The next problems in this section are devoted to the investigation of
exceptional families.

From now on, we fix positive integers~$d$ and~$t$; we also fix some
$(d;t)$-exceptional family~$\cG$. Recall that for every~$A\in\cG$ we fix one
set $X_A$ such that $|X_A|=t$, $X_A\cap A=\emp$, but $X_A\cap B\neq
\emp$ for all $B\in\cG$ distinct from~$A$.

\begin{df}
  Let $x$ be some element. Denote by $g(x)$ the number of the sets
  $A\in\cG$ such that $x\in A$. Denote by $h(x)$ the number of the sets
  $A\in\cG$ such that $x\in X_A$.
\end{df}

\itemtr a) Assume that $t=2$. Prove that $h(x)\leq d+2$ for every~$x$.

b) Prove that $h(x)\leq b(d;t-1)$ (for an arbitrary~$t$).

\itemtr Prove that $g(x)\leq b(d-1;t)$ for every~$x$.

\itemtr Assume that $t=2$ and $h(x)\leq d$. Prove that $|\cG|\leq g(x)+h(x)+b(d-h(x);2)$.

\section{The Helly--Gallai numbers for the two-dimensional quasi-finite sets}

The families considered in the previous section may be regarded as {\em
1-dimensional} since the intersection of any two of them is finite. In
particular, setting $t=1$ we get a combinatorial analogue of a family of lines.
In the same way, we may define {\em 2-dimensional} families as follows.

\begin{df}
  Let $\cF$ be a family of sets. Let $\cF'$ be the family of all the
  intersections of two distinct elements from~$\cF$, i.e.
  $$
    \cF'=\{A\cap   B\;:\; A,B\in\cF,\;A\neq B\}.
  $$
  We say that~$\cF$ is a {\em 2-dimensional family of degree~$d$} if~$\cF'$ is
  a (1-dimensional) family of degree~$d$.

  Now let us fix some positive integers~$d$ and~$t$. For every 2-dimensional
  family~$\cF$ of degree~$d$, consider its (minimal) $t$-Helly--Gallai number~$HG_t(\cF)$.
  Denote by~$a_2(d;t)$ the maximal such number.
\end{df}

In this section, we do not propose an explicit investigation agenda. Instead of
that, we propose you to investigate the numbers~$a_2(d;t)$ by yourself. We will
accept all the results about these numbers. The problems below mark only some
natural directions of investigation.

\itemtr Prove that all the numbers $a_2(d;t)$ are finite.

\itemtr Assume that $d=0$. Give the necessary definitions on your own
and prove that $g(x)\leq t+1$.

\itemtr ({\sc investigatory, ``with no double intersections''})
Find some upper and lower bounds for the numbers $a(0;t)$ for some values
of~$t$.

\itemtr ({\sc investigatory, ``the case of planes''})
Find some upper and lower bounds for the numbers $a(1;t)$ for some values
of~$t$.

\itemtr ({\sc investigatory, a general case})
Find some upper and lower bounds for the numbers $a(d;t)$ for some values
of~$d$ and~$t$.

\Remark. In the last three problems, as usual, serial bounds are more valuable than
partial results for fixed values of~$(d;t)$. Nevertheless, we insistently
recommend you to start with a consideration of a sufficient amount of
particular cases.

\end{document}

