\documentclass[11pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{ifthen}

\pagestyle{plain}
\advance\textwidth40mm
\advance\textheight70mm
\advance\voffset-30mm
\advance\hoffset-25mm
\footskip=8mm

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


\makeatletter
%%%%% NEW THEOREMS %%%%%
%\renewcommand{\thethm}{\arabic{section}.\arabic{thm}}
%\renewcommand{\thecor}{\arabic{cor}}
%\renewcommand{\thedf}{\arabic{df}}
%\renewcommand{\thelm}{\arabic{lm}}
%\renewcommand{\theprop}{\arabic{prop}}
%\renewcommand{\theequation}{\arabic{equation}}
\renewcommand{\abstractname}{Abstract}

\newcommand\txt[2]{{#1{\ifthenelse{\equal {#2}{}}{}{ #2}}. }}
\def\note{\par {\bf Remark.} }
%\def\zam#1.#2\par{\txt{\bf Замечание}{#1}\ #2\par%
%               \@ifnextchar {\Zam}{}{\@ifnextchar\begin{}{\smallskip}}}
\def\example#1.{\txt{\bf Example}{#1}}
%\def\proof#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{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\itemp#1{%
  \par\medskip\noindent%
  \protected@edef\@currentlabel{\thesection.#1}%
  \textbf{\thesection.#1.} }

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

\long\def\stm#1{ {\it #1}\par\smallskip}
\def\newsect{\refstepcounter{section}}

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

\def\cC{{\mathcal C}}
\def\cO{{\mathcal O}}
\def\cN{{\mathcal N}}
\def\cP{{\mathcal P}}
\def\cK{{\mathcal K}}
\def\cS{{\mathcal S}}
\def\cL{{\mathcal L}}

\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

\centerline{\Large\bf Solutions.}

\vskip\baselineskip

\newsect
\newsect

\itemm \label{first}
\stm{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.}

Denote the given segments as $[a_1,b_1],\dots,[a_n,b_n]$. Let $a_s=\max_{1\leq
i\leq n} a_i$, $b_t=\min_{1\leq i\leq n} b_i$ (it is possible that $s=t$). If
$a_s \le b_t$ then each given segment contains~$a_s$, which contradicts the
condition of the problem. Hence $a_s > b_t$, therefore $t
\neq s$, and the $s$th segment has no common point with the $t$th one.

\itemm
\stm{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.}

If we delete any edge~$e$ from a tree~$G$, we cut this tree into two
components. Moreover, if a subtree $G'$ does not contain~$e$, then it lies in
one of these components.

Denote our subtrees by $G_1, \dots, G_n$. Let $k$ be a maximal integer such
that the intersection $G=G_1 \cap G_2 \cap
\cdots \cap G_k$ is nonempty (note that $k<n$). Then the intersection of $G$ and~$G_{k+1}$ is empty.

Now consider a shortest path conecting~$G$ with~$G_{k+1}$. The first edge~$e$
of this path does not belong to~$G$, hence some~$G_i$ (with $1\leq i\leq k$)
also does not contain~$e$. Let us delete this edge. The subtrees~$G_{k+1}$
and~$G$ come to different components of the remaining graph.
Therefore~$G_{k+1}$ and~$G_i$ are also in different components. Hence their
intersection is empty.

\itemm
\stm{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.}

Partition the circle into 1001 arcs (we call them {\em small} arcs). We call a
complement of any small arc a {\em large} arc. We claim that the family of
large arcs is a desired example. Namely, it is easy to check that the
intersection of any 1000 large arcs is nonempty, but the intersection of all of
them is obviously empty.

\Remark. The large arcs in the solution are assumed not to contain their
endpoints. One may decrease them slightly to obtain an example consisting of
closed arcs.

\itemm
\stm{({\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}

Induction on the number~$n\geq 4$ of the considered convex sets. The base case
is $n=4$. Consider our convex sets $F_1,F_2,F_3,F_4$. Let $x_i$ be a point of
intersection of all of them except~$F_i$. We apply the following lemma.

\begin{lm}[Radon's theorem]
  One can partition any four points in the plane into two sets so that the
  convex hulls of these sets have a common point.
\end{lm}

\proof Consider two cases: (i) the points are the vertices of some convex
quadrilateral, and (ii) one of the points lies inside the triangle formed by
the other three.
\qed

So, suppose for example that the convex hulls of the sets~$\{x_1,x_2\}$
and~$\{x_3,x_4\}$ intersect at point~$x$. Then $x$ lies if~$F_3$ and~$F_4$,
since the whole segment~$x_1x_2$ lies in these sets. Analogously, $x\in F_1\cap
F_2$. All the other cases are completely analogous.

\smallskip
For the induction step, assume that $n\geq 4$ and consider $n+1$ convex sets
$F_1,\dots F_{n+1}$. Let us construct a new family consisting of $n$ convex
sets $F_1'=F_1\cap F_{n+1},\dots,F_n'=F_n\cap F_{n+1}$. By the statement of the
base case, each three of the new sets have a nonempty intersection. Then, by
the induction hypothesis, all the new sets have a common point, QED.

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

Let $\cG$ be a finite family of progressions such that every two of them have a
common element. Note that the intersection of each two progressions from~$\cG$
is infinite (in fact, it is an infinite progression as well). So, with no loss
of generality we may assume that the $i$th progression is defined by the
condition $x\equiv a_i\pmod {n_i}$ (for that, we need only to ``forget'' about
some initial segment of the row of the positive integers).

Consider one of our progressions; say it is defined by $x\equiv a\pmod n$. This
condition is equivalent to the system of the relations having the form $x\equiv
a\pmod {p_j^{\alpha_j}}$ (here, $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ is the
prime decomposition of~$n$). Now, let us write down such a system for each
progression. We need to prove that the system of all obtained relations is
collocated (i.e. has a solution).

Note that every two relations in our system are collocated, since they
correspond either to one or to two progressions. Next, suppose that the system
contains two equivalences modulo the powers of the same prime~$p$ (say $x\equiv
a\pmod{p^\alpha}$ and $x\equiv b\pmod {p^\beta}$). These relations are
collocated; we may assume that $\alpha\geq
\beta$. Then the latter relation is a consequence of the former one,
so we may delete the latter from the system.

Performing such steps, we finally arrive to a system where all moduli are the
powers of distinct primes. Such a system has a solution by the Chinese
Remainder Theorem.

\Remark. One may show that for every $t\geq 2$, there are no $t$-Helly--Gallai numbers
for the set of out progressions,

\itemm \stm{Let $\cO$ be the set of all the circumferences in the plane. Find
$H(\cO)$.}

\textbf{Answer.} $H(\cO)=4$.

Firstly, we prove that 4 is a Helly number for~$\cO$. Consider a finite
family~$\cG$ of circumferences such that the intersection of all of them is
empty. Consider arbitrary different circumferences~$O_1,O_2\in\cG$. They have
at most two points of intersection. Denote these points by~$A$ and~$B$ (if some
of these points do not exist, the arguments are the same).

Recall that no point belongs to all the circumferences. Therefore there exist
$O_3,O_4\in\cG$ such that $A\notin O_3$ and $B\notin O_4$. Hence
$O_1,O_2,O_3,O_4$ have no common points, as desired.

We are left to present an example showing that $H(\cO)>3$. Consider a noncyclic
nondegenerate quadrilateral $ABCD$. Consider four circumcircles of the
triangles $ABC$, $ABD$, $ACD$, $BCD$. Each three of them have a nonempty
intersection but all four do not.

\newsect

\itemm \stm{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$.}

Item a) is a particular case of b); so we present only a solution for the
latter one.

Denote the segments under consideration as $[a_1,b_1],\dots,[a_n,b_n]$. Denote
by~$c_1$ the minimal number among all $b_i$'s. Then each our segment either
contains~$c_1$ or lies to the right of~$c_1$. Denote by~$c_2$ the minimal~$b_i$
such that the segment~$[a_i,b_i]$ lies to the right of~$c_1$. Analogously, we
get that each our segment either contains~$c_1$ or~$c_2$, or lies to the right
of~$c_2$.

Proceeding in the same way while it is possible, we finally get the sequence
$c_1,c_2,\dots,c_k$ such that each segment contains at least one of these $k$
numbers. So, if $k\leq t$ then we have found a desired transversal. Assume now
that $k\geq t+1$. Consider $t+1$ segments with the right ends
$c_1,\dots,c_{t+1}$; by our choice, they are pairwise disjoint, so they do not
admit a $t$-transversal.

Thus, we have proved that either all the segments have a $t$-transversal, or
there are $t+1$ pairwise disjoint segments.  This means that $t+1$ is a
$t$-Helly--Gallai number for the segments in the line. Finally, an obvious
example of $t+1$ pairwise disjoint segments shows that $HG_t(\cS)>t$.

\itemm \stm{a) 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$.}

a) Set $k=500$. We construct a family~$\cF$ of $2k+1$ sets $A_1,\dots,a_{2k+1}$
(all indices are considered modulo~$2k+1$; thus $A_i=A_{2k+1+i}$) as follows.
Firstly, consider a set of indices $S\subset \{1,2,\dots,2k+1\}$ which does not
contain two indices with difference~1 (in particular, we prohibit the situation
$1,2k+1\in S$). For each such set~$S$, we introduce an element~$x_S$ (the
elements for different sets should be different as well). Next, we define
$A_k=\{x_S: k\in S\}$.

The obtained family has a Helly number~2. Indeed, assume that a subfaily~$\cG
\subset \cF$ has an empty intersection; let $\cG=\{A_i: i\in I\}$. If $I$ contains two
indices $i$ and~$i+1$ with difference~1, then $A_i,A_{i+1}\in \cG$ and $A_i\cap
A_{i+1}=\emp$. Otherwise all the sets in~$\cG$ contain~$x_I$ which is
impossible.

Finally, we claim that every $2k$ sets from~$\cF$ have a 2-transversal while
all $2k+1$ sets do not. Assume that~$\cF$ admits a 2-transversal~$\{x_S,x_T\}$
with $|S|\geq |T|$. Then $|S|\geq k+1$, and hence $S$ contains two neighboring
indices which is impossible. On the other hand, let us delete~$A_{2k+1}$
from~$\cF$; all the other sets have a 2-transversal $\{x_S,x_T\}$ where
$S=\{1,3,\dots,2k-1\}$ and $T=\{2,4,\dots,2k\}$.

Thus, $HG_2(\cF)=2k+1$.

b) For every positive integer~$k$, let us construct a family~$\cF_k$ as above.
We may assume that the sets from different families have no common elements.
Then it is easy to show that the union $\cF=\cF_1\cup\cF_2\cup\dots$ satisfies
all the requirements.

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

It suffices to prove that $HG_2(\cC) \ge 2k+1 $ for every positive integer~$k$.
Consider a circle with center~$O$; let $x_1,\dots,x_{2k+1}$ be the vertices of
a regular $(2k+1)$-gon inscribed into this circle (again, we regard the indices
 modulo~$2k+1$). Let $A_i$ be a convex hull of the points
 $x_i,\dots,x_{i+k-1}$. Then all the considered sets except any of them  admit a
 2-transversal (e.g., $\{x_k,x_{2k}\}$ is a 2-transversal for all the sets
 except~$A_{2k+1}$).

On the other hand, we claim that each point~$T$ belongs to not more than $k$
sets. Actually, let the ray~$OT$ intersect the boundary of $(2k+1)$-gon on the
semiinterval $(x_{i-1},x_i]$. Then $T$ may belong only to the sets
$A_{i-k+1},\dots,A_i$ as desired.

Hence our family of cardinality~$(2k+1)$ does not admin a 2-transversal, QED.

\itemmstar \stm{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?}

a) Induction on $t\geq 3$. We first prove the induction step; the base case
$t=3$ is investigated further.

Let $\cG$ be a finite family of lines such that every $\leq t^2+1$ lines
from~$\cG$ have a $t$-transversal. Choose arbitrary $t^2+1$ lines from~$\cG$.
One of the points of their $t$-transversal should belong to at least~$t+1$
chosen lines. Denote this point by~$A$, and let $\ell_1,\dots,\ell_{t+1}\in\cG$
be $t+1$ lines containing~$A$.

Denote by~$\cG'$ a subfamily of~$\cG$ consisting of those lines which do not
contain~$A$. We claim that each subfamily $D\subseteq\cG$ such that $|D|\leq
t^2-t$ has a $(t-1)$-transversal. Actually, we know that the family
$D\cup\{\ell_1,\dots,\ell_{t+1}\}$ has a $t$-transversal~$X$. By the pigeonhole
principle, two of the lines~$\ell_1,\dots,\ell_{t+1}$ should pass through the
same point of~$X$; hence this point is~$A$, i.e. $A\in X$. Finally, since the
lines from~$D$ do not contain~$A$, the set~$X\setminus\{A\}$ is a transversal
of~$D$.

\smallskip
Note now that $t^2-t\geq (t-1)^2+1\geq HG_{t-1}(\cL)$. Hence~$\cG'$ has a
$(t-1)$-transversal~$X$ by the induction hypothesis; therefore~$X\cup\{A\}$ is
a desired $t$-transversal for~$\cG$.

\smallskip
The proof of the base case follows the same lines except for the last paragraph
(namely, the only argument where we use the induction hypothesis). To finish
this argument, it suffices to show that $t^2-t=6\geq HG_2(\cL)$.

Note first that $HG_1(\cL)\leq 3$. Actually, if every three lines from~$\cG$
have a common point, then the intersection point of two of these lines should
belong to all the other lines. Finally, the inequality $HG_2(\cL)\leq 6$ can be
obtained again in the same way as the induction step (with the numbers $t^2+1$
and $t^2-t$ replaces by~6 and~3, respectively).


\medskip
b) We prove that $HG_t(\cL)=C_{t+2}^2$.

Firstly, we show that $HG_t(\cL)\geq C_{t+2}^2$. Take $t+2$
points~$T_1,\dots,T_{t+2}$ in a general position, and draw all the lines
connecting them. One may show that it is possible to choose the points in such
a way that no three lines intersect at a point different from $T_i$'s. For such
arrangement of points, our $C_{t+2}^2$ lines do not admit a $t$-transversal,
but all the lines except an arbitrary one have a $t$-transversal.

\smallskip
It remains to prove that $HG_t(\cL)\leq C_{t+2}^2$. We will use the following
lemma.

\begin{lm}
Let $P_1(x,y),\dots,P_k(x,y)$ be the polynomials in two variables of degree
$\leq t$. Suppose that $k>C_{t+2}^2$. Then there exist the numbers
$s_1,\dots,s_k$ (not all of them are zeroes) such that
$s_1P_1(x,y)+\dots+s_kP_k(x,y)=0$.
\end{lm}

\proof Our conditions on the variables $s_i$ can be rewritten as a system
of~$C_{t+2}^2$ linear homogeneous (i.e. with zero constant terms) equations
(the number of equations is simply the number of monomials  of degree~$\leq t$
in two variables). Since the number of variables is strictly greater than the
number of equations, this system has a nonzero solution.
\qed

Now we return to the solution. Obviously, it suffices to prove the following
statement: If $n\geq C_{t+2}^2$, and every $n$~lines in~$\cG$ have a
$t$-transversal, then every $n+1$ lines from~$\cG$ also have a $t$-transversal.

Assume the contrary and consider a family~$\cF$ of $n+1$ lines violating our
statement. Introduce a Cartesian system so that the origin does not lie on any
considered line. For an arbitrary index~$j$, the equation of the $j$th
line~$\ell_j$ can be written in the form $a_jx+b_jy+1=0$.

Now let us fix an arbitrary index~$i$ for a while. All the lines in~$\cF$
except~$\ell_i$ have a $t$-transversal consisting of points $(x_1,y_1)$, \dots,
$(x_t,y_t)$ (surely, none of these points lie on~$\ell_i$). This means that
$\prod_{k=1}^t (a_jx_k+b_jy_k+1)=0$ for all $j\neq i$, but the same relation is
false for $j=i$. Denoting now $P_i(a,b)=\prod_{k=1}^t (ax_k+by_k+1)$, we obtain
that $P_i(a_j,b_j)=0$ for all $j\neq i$, but $P_i(a_i,b_i)\neq 0$.

All the obtained polynomials have degree~$t$. By the lemma above, there exist
the numbers $s_1,\dots,s_n$ such that $\sum_{i=1}^n s_iP_i(a,b)=0$. We may
assume that $s_1\neq 0$. Hence we get $\sum_{i=1}^n
s_iP_i(a_1,b_1)=s_1P_1(a_1,b_1)\neq 0$. A contradiction.

\newsect

\itemm \stm{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$.

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

The problem statement can be rewritten as  $H(\cN_d)=d+1$.

Let~$\cG$ be a family of all subsets with $d$ elements in some fixed set~$X$ of
cardinality~$d+1$. Then each $d$ elements have a common element but the whole
family does not. Thus, $H(\cN_d)\geq d+1$.

Consider now an arbitrary finite subfamily $\cG\subset \cN_d$ such that each
$d+1$ sets in~$\cG$ share a common element. For every~$i=1,\dots,d+1$, denote
by~$s_i$ the minimal cardinality of the intersection of some~$i$ sets
from~$\cG$. Obviously, $1\leq s_{d+1}\leq s_d\leq \dots\leq s_1=d$. It follows
that $s_{j+1}=s_j$ for some~$j\in[1,d]$.

Consider now the sets $A_1,\dots,A_j\in\cG$ such that $|Q|=s_j$, where
$Q=A_1\cap\dots\cap A_j$. Assume that $Q\not\subseteq A$ for some $A\in\cG$;
then we get $s_{j+1}=s_j>|Q\cap A|=|A_1\cap\dots\cap A_j\cap A|$ which
contradicts to the definition of~$s_{j+1}$. Thus, all the sets in~$\cG$ contain
a nonempty set~$Q$, QED.

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

Surely, this problem is a corollary of the problem~\ref{gen-fin}. Here we
present an easier proof.

Induction on~$t$. The base case $t=1$ follows from the previous problem.

For the induction step, assume that $HG_{t-1}(\cN_d)=S<\infty$. We prove that
$HG_t(\cN_d)\leq T=S+C_{Sd}^t$.

Consider an arbitrary finite subfamily $\cG\subset \cN_d$ such that every $T$
sets in $\cG$ have a $t$-transversal. If every $S$ sets of $\cG$ have
$(t-1)$-transversal, then the family~$\cG$ has even a $(t-1)$-transversal by
the induction hypothesis. Otherwise, there exists a subfamily
$\cK=\{A_1,\dots,A_S\}\subset \cG$ which has no $(t-1)$-transversal. Thus each
$t$-transversal of the family $\cK$ should be contained in the set
$Q=A_1\cup\dots\cup A_S$. Remark that $|Q|\leq Sd$.

Assume now that the family  $\cG$ has no $t$-transversal. Then for each
$t$-element subset $X\subset Q$ there exists a set $A_X\in\cG$ such that
$A_X\cap X=\emp$. Now consider the subfamily
$$
  \cK'=\cK\cup\left\{A_X\;:\;X\subset Q,\;|X|=t\right\}.
$$
We have $|\cK'|\leq S+C_{Sd}^t=T$. Therefore $\cK'$ must have a
$t$-transversal~$Y$. Since $\cK\subset \cK'$, we have $Y\subset Q$. Finally, by
the choice of~$\cK'$, there exists the set $A_Y\in \cK'$ such that~$A_Y\cap
Y=\emptyset$. This contradiction concludes the proof.

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

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

a) See problem~4.4.

b) Follows from problem~\ref{gen-fin}.

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

It suffices to take a family~$\cG$ of all $d$-element subsets of some fixed
$(d+t)$-element set~$X$. Actually, each $t$-element subset in~$X$ has a common
element with each set in~$\cG$ except one.

%Достаточно рассмотреть семейство~$\cG$ всех $d$-элементных подмножеств
%$(d+t)$-элементного множества~$X$. Тогда любое $t$-элементное подмножество
%в~$X$ пересекается со всеми множествами из~$\cG$, кроме одного.

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

See the next problem.

\itemm \newcounter{catona}
\setcounter{catona}{\theprob}
\stm{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$.

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

a) Follows immediately from problem~4.7.

b) Assume the contrary. Consider a family $\cG\subset \cN_d$ of minimal
cardinality such that every its subfamily with~$\leq C_{d+t}^t$ sets has a
$t$-transversal, but~$\cG$ does not have a $t$-transversal. Surely, we have
$|\cG|>C_{d+t}^t$.

Let $\cG=\{A_1,\dots,A_n\}$. By our choice, for every~$i=1,\dots,n$ the family
$\cG\setminus\{A_i\}$ has a $t$-transversal~$B_i$. By the choice again, we have
$A_i\cap B_i=\emp$. Thus, the sets $A_1,\dots,A_n,B_1,\dots,B_n$ satisfy the
conditions of Katona's problem and hence $|\cG|=n\leq C_{d+t}^t$. A
contradiction.

\itemm
  \stm{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$.}

Let $X=A_1\cup\dots\cup A_n\cup B_1\cup\dots\cup B_n$; denote $n=|X|$. Consider
all $m!$ ways of numbering the elements of~$X$ by $1,\dots,m$ (or,
equivalently, all bijections $\sigma:X\to\{1,2,\dots,m\}$). Consider any such
numbering~$\sigma$; we say that it is
{\em of $i$th type} (for some $1\leq i\leq n$) if all the elements of~$A_i$
have smaller numbers than all the elements of~$B_i$ (i.e. $\sigma(a)<\sigma(b)$
for all $a\in A_i$, $b\in B_i$).

Firstly, we note that each numbering is of at most one type. Assume, to the
contrary, that~$\sigma$ is of both $i$th and~$j$th types for $i\neq j$. Denote
$a_i=\max_{a\in A_i} \sigma(a)$, $a_j=\max_{a\in A_j} \sigma(a)$; we may assume
that $a_i\leq a_j$. Then for every $b\in B_j$ and $a\in A_i$ we have
$\sigma(b)>a_j\geq a_i\geq \sigma(a)$; hence $A_i\cap B_j=\emp$. This
contradiction shows that our claim is valid.


Next, let us estimate the total number of the numberings of $i$th type. The
elements of $A_i\cup B_i$ can be ordered in $(a_i+b_i)!$ ways, and there are
exactly $a_i!b_i!$ appropriate ones. Moreover, for each such order, there
exists the same number of the numberings realizing this order. Hence the number
of the numberings of $i$th type is exactly $\displaystyle m!\cdot
\frac{a_i!b_i!}{(a_i+b_i)!}=m!\cdot \frac1{C_{a_i+b_i}^{a_i}}$.

Finally, the total number of the numberings is at least the sum of all the
numbers found above, i.e.
$$
  \sum_{i=1}^n \frac{m!}{C_{a_i+b_i}^{a_i}} \le m!,
$$
QED.

\itemm \stm{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$.}

Define $a_1=1,\,a_2=10^{101},\,a_3=10^{101}$ and
$b_1=10^{101},\,b_2=1,\,b_3=1$. Then each of the sets $B_2$ and $B_3$ should
have a common element with~$A_1$. All these three sets are of cardinality~1, so
they should coincide. Hence, since $B_2\cap A_2=\emp$, we also have $B_3\cap
A_2=\emp$ which is impossible.

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

\newsect

\itemm
  \stm{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.}

Consider three sets with a nonempty intersection, say $x \in A \cap B
\cap C$. Suppose that there exist two different sets $D$ and $E$ not
containing $x$. Consider the four sets $A,B,D,E$. Some three of them have a
common element $y$ ($y \neq x$ since $x\notin D,E$). Then $y$ belongs to at
least one of the sets~$A$ and~$B$; without loss of generality, $y\in A$. Next,
$A$ and $B$ may have at most one element in their intersection, and $x\in A\cap
B$; therefore $y\notin B$. Analogously, $y \notin C$. Then $y
\in D$ and $y \in E$, in other case there is no three sets among $A,B,D,E$
covering $y$.


Consider the four sets $B,C,D,E$. Among any three of them there are either
both~$B$ and~$C$,  or both~$D$ and~$E$. The unique common element of $B$ and
$C$ is~$x$, and it does not belong to~$D$ or~$E$. Analogously, the unique
common element of $D$ and $E$ is $y$, and it does not belong to $B$ or $C$.
Thus, the four sets $B,C,D,E$ have no element belonging to three of them. This
contradiction proves that there exists at most one set in~$\cF$ not
containing~$x$.

%Рассмотрим четверку $B,C,D,E$. Любая тройка множеств из нее содержит
%или пару $B,C$, или пару $D,E$. Но единственный общий элемент пары
%$B,C$ --- $x$,  и он не принадлежит ни $D$ ни $E$. Аналогично,
%единственный общий элемент пары $D,E$
%--- $y$,  и он не принадлежит ни $B$ ни $C$. Итак, для четверки $B,C,D,E$ нет
%элемента, покрытого тремя множествами --- противоречие. Значит не более чем
%одно не содержит $x$.

\itemm \stm{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$.}

Assume that for every four sets in~$\cF$, there are three with a nonempty
intersection. Then, by the previous problem, some element~$x$ belongs toall the
sets on~$\cF$ except one. Taking any element~$y$ from this exceptional set, we
obtain a 2-transversal~$\{x,y\}$ of~$\cF$.

Otherwise, there exist four sets~$A,B,C,D$ such that no three of them share a
common element. Adding any other set~$E\in\cF$, we obtain a 5-tuple of sets
three of which have a common element; these sets should be~$E$ together with
some pair of the original four sets, and their common element is a (unique!)
common element for this pair. There are 13 ways to choose~$E\in \cF$ and 6 ways
to choose a pair of the original sets. Hence, some pair appears for three
choices of~$E$, and its common element~$x$ belongs to five sets in~$\cF$. Now
we denote these five sets by $X_1,X_2,X_3,X_4,X_5$.

\smallskip
Consider now all the sets in~$\cF$ not containing~$x$. If there are at most two
of them, then their common element~$y$ together with~$x$ form a desired
2-transversal for~$\cF$. Next, if every three of these sets have a common
element, then it is easy to see that this element~$y$ should be the same for
all the triples, and $\{x,y\}$ is a 2-transversal for~$\cF$ again.

In the only case remaining, there exist three sets~$Y,Z,T$ not containing~$x$
and with no common element. Denote their pairwise common elements
by~$a_1,a_2,a_3$. Note that $a_i$ cannot belong to two of the sets
$X_1,\dots,X_5$ since otherwise these two sets have two common elements: $x$
and~$a_i$. Hence, among these five sets there are two (say $X_4$ and~$X_5$)
containing none of $a_i$'s. Finally, consider five sets $X_4,X_5,Y,Z,T$; no
three of them have a common element. A contradiction.

\medskip
\textbf{Firstly, we will present the solutions of problems~5.10 and
5.12--5.14. We will use them further as lemmas.}

%{Далее мы сначала приведём доказательства ключевых фактов про
%исключительные множества, а именно задач 5.10, 5.12--5.14. Мы будем
%затем использовать их в решениях оставшихся задач.}

In the sequel, by $\cG$ we always denote a $(d,t)$-exceptional family.
%We call
%the set $X_A$ the {\em representation} (or the {\em $\cG$-representation}) of
%the set $A$.

One may easily check that $X_A\not\subseteq X_B$ for arbitrary distinct $A,B
\in \cG$.

We need the following easy lemmas.
 %Заметим сразу,
%что все множества $X_A$ при $A\in\cG$ различны, ибо при $A\neq B$
%множество $X_A$ пересекает~$B$, но не~$A$, а множество~$X_B$ ---
%наоборот. Более того, отсюда же следует, что $X_A\not\subseteq X_B$.



%Для решения дальнейших задач будут полезны следующие простые леммы.

\begin{lm}
  \label{dec-t}
Let $S$ be some set, $|S|=s$. Consider the subfamily $\cF = \{A:\; A
\in \cG ,\; S\subseteq X_A \}$. Then $\cF$ is
a $(d,t-s)$-exceptional family.

%
%  Пусть $\cG$ --- $(d;t)$-исключительное семейство, а $S$ --- некоторое
%  множество мощности~$s$. Рассмотрим все такие множества $A\in\cG$, что $S\subseteq X_A$;
%  составим из них семейство~$\cF$
%  (то есть $\cF=\{A\in\cG: S\subseteq X_A\}$). Тогда $\cF$ является
%  $(d,t-s)$-исключительным.
\end{lm}

\proof If $S\subseteq X_A$ then $S\cap A=\emp$. Thus for all
distinct $A,B\in\cF$ we have $A\cap (X_B\setminus S)=A\cap X_B\neq\emp$. Hence,
the set $X_A\setminus S$ has a common element with each set in~$\cF$
except~$A$. Moreover, we have $|X_A\setminus S|=t-s$. That means exactly that
$\cF$ is $(d;t-s)$-exceptional.
\qed

%Если $S\subseteq X_A$, то $S\cap A=\emp$. Значит, для любых
%различных $A,B\in\cF$ мы имеем $B\cap (X_B\setminus S)=B\cap
%X_A\neq\emp$. Таким образом, для семейства~$\cF$ можно все
%множества~$X_A$ заменить на $X_A\setminus S$, причём $|X_A\setminus
%S|\leq t-s$. Тогда ясно, что $\cF$ --- $(d,t-s)$-исключительное.
%\qed

\begin{lm}
  \label{dec-d}
  Let $S$ be some set, $|S|=s$. Consider the family $\cF = \{A\setminus S: \; A\in \cG, \; S \subset A \} \subset
  \cG$. Then $\cF$ is a $(d-s,t)$-exceptional family.
%  Пусть $\cG$ --- $(d;t)$-исключительное семейство, а $S$ --- некоторое
%  множество мощности~$s$. Рассмотрим все множества $A\in\cG$, содержащие~$S$, и составим
%  семейство~$\cF$ из всех таких множеств с выкинутым множеством~$S$
%  (то есть $\cF=\{A\setminus S: S\subseteq A\in\cG\}$). Тогда $\cF$ является
%  $(d-s,t)$-исключительным.
\end{lm}

\proof %We will prove that $\cF$ is a $(d-s,t)$-exceptional family
%with respect to the representations $X_A$.
%
For every distinct $A,B\in\cG$, we have $|(A\setminus S)\cap (B\setminus
S)|=|A\cap B|-s\leq d-s$. Also, since $X_A\cap S=\emp$ we have $(B\setminus
S)\cap X_A=B\cap X_A\neq \emp$. Finally, $(A\setminus S) \cap X_A \subseteq A
\cap X_A = \emp$.
\qed

%Ясно, что для любых двух различных множеств $A,B\in\cG$,
%содержащих~$S$, выполняется условие $|(A\setminus S)\cap (B\setminus
%S)|=|A\cap B|-s\leq d-s$. Кроме того, мы имеем $X_A\cap S=\emp$;
%значит, $(B\setminus S)\cap X_A=B\cap X_A\neq \emp$, что и значит,
%что $\cF$ --- $(d-s,t)$-исключительное.

\medskip
\itemp{10} \stm{Prove that $b(d;t)\geq a(d;t)$.}

It is sufficient to prove that for any integer~$n$, $a(d;t)> n$ implies
$b(d;t)> n$.

If $a(d;t)> n$, then there exist a family~$\cG$ of degree~$d$ such that any
$n$~sets in~$\cG$ have a $t$-transversal, but the whole family does not.
Consider the minimal (with respect of number of sets) subfamily $\cF \subset
\cG$ having no $t$-transversal. Obviously, $|\cF|> n$. Since $\cF$ is minimal, any subfamily of $\cF$
has a $t$-transversal, thus $\cF$ is $(d,t)$-exceptional. Then $b(d;t)> n$.

%Достаточно доказать, что если $a(d;t)> n$ при некотором~$n$, то и $b(d;t)> n$.
%
%Если $a(d;t)\geq n$, то существует такое семейство~$\cG$ степени~$d$, что любые
%$n$ множеств из~$\cG$ имеют $t$-трансверсаль, а всё семейство --- не имеет. Из
%всех подсемейств семейства~$\cG$, не обладающих $t$-трансверсалью, выберем
%минимальное по количеству множеств и назовём его~$\cF$. Пусть $k=|\cF|$; ясно,
%что $k>n$. Тогда по выбору~$\cF$, любые $k-1$ множеств из~$\cF$ (скажем, все
%без некоторого~$A$) имеют $t$-трансверсаль~$X$. Заметим, что $X$ не должна
%пересекать~$A$, иначе~$X$ является $t$-трансв\ерсалью для~$\cF$. Значит, $X$
%удовлетворяет всем условиям на множество~$X_A$.
%
%Итак, $\cF$ --- $(d;t)$-исключительное семейство, поэтому $b(d;t)\geq k>n$, что
%и требовалось доказать.

\Remark. In the sequel, almost all the upper bounds for~$a(d;t)$ are in fact the upper
bounds for~$b(d;t)$. In this case we just omit mentioning that $b(d;t)\geq
a(d;t)$.

%В дальнейшем почти все верхние оценки, получаемые на~$a(d;t)$, на
%самом деле будут оценками на~$b(d;t)$. В этих случаях мы будем
%опускать ссылку на предыдущую задачу, завершающую доказательство.


\itemp{12} \stm{a) Let $t=2$. Prove that $h(x)\leq d+2$ for arbitrary $x$.

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

%\stm{a) Пусть $t=2$. Докажите, что $h(x)\leq d+2$ для любого $x$.
%
%b) Пусть $t$ произвольно. Докажите, что $h(x)\leq b(d;t-1)$.}
Although item b) is a generalization of item a), we present a separate proof of
item a) to clarify the idea.


%Пункт а) является частным случаем б) ввиду задачи 5.3. Тем не менее, мы
%приведём самостоятельное решение пункта а), а уже в решении б) сошлёмся на
%нужную лемму.

а) Suppose $h(x)\geq d+3$, i.e. there exist $A_1,\dots,A_{d+3}\in\cG$ such that
$X_{A_i}=\{x,x_i\}$ for some elements~$x_i$ (obviously, the elements $x_i$ are
distinct). Then $\{x_1,x_2,\dots,x_{d+1}\} \subset A_{d+2}$ and
$\{x_1,x_2,\dots,x_{d+1}\} \subset A_{d+3}$ which contradicts the condition
$|A_{d+2}\cap A_{d+3}|>d$.


b) Applying Lemma~\ref{dec-t} for the case $S=\{x\}$, we obtain that the family
 $\cF=\{A\in\cG: x\in X_A\}$ is $(d,t-1)$-exceptional, thus
$h(x)=|\cF|\leq b(d;t-1)$.


%б)
%По определению числа $h=h(x)$, существуют такие множества
%$A_1,\dots,A_{h}\in\cG$, что $X_{A_i}=\{x\}\cup X_i$, где $X_i$
%--- некоторые $(t-1)$-элементные множества. Поскольку $x\in X_{A_i}$, мы получаем $x\notin
%A_i$; значит, из условия $X_{A_i}\cap A_j\neq \emp$ вытекает $X_i\cap
%A_j\neq\emp$ при всех $i\neq j$. Это означает, что семейство
%$\cF=\{A_1,\dots,A_{b+1}\}$ является $(d;t-1)$-исключительным. Но тогда
%$h=|\cF|\leq b(d;t-1)$, что и требовалось доказать.

\itemp{13} \stm{Prove that $g(x)\leq b(d-1;t)$ for every~$x$.}

Applying Lemma~\ref{dec-d} to the set $S=\{x\}$, we obtain that
$\cF=\{A\setminus \{x\}: A\in \cG, x\in A\}$ is $(d-1,t)$-exceptional, i.e.
$g(x)=|\cF|\leq b(d-1;t)$.

%
%По определению числа $g=g(x)$, существуют такие множества
%$A_1,\dots,A_g\in\cG$, что $x\in A_i$. Это значит, что $x\notin X_{A_i}$, ибо
%$X_{A_i}\cap A_i=\emp$. Таким образом, из условия $X_{A_i}\cap A_j\neq\emp$
%вытекает $X_i\cap (A_j\setminus\{x\})\neq\emp$ при всех $i\neq j$. Полагая
%$B_i=A_i\setminus\{x\}$, мы получаем теперь, что $|B_i\cap B_j|=|(A_i\cap
%A_j)\setminus\{x\}|=|A_i\cap A_j|-1\leq d-1$ при всех $i\neq j$. Значит,
%семейство $\cF=\{B_1,\dots,B_g\}$ является $(d-1;t)$-критическим, и
%$g=|\cF|\leq b(d-1,t)$, что и требовалось доказать.

\itemp{14} \stm{Assume that $t=2$ and $h(x)\leq d$. Prove that $|\cG|\leq g(x)+h(x)+b(d-h(x);2)$.}

Let $B_1,\dots,B_h \in \cG$ be all the sets in~$\cG$ that contain $x$ (then
$h=h(x)$). Let $X_{B_i}=\{x,x_i\}$; again all~$x_i$ are distinct.

Let $A_1,\dots,A_k \in \cG$ be all the sets such that $x \notin A_i$ and $x
\notin X_{A_i}$. Since $k=|\cG|-g(x)-h(x)$, it is sufficient to prove that
$k\leq b(d-h(x);2)$.

Since $A_i\neq B_j$ for all $i$ and~$j$, we get $\{x,x_j\}\cap A_i\neq\emp$.
Keeping in mind that $x\notin A_i$ we get $x_j\in A_i$. Denote
$Y=\{x_1,\dots,x_h\}$; we have proved that $Y \subset A_i$ for all
$i=1,\dots,k$. Now, applying Lemma~\ref{dec-d} for~$S=Y$ we get $k\leq
b(d-h;2)$.

\Remark. Both the statement and the proof remain valid for the case $h(x)>d$;
note that we have $b(d-h;t)=1$ for $d<h$.

%Положим теперь $A_i'=A_i\setminus Y$, и обозначим $\cF=\{A_1',\dots,A_k'\}$. Мы
%имеем $|A_i'\cap A_j'|=|A_i\cap A_j|-|Y|\leq d-h$, то есть $\cF$ является
%семейством степени~$d-h$. Далее, множество~$X_{A_i}$ не пересекается с~$A_i$ и,
%следовательно, с~$Y$. Значит, $X_{A_i}\cap A_j'=X_{A_i}\cap A_j\neq \emp$ при
%всех $i\neq j$. Таким образом, $\cF$ является $(d-h,2)$-критическим

\medskip

\textbf{Now, we firstly prove the serial bounds, although using sometimes the sharp partial bounds obtained further.}

%{Сначала мы соберём серийные (но не обязательно точные) оценки.
%Правда, иногда мы будем пользоваться точными оценками из частных
%случаев ниже.}

Since $a(d;t) \le b(d;t)$ (see problem~5.10) it is sufficient to prove the
required upper bounds for~$b(d;t)$ instead of~$a(d;t)$. Thus in such cases we
always consider some $(d;t)$-exceptional family $\cG$ and prove some upper
bounds for~$|\cG|$.
%Согласно задаче~5.10, для получения верхних оценок на $a(d;t)$ достаточно
%получить такие же оценки на $b(d;t)$. Поэтому в каждом случае ниже мы с самого
%начала предполагаем, что выбрано $(d;t)$-критическое семейство~$\cG$, и
%оцениваем его мощность.

\itemp8 \label{genq1}\stm{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?}

%\stm{а) Докажите, что $a(d;t) \ge C_{d+t+1}^t$.
%
%б$)^{**}$ Существуют ли значения $d$, $t$, при которых неравенство в предыдущем
%пункте строгое?}

a) Consider a set $B$, $|B|=d+t+1$. Let $\cG$ be the family of all
$(d+1)$-element subsets of $B$. Then for any distinct $A_1,A_2 \in
\cG$ we have $|A_1\cap A_2| \le d$. Also, for any $A\in \cG$ we put
$X_A = B \setminus A$. Thus $|X_A|=t$ and $A_1 \cap X_A \neq \emp$ for any
distinct $A,A_1 \in \cG$. So, $\cG$ is $(d,t)$-exceptional.

b) The solution of this item is still not known.
%а) Пусть $\cG$ --- семейство всех $(d+1)$-элементных подмножеств некоторого
%$(d+t+1)$-элементного множества~$B$. Тогда любые два различных множества
%из~$\cG$ пересекаются не более, чем по~$d$ элементам. С другой стороны, любое
%$t$-элементное подмножество $X\subset B$ пересекается со всеми множествами
%из~$\cG$, кроме одного.

%б) Жюри до сих пор не знает ответа на этот вопрос.

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

%Согласно задачам 5.8а) и 5.10, нам достаточно доказать, что $b(d;1)
%\le d+2$. ???? Уже сто раз это сказано!

Suppose that a $(d;1)$-exceptional family $\cG$ contains at least $d+3$ sets,
say $\{A_1,A_2,\dots ,A_{d+3}\}\subseteq \cG$. Let $X_{A_i}=\{x_i\}$, all $x_i$
are distinct for $i=1,\dots,d+3$. By the definition of a $(d;t)$-exceptional
family we have $x_i \in A_1$ for $i=3,\dots,d+3$. Analogously $x_i \in A_2$ for
$i=3,\dots,d+3$. Thus $|A_1 \cap A_2| \ge |\{x_3,
\dots,x_{d+3}\}|=d+1$. A contradiction.


%Пусть существует $(d;1)$-исключительное семейство
%$\cF=\{A_1,A_2,\dots ,A_{d+3},\dots\}$ из не менее чем $d+3$
%множеств. По определению $(d;1)$-исключительного семейства все
%$X_{A_i}$ одноэлементные (пусть $X_{A_i}=\{x_i\}$); значит, $x_i \in
%A_j$ при $i \neq j$. Очевидно, $x_i \neq x_j$ при $i \neq j$.
%Значит, множества $A_1$ и $A_2$ содержат $d+1$ общий элемент $x_3,
%\dots,x_{d+3}$, что невозможно.

\Remark. Further we will also use an obvious proposition
$a(0;t)=b(0;t)=t+1$.
%В дальнейшем нам ещё потребуется очевидное равенство
%$a(0;t)=b(0;t)=t+1$. Его доказательство мы оставляем читателю.

\medskip
%Для удобства введём некоторые обозначения.
For the sake of brevity we introduce the following notation.

\begin{df}
  Let $G_x=\{A\in\cG: x\in A\}$ and
  $H_x=\{A\in\cG: x\in X_A\}$ for arbitrary $x$.
\end{df}

%Для индукционного перехода в следующей задаче будет полезно следующее уточнение
%задачи 5.12а).
For the induction step in the next problem, we need the following sharpening of
the statement of problem 5.12a).

\begin{lm}
  \label{h<=d}
 % Пусть $t=2$, и пусть $|\cG|>b(d-1;2)+d+3$. Тогда $h(x)\leq d$ для любого
%  элемента~$x$.
Assume that $t=2$ and $|\cG|>b(d-1;2)+d+3$. Then $h(x)\leq d$ for all~$x$.
\end{lm}

\proof Assume, to the contrary, that there exist $d+1$ distinct sets
$A_1,\dots,A_{d+1}$ such that $x \in X_{A_i}$. Let $X_{A_i}=\{x,x_i\}$ (again
all $x_i$ are distinct). Applying problem~5.13 we get $g(x)\leq b(d-1;2)$, so
there are at least $d+3$ sets in $\cG \setminus G_x$ and at least two of these
sets are distinct from $A_1,\dots,A_{d+1}$. Denote those two sets by $B$ and
$C$. Since~$x\notin B$ but $X_{A_i}\cap B\neq \emp$ we conclude
$\{x_1,\dots,x_{d+1}\}\subseteq B$. Analogously $\{x_1,\dots,x_{d+1}\}\subseteq
C$. Thus $|B\cap C|\geq d+1$. A contradiction.
\qed

% От противного. Пусть существуют такие
%$d+1$ множеств $A_1,\dots,A_{d+1}$, что $X_{A_i}=\{x,x_i\}$ (при
%различных элементах $x_i$). По задаче 5.13, мы имеем $g(x)\leq
%b(d-1;2)$. Значит, в~$\cG$ существуют хотя бы $d+3$ множества, не
%содержащие~$x$, и два из них не совпадают с~$A_i$. Пусть это
%множества~$B$, $C$. Поскольку~$x\notin B$, но $X_{A_i}\cap B\neq
%\emp$, получаем $\{x_1,\dots,x_{d+1}\}\subseteq B$. Аналогично,
%$\{x_1,\dots,x_{d+1}\}\subseteq C$. Значит, $|B\cap C|\geq d+1$, что
%%невозможно.



% От противного. Пусть существуют такие
%$d+1$ множеств $A_1,\dots,A_{d+1}$, что $X_{A_i}=\{x,x_i\}$ (при
%различных элементах $x_i$). По задаче 5.13, мы имеем $g(x)\leq
%b(d-1;2)$. Значит, в~$\cG$ существуют хотя бы $d+3$ множества, не
%содержащие~$x$, и два из них не совпадают с~$A_i$. Пусть это
%множества~$B$, $C$. Поскольку~$x\notin B$, но $X_{A_i}\cap B\neq
%\emp$, получаем $\{x_1,\dots,x_{d+1}\}\subseteq B$. Аналогично,
%$\{x_1,\dots,x_{d+1}\}\subseteq C$. Значит, $|B\cap C|\geq d+1$, что
%невозможно.

\Remark. In fact, this proof is a repetition of the solution of problem~5.14
(or its version for $h>d$).

\itemp{5} \stm{а) 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$.}

а) Follows from problem~5.8а).

б) We use the induction on $d\geq 2$ to prove that $b(d;2)\leq 2d^2+3$. The
base case will follow from the step.

Assume first that $b(d;2)\geq b(d-1;2)+d+3$. Then for all~$x$ we have $h(x)\leq
d$ by Lemma~\ref{h<=d}. Let $b=|\cG|$.

\smallskip
Now, for every element~$x$ denote by~$n(x)$ the number of (ordered) triples of
distinct sets~$(A,B,C)$ from~$\cG$ such that $x\in A$, $x\in B$, and $x\in
X_C$. We will bound the sum~$\sigma$ of all the numbers~$n(x)$ in two different
ways.

On one hand, there exist $b(b-1)$ pairs of different sets~$(A,B)$. For each
such pair, there are not more than $d$ ways to choose an element $x\in A\cap
B$, and for every such element there exist $h(x)\leq d$ possibilities for~$C$.
Thus, we  get $\sigma=\sum_x n(x)\leq b(b-1)\cdot d^2$.

On the other hand, consider an arbitrary set~$C$; let $X_C=\{x,y\}$. Each of
the other $b-1$ sets in~$\cG$ contains either~$x$ or~$y$. Denote by~$s_x$
and~$s_y$ the number of sets containing~$x$ and~$y$, respectively. Then
$s_x+s_y\geq b-1$. Furthermore, there exist $s_x(s_x-1)$ pairs of the sets
intersecting by~$x$, as well as $s_y(s_y-1)$ pairs intersecting by~$y$. In all,
the triples with this fixed~$C$ are counted exactly
$s(C)=s_x(s_x-1)+s_y(s_y-1)$ times. From $s_x+s_y\geq b-1$ one easily gets
$s(C)\geq
\frac{(b-1)(b-3)}2$ (the estimate is sharp for $s_x=s_y=\frac{b-1}2$).
Thus, we get $\sigma\geq b\frac{(b-1)(b-3)}{\mathstrut2}$.
% 2s^2-2s(b-1)+(b-1)(b-2)

Finally we get $d^2b(b-1)\geq \sigma\geq \frac12 b(b-1)(b-3)$, hence $2d^2\leq
b-3$, QED.

\smallskip
The only remaining case is $b(d;2)\leq b(d-1;2)+d+2$. If $d\geq 3$, then by the
induction hypothesis we have $b(d;2)\leq (2(d-1)^2+3)+d+2=2d^2-3d+5\leq
2d^2+3$, as desired. Finally, if  $d=2$, then we use the problem~5.4a) to
obtain~$b(1;2)=6$, therefore $b(2;2)\leq 6+2+2=10$ which is even stronger than
we need.

\Remark. Note that the estimates in main part of the solution admit some
improvements. Thus, the upper bound for~$\sigma$ is sharp only if $h(x)=d$ for
all~$x$. On the other hand, one may see from problem~5.14 that under this
restriction $g(x)$ is much greater than~$\frac{b-1}2$, and the lower bound is
far from being sharp. The method of obtaining sharper bounds is shown in the
proof of the Lemma~\ref{price} before the computation of~$b(1;4)$ and applied
after that.

\itemp7 \stm{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$.}

а) Follows from problem~5.8а).

б) The solution is literally the same as that for 3.4a): the only property of
the lines which is used there (but not in 3.4b)!) is exactly that they form a
family of degree~1.

\itemp{11} \stm{Prove that the number~$b(d;t)$ is finite for all~$d$ and~$t$.}

We prove the estimate $b(d;t)\leq t^{d+1}+(t^{d-1}+t^{d-2}+\dots+t^0)$ by the
induction on~$d\geq 1$. The base case $d=1$ is proved in~5.7б).

For the induction step, let $d\geq 2$. Consider an arbitrary set~$A\in\cG$; let
$X_A=\{x_1,\dots,x_t\}$. Then each of the other sets in~$\cG$ contains at least
one of the elements $x_1,\dots,x_t$. Next, the number of sets in~$\cG$
containing~$x_i$ is at most~$b(d-1;t)$ by Lemma~\ref{dec-d}. Therefore
$|\cG|\leq 1+tb(d-1;t)=1+t^{d+2}+(t^d+t^{d-1}+\dots+t)$, as desired.

\Remark. Instead of~5.7б), one may use a trivial bound $b(0;t)\leq t+1$ as the base case.
This way, one obtains a bit weaker bound, namely $b(d;t)\leq
t^{d+1}+t^d+\dots+1$.

\itemp9 \stm{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)$.}

Item~a) is an immediate consequence of~5.10 and~5.11. From the solutions of the
same problems one can obtain $a(d;t)\leq t^{d+1}+(t^{d-1}+t^{d-2}+\dots+t^0)$
for all~$d\geq 1$.

%%%
% begin Миша
\textbf{Finally, we proceed to sharp (although particular) results from problems~5.4 and~5.6.
Here we do not refer to the numbers of problems but just write down the
equalities to be proved.}
%Наконец, мы переходим к точным, хотя и частным, результатам из задач~5.4 и~5.6. Здесь мы не ссылаемся на пункты этих задач, а просто выписываем доказанное равенство.}

The lower bounds in all cases follow directly from problem~5.8a). For the upper
bounds we assume again that a $(d;t)$-critical family~$\cG$ is chosen and we
bound the cardinality of the family.
%Нижние оценки во всех случаях непосредственно следуют из задачи 5.8а). Для верхних оценок мы опять предполагаем, что выбрано $(d;t)$-критическое семейство~$\cG$, и оцениваем его мощность.

\underline{\boldmath$b(1;2)=6$.}
Assume that $|\cG|\geq 7$. Consider an arbitrary $C\in\cG$; set $X_C=\{x,y\}$.
Then each of the remaining sets in~$\cG$ contains either~$x$ or~$y$; hence at
least three of the sets contain the same element of~$X_C$, say $x\in
A_1,A_2,A_3$. Notice that $g(x)\leq 3$ by problem~5.13; so the remaining sets
in~$\cG$ do not contain~$x$. By our assumption, $\cG$ contains at least $4$
sets $C_1,C_2,C_3,C_4$ distinct from~$A_i$.

Consider an arbitrary index~$k=1,2,3,4$. Set $X_{C_k}=\{x_1,x_2\}$. There must
be two sets among~$A_i$ containing the same element~$x_j$. Since their
intersection consists of~$x$ only (because $\cG$ is a family of degree $1$!) it
follows that $x=x_j\in X_{C_k}$. Thus $x\in C_k$ for each $k=1,2,3,4$. Then by
Lemma~\ref{dec-t} applied to~$S=\{x\}$ the family $\{C_1,C_2,C_3,C_4\}$ is
$(1;1)$-exceptional, and by problem~5.3 it has at most 3 elements. A
contradiction.


\Remark.
Analyzing this solution one can capture the following lemma useful for the
sequel.


\begin{lm}
  \label{1t}
   Let $\cG$ be an exceptional $(1,t)$-family such that $g(x)\geq t+1$ for some~$x$. Then for each $B\in\cG$,
   we have either $x\in B$ or $x \in X_B$. Moreover,
   in this case we have that $g(x)=t+1$ and the family $\cF=\cG\setminus G_x$ is $(1,t-1)$-exceptional.
\end{lm}

%\Remark. Напомним, что в любом случае $g(x)\leq t+1$ по задаче 5.13.

\proof Assume that $g(x)\geq t+1$; we have $G_x\supseteq \{A_1,\dots,A_{t+1}\}$.

Assume that $x\notin B$ and $x\notin X_B$ for some $B\in\cG$. Each of the sets
$A_1,\dots,A_{t+1}$ contains at least one element of~$X_B$; since $|X_B|=t$ it
follows that two of these sets contain the same element (say, $y\in A_1\cap
A_2\cap X_B$). But then $A_1\cap A_2$ contains (distinct!) elements~$x$
and~$y$, which is impossible. Thus the required set~$B$ does not exist.

Further, $g(x)\leq t+1$ by problem~5.13, so that $g(x)=t+1$. The second
assertion now follows from Lemma~\ref{dec-t}.
\qed

\medskip
\underline{\boldmath$b(1;3)=10$.}
Assume that $|\cG|\geq 11$. Consider an arbitrary $C\in\cG$; set
$X_C=\{x,y,z\}$. Then each of the remaining sets in~$\cG$ contains at least one
of the elements~$x$, $y$, or~$z$, thus $g(x)+g(y)+g(z)\geq 10$. Hence at least
one of the summands is greater than $3$, say, $g(x)\geq 4$. Then by
Lemma~\ref{1t} we obtain that $\cF=\cG\setminus G_x$ is $(1;2)$-exceptional,
and $|\cF|\geq 7$. This contradicts to $b(1;2)=6$.

\Remark. The previous two statements essentially repeat the solution of problem~3.4а).
We present them here to make the appreciation of the next point more
convenient.

\medskip
For the sequel we improve somehow the main approach of problem~5.5. That is, we
slightly modify the definition of the sum~$\sigma$, so that it allows to obtain
a bit better estimates. The meaning of the following definition is clear from
the lemma afterwards.

\begin{df}
For each element $x$ belonging to at least one set of the form~$X_A$, the {\em
price} of $x$ is~$\displaystyle
  p(x)=\frac{g(x)(g(x)-1)}{h(x)}$. For each $C\in\cG$,
  define its {\em price}  by the formula $P(C)=\sum_{x\in X_C}p(x)$.
\end{df}

\begin{lm}
  \label{price}
  Let $\cG$ be a $(d;t)$-critical family of cardinality~$b$. Then there exists a set~$C\in\cG$ such that $P(C)\leq d(b-1)$.
\end{lm}

\proof
Again, for each element~$x$ denote by $n(x)$ the number of ordered triples of
distinct sets~$(A,B,C)$ from the family~$\cG$ such that $x\in A$, $x\in B$, and
$x\in X_C$. But now we are going to estimate a different sum, that is
$$
  \Sigma=\sum_x \frac{n(x)}{h(x)}
$$
(naturally, the sum is over all the elements appearing in the sets of the
form~$X_A$).

On one hand, there exist $b(b-1)$ pairs of distinct sets~$(A,B)$. For each such
pair there is no more than $d$ possibilities to choose an appropriate
element~$x$ (because $|A\cap B|\leq d$). Further, any element  $x\in A\cap B$
contributes exactly~1 to the sum~$\Sigma$; indeed, there exist $h(x)$
possibilities for the set~$C$, and each of these possibilities is counted with
the ``weight'' $1/h(x)$. Thus we get
$$
  \Sigma=\sum_{(A,B):\;A\neq B} |A\cap B|\leq d\cdot b(b-1).
$$

On the other hand, we consider an arbitrary set~$C$, and we show that its
contribution to~$\Sigma$ is equal to~$P(C)$. Indeed, for each $x\in X_C$, we
count exactly $g(x)(g(x)-1)$ pairs in the number $n(x)$. Taking into account
the ``weight'' $1/h(x)$, we obtain that the ``contribution of the pair $x,C$''
equals $p(x)$. Therefore the contribution of the set~$C$ equals~$P(C)$, as
required.

So $db(b-1)\geq \Sigma=\sum_{C\in\cG} P(C)$. By the pigeonhole principle, one
of the $b$~summands from the right-hand side is not greater than~$d(b-1)$.
\qed

%%%
% end Миша

\medskip
\underline{\boldmath$b(1;4)=15$.}
Assume that $|\cG|\geq 16$; removing several sets from~$\cG$ we may also assume
that $b=|\cG|=16$. Consider an arbitrary $C\in\cG$; set
$X_C=\{x_1,x_2,x_3,x_4\}$. Analogously to the previous case, we get $\sum_i
g(x_i)\geq 15$, and $g(x_i)\leq 4$ (otherwise, using Lemma~\ref{1t}, we get a
contradiction with $b(1;3)=10$).

So $\sum_ig(x_i)=\sum_i|G_{x_i}|\leq 16$, but each set $A\in \cG$ distinct
from~$C$ must be contained in at least one of  $G_{x_i}$. This implies that
either all the families $G_{x_i}$ are disjoint or only two of them intersect
each other by a single set. In any case we may assume that $G_{x_1}$,
$G_{x_2}$, and
$G_{x_3}$ are disjoint and contain 4 sets each% (а $G_{x_4}$ может
%пересекаться лишь с~$G_{x_3}$ и содержать 3 или 4 элемента)
.

\smallskip
\textbf{Proposition.} For each~$A\in\cG$, which is distinct from~$C$, the set~$X_A$ contains neither of the elements~$x_1,x_2,x_3$.

\textit{Proof.} Assume that $x_1\in X_A$; then clearly $x_1\notin A$.
Notice that one of the two elements $x_2,x_3$ also does not belong to~$A$,
because $G_{x_2}\cap G_{x_3}=\emp$; we may assume that $x_2\notin A$. Suppose
now that $x_2\notin X_A$. Denote by $B_1,B_2,B_3,B_4$ the four sets containing
~$x_2$; none of them contains~$x_1$. The intersection of any two of them is
$\{x_2\}$; hence all the sets $B_i\cap X_A$ are disjoint. Thus $X_A$ consists
of these four intersections (because $|X_A|=4$). But they do not contain~$x_1$.
This contradicts to the assumption that $x_1\in X_A$.

We have proved that $x_1,x_2\in X_A$. Now assume that $x_3\notin X_A$. The
family  $G_{x_3}$ contains at least three sets distinct from~$A$. They must
intersect with~$X_A$ by distinct elements, which are also distinct
from~$x_1,x_2$. This is again impossible because $|X_A|=4$. Thus
$X_A=\{x_1,x_2,x_3,y\}$ for some~$y\neq x_4$.

Finally, consider two sets~$B,B'\in
\cG$ which do not belong to~$G_{x_1}\cup G_{x_2}\cup G_{x_3}$ and are distinct from $A$ and
$C$ (such sets exist because $|G_{x_1}|+|G_{x_1}|+|G_{x_1}|+2= 14=|\cG|-2$).
Then $\emp\neq B\cap X_C$, therefore $x_4\in B$. Analogously, $y\in B$, and
also $x_4,y\in B'$. Thus $|B\cap B'|\geq 2$, which is impossible.
\qed

So we know that $h(x_1)=h(x_2)=h(x_3)=1$ and $g(x_1)=g(x_2)=g(x_3)=4$. Hence
${P(C)\geq 3\cdot \frac{12}1+p(x_4)>36}$. On the other hand, by
Lemma~\ref{price} there exists~$C\in\cG$ such that $P(C)\leq db=30<36$. This
contradiction concludes the proof.

\medskip
\underline{\boldmath$b(2;2)=10$.}
Assume that $|\cG|=11$. It follows from Lemma~\ref{h<=d} that $h(x)\leq 2$ for
each $x$, and by problem~5.13 we have $g(x)\leq 6$. Then by problem~5.14,  we
get that $g(x)=6$ whenever $h(x)=2$. Thus if $g(x)$ attains one of the values
4, 5 or 6, then $p(x)$ cannot be less than 12, 20 or $\frac{30}2=15$,
respectively.

By Lemma~\ref{price} there exist~$C\in\cG$ such that $P(C)\leq 2\cdot 10=20$.
Let $X_C=\{x,y\}$, where $g(x)\geq g(y)$. Notice that $g(x)+g(y)\geq |G_x\cup
G_y|=10$, so that $g(x)\geq 5$, $g(y)\geq 4$. Then $P(C)\geq 15+12=27$. A
contradiction.

\medskip
\underline{\boldmath$b(3;2)=15$.}
 Assume that $|\cG|=16$. Arguing analogously to the previous solution we get $h(x)\leq 3$, $g(x)\leq 10$, and for $h(x)=1,2,3$ we have  $g(x)\geq 5,8,10$, respectively.

Further, using Lemma~\ref{price} we find $C\in\cG$ such that $P(C)\leq3\cdot
15=45$. Set $X_C=\{x,y\}$, where  $g(x)\geq g(y)$. Then $g(x)\geq 8$, therefore
$p(x)\geq 28$; also $p(y)\geq 20$, because $g(y)\geq 5$. Thus $P(C)\geq 48$. A
contradiction.

\medskip
\underline{\boldmath$b(4;2)=21$.}
Arguing analogously to the previous solutions, we find $C\in\cG$ such that
$P(C)\leq 84$. If $X_C=\{x,y\}$ and $g(x)\geq g(y)$, then we get an analogous
contradiction in every case except $g(y)=6$; in this remaining case we
necessarily have $g(x)=15$ and $h(x)=4$ (otherwise $P(C)>84$ again).

Consider the last case separately. Since $h(x)=4$, there exist sets
$C_1,C_2,C_3,C_4$ such that $h(C_i)=\{x,y_i\}$. Then there exist
$22-g(x)-h(x)=3$ sets $B_1,B_2,B_3$ such that $x\notin B_i$ and $x\notin
X_{B_i}$. By the properties of the sets $X_{C_j}$ it follows that
$\{y_1,y_2,y_3,y_4\}\subseteq B_i$. Thus any two sets~$B_i$ must intersect
precisely by the elements $y_1,y_2,y_3,y_4$.

Finally, for each $C\in\cG$, which is distinct from~$B_i$, the set~$X_C$
intersects all $B_i$; thus one its element is contained in two sets $B_i,B_j$.
Thus one of the elements $y_1,y_2,y_3,y_4$ is contained in~$X_C$. This implies
that $\sum_i h(y_i)\geq 22-3=19$; but then $h(y_i)\geq 5$ for some~$i$. As we
have noticed above, this is impossible.

\Remark. Developing these approaches the authors have proved that $a(d;2)=b(d;2)=C_{d+2}^2$ for each $d\leq 7$.

\end{document}
