%--------------------------------------------------
%      Avoider Forcer
%      
%--------------------------------------------------
\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
%
\renewcommand{\ss}{\smallskip}
\newcommand{\beq}[1]{\begin{equation}\label{#1}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqa}{\begin{eqnarray*}}
\newcommand{\eeqa}{\end{eqnarray*}}
%
\newcommand{\MB}{\mathcal{MB}}
\newcommand{\AF}{\mathcal{AF}}
\newcommand{\AFm}{\mathcal{AF}_\text{\rm mon}}
\newcommand{\FA}{\mathcal{FA}}
\newcommand{\F}{\mathcal H}
\newcommand{\FGn}{{\mathcal H}_{G,n}}
\newcommand{\D}[2]{{\mathcal D}_{#1,#2}}
\newcommand{\C}[2]{{\mathcal C}_{#1,#2}}
\newcommand{\PMn}{{\mathcal M}_n}
\newcommand{\Hamn}{{\mathcal Ham}_n}
%
\newcommand{\eps}{\varepsilon}
\newcommand{\al}{\alpha}
\newcommand{\rank}{\text{\rm rank}}
\newcommand{\aas}{a.a.s.}
\newcommand{\fu}{f^+}
\newcommand{\fl}{f^-}
\newcommand{\fm}{f^\text{\rm mon}}
%
\newcommand{\subs}{\subseteq}
\newcommand{\setm}{\setminus}
\newcommand{\lf}{\lfloor}
\newcommand{\rf}{\rfloor}
\newcommand{\lc}{\lceil}
\newcommand{\rc}{\rceil}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
%
\newtheorem{theorem}{Theorem} [section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
%
\let\epsilon=\varepsilon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{Avoider-Forcer games on hypergraphs with small rank}
\author{
Ma{\l}gorzata Bednarska-Bzd\c ega\\
\small Department of  Discrete Mathematics\\[-0.8ex]
\small Adam Mickiewicz University\\[-0.8ex]
\small Pozna\'n, Poland\\
\small\tt  mbed@amu.edu.pl
}
%\keywords {combinatorial games, Avoider-Forcer games}
%\subjclass {Primary: 91A46, %Combinatorial games
%Secondary: 91A43} %Games involving graphs

\date{\dateline{Jan 25, 2013}{Dec 04, 2013}\\
\small Mathematics Subject Classifications: 91A46, 91A43}

\begin{document}

\maketitle

\begin{abstract}
We study biased $(a:f)$ Avoider-Forcer games played on hypergraphs,
in the strict and monotone versions. 
We give a sufficient condition for  Avoider's win, useful 
in the case of games on hypergraphs whose rank is smaller than $f$. 
We apply this result to estimate the threshold bias 
in Avoider-Forcer $(1:f)$ games in which
Avoider is trying not to build a copy of a fixed graph $G$ in $K_n$.
We also study the $d$-degree $(1:f)$ game in which   
Avoider's aim is to avoid a spanning subgraph of minimal degree 
at least $d$ in $K_n$. We show that 
the strict 1-degree game has the threshold which is the same as the threshold of the 
Avoider-Forcer connectivity game. 

\bigskip\noindent \textbf{Keywords:} combinatorial games, Avoider-Forcer games, Avoider-Enforcer games
  
\end{abstract}


\section{Introduction}\label{intro}

Let $V$ be a finite set and $E$ be a multiset of subsets of $V$.
We consider two types of two-person positional games played on the hypergraph $\F=(V,E)$\,;
these are Avoider-Forcer strict games (cf.~\cite{TTT} and \cite{ae07}) and
Avoider-Forcer games in the monotone version (introduced in \cite{ae09}). 
We will relate these games with the widely studied and well understood Maker-Breaker games.

Let us recall that in {\sl Maker-Breaker $(p:q)$ games},
where $p$ and $q$ are natural numbers, 
two players claim in turns previously unselected ({\sl free}) elements of $V$ 
until all elements of $V$ are selected.
In every turn Maker selects $p$ vertices and Breaker 
answers by selecting $q$  vertices of the hypergraph $\F$. 
Maker wins if and only if by the end of the game he occupies all elements of at least one edge of $\F$. 
We will denote such games by $\MB(\F,p,q)$. 


In {\sl Avoider-Forcer strict $(a:f)$ game}, denoted by $\AF(\F,a,f)$,  
in each turn Avoider selects exactly $a$ elements and then Forcer  
selects exactly $f$  elements of $V$. If in the last turn there are fewer free  
vertices than a player has to select, he takes all the remaining 
unoccupied elements. Avoider loses if by the end of the game he selects all elements 
in at least one edge of the hypergraph, otherwise he wins.

The rules of {\sl Avoider-Forcer $(a:f)$ games in the monotone version} are almost the same as 
those of $\AF(\F,a,f)$. The only difference is
that Avoider and Forcer select at least $a$ and at least $f$ elements per turn respectively.
We denote such games by $\AFm(\F,a,f)$. 

Let us remark that we follow the game terminology of \cite{TTT}, while the authors of \cite{aebox}, 
\cite{planar}, \cite{ae09}, \cite{ae07} and \cite{cover}  call Forcer {\sl Enforcer}. 
We also emphasize that by the $i$th turn we mean the pair of Avoider's $i$th move and Forcer's $i$th move.

An important tool used in studying Avoider-Forcer games 
is the following winning condition for Avoider,
proved by Hefetz, Krivelevich and Szab\'o. The condition was proved in \cite{ae07}
for $\AF(\F,a,f)$, and the authors of \cite{ae09} noted that it applies also to $\AFm(\F,a,f)$.

\begin{theorem}[\cite{ae07}, Thm 1.1]\label{ae07}
If
$$\sum_{D\in E(\F)}\Big(\frac{1}{a}+1\Big)^{-|D|+a}<1,$$
then for every $f\ge 1$, Avoider has a winning strategy for
the games $\AF(\F,a,f)$ and $\AFm(\F,a,f)$.

If
$$\sum_{D\in E(\F)}\Big(\frac{1}{a}+1\Big)^{-|D|}<1,$$
$f\ge 1$ and Forcer makes the last move in $\AF(\F,a,f)$, then 
Avoider has a winning strategy for $\AF(\F,a,f)$.
\end{theorem} 

Let us define the {\sl  rank} of a hypergraph by setting 
$$\rank(\F)=\max_{D\in E(\F)}|D|.$$ 
In this paper we give 
the following Avoider's winning condition, 
which is useful in games 
played on hypergraphs of small rank. 

\begin{theorem}\label{awf}
Let $\F$ be a hypergraph of rank $r$.
\begin{itemize}
\ss\item[(i)]
If
$$\sum_{D\in E(\F)}\Big(\frac{f}{ar}+1\Big)^{-|D|+a}<1\,,$$
then Avoider has a winning strategy for both $\AF(\F,a,f)$ and $\AFm(\F,a,f)$.
\ss\item[(ii)]
Let
$$\sum_{D\in E(\F)}\Big(\frac{f}{ar}+1\Big)^{-|D|}<1\,.$$
Then for every $f'\ge f$, in the course of $\AF(\F,a,f')$ and $\AFm(\F,a,f')$,
in each position with at least $a+f$ free vertices, 
Avoider has a move after which  no edge of $\F$ is entirely 
occupied by him.
\end{itemize}
\end{theorem}

The first inequality in the above theorem, for $a=1$, looks similar to the well known Beck's winning condition 
for Breaker in $\MB(\F,1,f)\,$ (cf.~\cite{beckwf}):
\beq{beckwf}
\sum_{D\in E(\F)}(f+1)^{-|D|+1}<1.
\eeq
However, we cannot expect that (\ref{beckwf}) is in general a sufficient
condition for Avoider's win in $\AFm(\F,1,f)$. Furthermore, for any $a\ge 1$ we cannot improve the expression
$\big(\frac{f}{ar}+1\big)$ in Theorem \ref{awf}(i) more than up to $\big(\frac{3f}{ar}+1\big)$.
We express this fact by Theorem \ref{awfopt}:

\begin{theorem}\label{awfopt}
Let $a\ge 1$ and $r\ge 3a$. There exists a constant 
$c$ (depending on $r$ and $a$) such that for every $f>c$ there exists a hypergraph $\F$
of rank $r$ which satisfies the condition  
$$\sum_{D\in E(\F)}\Big(\frac{3f}{ar}+1\Big)^{-|D|+a}<1\,,$$
but Forcer has a winning strategy for $\AFm(\F,a,f)$.
\end{theorem}
The construction of a hypergraph described in the above theorem is very simple. We will consider
edge-disjoint, $r$-uniform hypergraphs and apply the results on {\sl Box games} by
Ferber, Krivelevich and Naor~\cite{aebox}.

In order to demonstrate how to use Theorem \ref{awf},
we study the threshold properties 
of Avoider-Forcer $(1:f)$ games. As observed in \cite{ae09} 
and \cite{ae07}, for such games one can consider
three types of thresholds.
Thus, given a hypergraph $\F$, 
we denote by {\sl the lower threshold bias} $\fl_{\F}$ the largest integer such that 
for every $f\le \fl_{\F}$
Forcer has a winning strategy for $\AF(\F,1,f)$. 
We mean by {\sl the upper threshold bias} $\fu_{\F}$ the largest integer $f$ such that 
Forcer wins $\AF(\F,1,f)$. Both $\fl_{\F}$ and $\fu_{\F}$ always exist, 
except for some degenerate cases.
If $\fu_{\F}=\fl_{\F}$, then we call the number $f_{\F}=\fu_{\F}=\fl_{\F}$ {\sl the threshold bias of
the strict game}. Finally,  {\sl the threshold bias of
the monotone game} is the non-negative integer {$\fm_{\F}$ such that 
Forcer wins $\AFm(\F,1,f)$ iff $f\le \fm_{\F}$. 
Throughout the paper the (upper/lower/monotone) threshold bias is called shortly 
{\sl the (upper/lower/monotone) threshold}. 
Note that the monotonicity rules of 
$\AFm(\F,1,f)$ guarantee the existence of $\fm_{\F}$,
as opposed to the strict Avoider-Forcer games, in which the threshold $f_{\F}$ 
may not exist (cf.~\cite{ae07}). 

The threshold properties of Avoider-Forcer games were studied extensively for {\sl graph games}.
In such games the players select edges of the complete graph $K_n$, Avoider's aim is to 
avoid a graph from a given family of subgraphs of $K_n$ 
(see e.g.~\cite{planar},\cite{ae09},\cite{ae07},\cite{cover}). Let us mention   some
examples of graph games, studied before in both strict and monotone versions. In {\sl connectivity
games} Avoider is trying to avoid any connected spanning subgraph of $K_n$. In other words,
the connectivity games $\AF(\C1n,1,f)$ and $\AFm(\C1n,1,f)$ 
are played on the hypergraph $\C1n$, with vertex-set $V(\C1n)=E(K_n)$, 
whose edges are connected spanning subgraphs of $K_n$. 
In a similar way, the hypergraphs
$\C dn$, $\C dn'$, $\Hamn$ and $\PMn$ correspond to the families of all $d$-connected spanning subgraphs, 
$d$-edge-connected spanning subgraphs, Hamiltonian cycles
and perfect matchings in $K_n$ respectively. To avoid technicalities  we always assume that $n$ is even 
when considering $\PMn$.
We denote by $\D dn$, with $1\le d\le n-1$, the hypergraph corresponding to
the family of all spanning subgraphs of the minimum degree at least $d$. Finally, given a graph $G$,
by $\FGn$ we denote the hypergraph corresponding to the family of all copies of $G$ in $K_n$.
We refer to games played on the hypergraphs $\Hamn$, $\C dn$, $\D dn$ and $\FGn$, as
{\sl Hamiltonicity, $d$-connectivity, $d$-degree and small-graph games} respectively.

Somewhat surprisingly the thresholds for monotone Avoider-Forcer Hamiltonicity, 
\mbox{$d$-connectivity} and $d$-degree games (with $d$ fixed) are very similar to 
their Maker-Breaker counterparts.
Krivelevich and Szab\'o \cite{cover} showed that if $f\le (1+o(1))n/\ln n$, then Forcer 
wins $\AFm(\Hamn,1,f)$ (and therefore wins also $\AFm(\PMn,1,f)$). The same condition on $f$ suffices to 
force Avoider to create a spanning $d$-connected subgraph of $K_n$,  
so $\AFm(\D dn,1,f)$ and $\AFm(\C dn',1,f)$ can be won by Forcer. 
On the other hand, Hefetz {\em et al.}~\cite{ae09} proved that if $f>(1+o(1))n/\ln n$, then 
Avoider wins $\AFm(\D1n,1,f)$. Hence we have
$$\fm_{\D dn}, \fm_{\C dn'}, \fm_{\C dn}, \fm_{\Hamn}, \fm_{\PMn}=(1+o(1))\frac{n}{\ln n}.$$ 
So the leading term of the threshold in all the above games is the same as in the corresponding
Maker-Breaker games (\cite{CE},\cite{GSz},\cite{kriv}). %d-connected: {kriv} na koncu

The strict versions of the above Avoider-Forcer games are 
harder to study and we know only partial results for some 
of these games. 
Hefetz, Krivelevich and Szab\'o \cite{ae07} proved that for the connectivity game $\AF(\C1n,1,f)$ 
the threshold exists and 
\beq{conn}
f_{\C1n}=\Big\lf\frac{n-1}{2}\Big\rf.
\eeq

For the games $\AF(\PMn,1,f)$ and $\AF(\Hamn,1,f)$ the orders of the upper and the lower thresholds are 
not known. Hefetz, Krivelevich and Szab\'o \cite{ae07} proved that
$\fl_{\PMn}=\Omega(n/\ln n),\,$
and due to Krivelevich and Szab\'o \cite{cover} we have
$\fl_{\Hamn}=\Omega(n/\ln n).\,$
As for the upper threshold, a simple calculation of the number of edges needed to create a 
perfect matching or a Hamilton cycle in $K_n$ implies that $\fu_{\PMn}<n$ and $\fu_{\Hamn}<0.5n$. Although in this paper we improve 
slightly these bounds (see Corollary~\ref{corr2}  below),  the questions whether $\fu_{\PMn}=o(n)$ 
and $\fu_{\Hamn}=o(n)$ remain widely open.

Thresholds for small-graph Avoider-Forcer games, even in the monotone version,
often differ from the thresholds of Maker-Breaker games.
Hefetz {\em et al.}~\cite{ae09} showed that for the triangle game 
we have 
\begin{equation}\label{triangle}
\fm_{\F_{K_3,n}}=\Theta(n^{3/2}),
\end{equation}
while in the Maker-Breaker triangle game
the threshold is of order $\sqrt n$ (cf.~\cite{CE}). 
In general, for every graph $G$ with at least two edges,
the Maker-Breaker threshold is of order
$n^{1/m_2(G)}$, where $m_2(G)=\max\big\{(e(F)-1)/(v(F)-2):\;F\subseteq G,\,e(F)\ge 2\big\}$,
and $v(F)$ and $e(F)$ denote the number of vertices and edges of $F$ respectively (cf.~\cite{mbtl}).

As for the strict version of small-graph games, the order of the upper or the lower threshold is not 
known for any graph containing a cycle. Not much is known about the thresholds for trees. 
For a path $P_3$ on three vertices we have
$\fl_{\F_{P_{3},n}}=\Theta(n^{3/2})$ and $\fu_{\F_{P_{3},n}}=\binom n2-2$\, (\cite{ae09}). 
We should also mention that
Ferber, Krivelevich and Naor~\cite{aebox} considered
strict Avoider-Forcer $(a:f)$ small-graph games played on dense graphs with $n$ vertices. 
They found a condition sufficient for forcing Avoider to build a copy of a fixed graph $G$, 
provided $a$ and $f$ are fixed and $n$ is large. From their results we can infer that 
if $f+1$ is coprime to every number not greater than $e(G)$ and $f<cn^{2/e(G)}$ with some constant $c$
depending on $G$, then Avoider in $\AF(\FGn,1,f)$ is forced to build a copy of $G$ in $K_n$. 

Here we will be primarily concerned with
 the upper and the lower thresholds 
in \mbox{$d$-degree} and small-graph games played on $K_n$.
For 1-degree strict game, the result (\ref{conn}) implies that $\fl_{\D1n}\ge \lfloor (n-1)/2\rfloor$.
We will show that $\lfloor (n-1)/2\rfloor$ is also the upper bound for 
$\fu_{\D1n}$ and hence $\fl_{\D1n}=\fu_{\D1n}$;
the only exceptions are $n=4$ and $n=7$. 

\begin{theorem}\label{deg1}
For every $n\ge 3$, if $n\neq 4,7$, then 
$$\fu_{\D{1}n}\le \Big\lf\frac{n-1}{2}\Big\rf.$$
\end{theorem}

One can easily check that $\fl_{\D{1}4}=1$ and $\fu_{\D{1}4}=4$. 
With some effort one can calculate that $\fl_{\D{1}7}=\fu_{\D{1}7}=4$. 

\begin{cor}\label{corr}
Let $n\ge 3$. If $n\neq 4$, then the threshold $f_{\D1n}$ exists, and for $n\neq 4,7$
$$f_{\D1n}=f_{\C1n}=\Big\lf\frac{n-1}{2}\Big\rf.$$
\end{cor}

For fixed $d\ge 2$ the inequality $\fu_{\D dn}<n/d$ is obvious, while 
the best known lower estimation of $\fl_{\D d n}$ is $\fl_{\D d n}\ge n/(2d)-1$, 
which  is implied by 
the following result by Hefetz, Krivelevich and  Szab\'o~\cite{ae07}: 
\begin{equation}\label{ae07dconn}
\fl_{\C dn'}\ge \frac{n}{2d}-1.
\end{equation}
Therefore $n/(2d)-1\le \fl_{\D d n}\le \fu_{\D d n}<n/d$.
It would be interesting to find the optimal constants $c,c'>0$ 
(perhaps depending on $d$)
such that $\fl_{\D dn}\ge cn/d$ and $\fu_{\D dn}\le c'n/d$. We did not succeed
in finding such constants even for $d=2$, but we can prove that   
the upper bound $n/d$ on $\fu_{\D dn}$ is not optimal even asymptotically. 

\begin{theorem}\label{deg2}
Let $d\ge 2$ be a fixed integer. Then  
$$\fu_{\D dn}<\frac{n}{\sqrt{(d-1)^2+1}+1}+o(n).$$
%for d=d(n) n/d->\infty: tez, ale o(n/d)
\end{theorem}

As far as strict $d$-degree games with $d=d(n)\to\infty$ are concerned,
the upper and lower thresholds are close to $n/d$.
It is a consequence of the obvious estimation $\fu_{\D dn}<n/d$ and   
Beck's results on {\sl discrepancy games}, which we discuss in Section \ref{kdeg}.

\begin{theorem}[implicit in \cite{TTT}]\label{degbig}
If $d=d(n)=\omega(\sqrt n)$ then
$$\fl_{\D d n}=(1+o(1))\frac nd\quad\text{and}\quad
\fu_{\D d n}=(1+o(1))\frac nd\,.$$
%$$\fl_{\D d n}=(1+o_d(1))\frac nd\quad\text{and}\quad
%\fu_{\D d n}=(1+o_d(1))\frac nd\,,$$
%where $o_d(1)$ is a quantity which tends to 0 as $d\to \infty$. 
\end{theorem}

Theorems \ref{deg1} and \ref{deg2} imply some upper bounds on 
$\fu_{\PMn}$ and $\fu_{\Hamn}$. They are far from the known lower bounds $\Omega(n/\ln n)$,
but are still a little bit better than the obvious
estimations $\fu_{\PMn}<n$ and $\fu_{\Hamn}<0.5n$.

\begin{cor}\label{corr2}\ 

\begin{itemize}
\item[(i)]
$\fu_{\PMn}\le\big\lf\frac{n-1}{2}\big\rf$ for every even $n\neq 4$. 
\item[(ii)]
$\fu_{\Hamn}< 0.42\,n +o(n)$.
\end{itemize}
\end{cor}

Finally let us mention some new results on small-graph games. 
To this end we define three graph parameters (here and below 
we assume that $e(G)\ge 2$):
\beqa
m(G)&=&\max\limits_{F\subseteq G:\,v(F)\ge 1}\frac{e(F)}{v(F)},
\quad
m'(G)=\max\limits_{F\subseteq G:\,v(F)\ge 1}\frac{e(F)-1}{v(F)},\\ 
m_2(G)&=&\max\limits_{F\subseteq G:\,e(F)\ge 2}\frac{e(F)-1}{v(F)-2}\,.
\eeqa
Based on Theorem \ref{awf}, we will derive the following upper bounds on the mono\-tone/up\-per/lo\-wer 
thresholds of $\AF(\FGn,1,f)$ and  $\AFm(\FGn,1,f)$.

\begin{theorem}\label{smalla} 
Let $G$ be a graph with at least two edges. %2 wazne dla (i) bo m', dla (ii) i (iii) bo 1-kraw. zle
Then the following holds.
\begin{enumerate}[(i)]
\item\label{fplus}
$\fm_{\FGn}=O(n^{1/m'(G)})$ and $\fu_{\FGn}=O(n^{1/m'(G)})$.
\item\label{fminln}
%if $G$ contains two adjacent edges, then 
$\fl_{\FGn}=O(n^{1/m(G)}\ln n)$.
\item\label{fmin}
%if $G$ contains two adjacent edges, then 
$\fl_{\FGn}<c n^{1/m(G)}$ for 
some constant $c$ and infinitely many $n$. 
\item\label{defence}
For some constant $c$,  sufficiently large $n$,
and $f>c n^{1/m(G)}$, Avoider can avoid  a copy of $G$ until the last but one turn
of $\AF(\FGn,1,f)$ and  $\AFm(\FGn,1,f)$. 
\end{enumerate}
\end{theorem}

Note that  (\ref{fplus}) gives an alternative proof of the fact that
$\fm_{\F_{K_3,n}}=O(n^{3/2})$. 
In (\ref{fminln}) and (\ref{fmin}) the constant exponent $1/m(G)$  cannot be improved in general,
because for $G=P_3$ we have $\fl_{\FGn}=\Theta(n^{1/m(G)})$.
For an application of (\ref{defence}),  consider the triangle monotone game $(1:f)$,
with $f$ of order greater than $n$ but less than $n^{3/2}$.
We know by (\ref{triangle}) that Forcer has a winning strategy;
(\ref{defence}) implies that Avoider 
can defend almost to the very end of the game. 

\begin{theorem}\label{smallf}  \

\begin{itemize}
\ss\item[(i)]
$\fl_{\F_{K_3,n}}=\Omega(n^{1/2})$. 
\ss\item[(ii)]
$\fl_{\FGn}=\Omega(n^{1/m_2(G)}/\ln n)$ and $\fm_{\FGn}=\Omega(n^{1/m_2(G)}/\ln n)$
for every graph $G$ with at least two edges.
\end{itemize}
\end{theorem}
The first part of the above theorem is a consequence of a winning condition for Forcer,
which is presented in the next section.
The second part is implied by Theorem \ref{ae07} and
the recent hypergraph container theorem by Saxton and Thomason \cite{container1}.

The paper is organized in the following way. In Section \ref{main} we prove Theorems \ref{awf} 
and \ref{awfopt} and discuss some variants of Beck's winning condition for Forcer.
In Section \ref{kdeg} we prove Theorems \ref{deg1} and \ref{deg2}, and explain how 
Theorem \ref{degbig} follows from Beck's results on discrepancy games. 
In Section \ref{small} we prove Theorems \ref{smalla} and \ref{smallf}.


%%%%%%%%%% main %%%%%%%%%%%%%%%


\section{Winning criteria for Avoider and Forcer}\label{main}

Apart from the definitions stated in the introduction, we will use the following notation. 

By $\Delta(\F)$ we denote the maximum degree of the hypergraph $\F$, 
i.e.~$$\Delta(\F)=\max_{x\in V(\F)}|\{D\in E(\F):\, x\in D\}|.$$
Additionally, we set
$$\Delta_2(\F)=\max_{x,y\in V(\F),\,x\neq y}|\{D\in E(\F):\, x,y\in D\}|.$$
%and say that $\F$ is {\sl almost disjoint} if $\Delta_2(\F)\le 1$.

Given a hypergraph $\F$ and $X\subs V(\F)$, we denote by $\F\setm X$ 
the hypergraph with the vertex-set $V(\F)\setm X$ and
the edge-multiset $\{D\setm X:\, D\in E(\F)\}$. 
By $\F-X$ we mean the hypergraph with the vertex-set $V(\F)\setm X$ and the edge-multiset 
$\{D\in E(\F):\, D\cap X=\emptyset\}$. 
We mean by $\F_X$  the subhypergraph of $\F$, induced by all edges $D\in E(\F)$ such that $X\subs D$.
For simplicity we write $\F_{x_1,x_2,\ldots,x_t}$ instead
of $\F_{\{x_1,x_2,\ldots,x_t\}}$.

Suppose that at a given moment of a game played on a hypergraph $\F$, the set $X$ consists of
all vertices Avoider has selected so far and $Y$ is the set of vertices which belong to Forcer.
Then we call the hypergraph $(\F\setm X)-Y$ {\sl the position} at that moment of the game. 
The position after the $i$th turn will be denoted by $\F(i)$, with the technical assumption that
$\F(0)=\F$. 


Given a hypergraph $\F$ and a real number $\mu>0$,  
we define {\sl the weight} $T_\mu$ of the hypergraph $\F$ as follows:
$$T_\mu(\F)=\sum_{D\in E(\F)}\mu^{-|D|}.$$

Notice that in the final position $\F'$ of an Avoider-Forcer game we have either 
$E(\F')=\emptyset$ and $T_\mu(\F')=0$ or $\emptyset\in E(\F')$ and $T_\mu(\F')\ge 1$.
Hence the final position is won by 
Forcer if and only if its weight $T_\mu$ is positive. 


\subsection{Winning condition for Avoider}\label{awin}

\begin{proof}[Proof of Theorem \ref{awf}.]
The proof of part (i) relies on the standard technique of minimizing the weight of the position,
used by Beck for proving the winning condition (\ref{beckwf}) for Breaker in Maker-Breaker games.
For completeness, we repeat briefly this argument and point out
where our proof is different from the proof of Theorem \ref{ae07}.

Consider the weight function $T=T_\mu$ with $\mu=\frac{f}{ar}+1$  
and suppose that Avoider uses {\sl a min-weight strategy}. 
More precisely, for every $i\ge 0$, in turn $i+1$ Avoider selects $a$ vertices $x_1,\ldots, x_a$
such that  
$x_{1}$ minimizes $T(\F(i)_{x})$ over all $x\in V(\F(i))$ and for $j=1,\ldots,a-1$
the vertex $x_{j+1}$ minimizes $T((\F(i)\setm\{x_1,\ldots,x_j\})_{x})$ over all $x\in V(\F(i)\setm\{x_1,\ldots,x_j\})$. 
We will show that 
the weight $T$ of the position, evaluated after every Forcer's move, 
does not increase in the course of the game.

Suppose that the play has $t$ turns and let $0\le i\le t-2$. Let 
$X=\{x_1,\ldots,x_a\}$ and $Y=\{y_1,\ldots,y_b\}$ with $b\ge f$ be the sets of all vertices selected 
in the $(i+1)$st turn by Avoider and Forcer respectively.
Notice that based on the definition of the min-weight strategy and the definition of $T$, 
$$T(\F(i)_{x_1})\le T(\F(i)_{x_a})\le T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x_a}),$$ 
and similarly, for $j=1,\ldots,a-2$,
\beqa
T((\F(i)\setm\{x_1,\ldots,x_j\})_{x_{j+1}})&\le& T((\F(i)\setm\{x_1,\ldots,x_j\})_{x_a})\\
&\le& T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x_a}).
\eeqa 
Furthermore, the function $T$, evaluated after selecting the vertices by Avoider, equals 
$$T(\F(i))+(\mu-1)\big[T(\F(i)_{x_1})+T((\F(i)\setm\{x_1\})_{x_2})+\ldots+
T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x_a})\big].$$
Hence Avoider's move $X$ increases $T$ by not more than 
$$a(\mu-1)T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x_a}).$$

Starting with $T(\F(i)\setm\{x_1,\ldots,x_{a}\})$, we will estimate 
the decrease of $T$ caused by Forcer's choice of $Y$. 
At this point our analysis veers away from the proof of Theorem \ref{ae07}.
 
After the move of Forcer, $T$ decreases by
\beqa
\sum_{\stackrel{D\in E(\F(i)\setm\{x_1,\ldots,x_{a}\})\colon}{D\cap Y\neq\emptyset}}\mu^{-|D|}
&\ge& 
\frac{1}{r}\sum_{\stackrel{D\in E(\F(i)\setm\{x_1,\ldots,x_{a}\})\colon}{D\cap Y\neq\emptyset}}|D|\mu^{-|D|}
\ge
\frac{1}{r}\sum_{y\in Y}\sum_{\stackrel{D\in E(\F(i)\setm\{x_1,\ldots,x_{a}\})\colon}{y\in D}}\mu^{-|D|}\\
&=&
\frac{1}{r}\sum_{y\in Y}T((\F(i)\setm\{x_1,\ldots,x_{a}\})_y)\\
&\ge&
\frac{1}{r}\sum_{y\in Y}T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_y)\\
&\ge&
\frac{f}{r} T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x_a}).
\eeqa 
In the last inequality we used the property that 
$x_{a}$ minimizes $T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x})$ over all $x\in V(\F(i)\setm\{x_1,\ldots,x_{a-1}\})$.

Summarizing, the change of $T$ in the $(i+1)$st turn is
\beqa
T(\F(i+1))-T(\F(i))&\le& 
a(\mu-1)T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x_a})\\
&& -\frac{f}{r} T((\F(i)\setm\{x_1,\ldots,x_{a-1}\})_{x_a}),
\eeqa
which is nonpositive as $\mu=\frac{f}{ar}+1$.
Consequently, we proved that $T(\F(i))\le T(\F(0))=T(\F)$ for $i=1,\ldots,t-1$. 

Consider the last, $t$th, turn;
Avoider takes a set $X$ of $a$ elements (or less, if it is not possible) 
 and Forcer takes some remaining elements. Then 
$$T(\F(t))\le \sum_{D\in E(\F(t-1))}\mu^{|D\cap X|}\mu^{-|D|}\le \mu^{a}T(\F(t-1))
\le \mu^{a}T(\F).$$ 
By the assumption of our theorem $T(\F)<\mu^{-a}$, so the above inequality implies that 
$T(\F(t))<1$.
It means that in the end position Avoider has no edge of $\F$ entirely occupied.

The proof of part (ii) is almost the same. It is even easier since we do not have to analyze 
the last turn separately.
\end{proof}


\begin{proof}[Proof of Theorem \ref{awfopt}.]
Suppose that $a,f,r,n\ge 1$ and $\F$ is 
a hypergraph with $n$ pairwise disjoint edges, each of size $r$. 
Ferber, Krivelevich and Naor~\cite{aebox} proved that if 
$$
N(a,f,k)=\begin{cases}
f+1 &\text{for } k< a+1,\\
f+1+\big\lc \frac f{a+1}\big\rc &\text{for } k=a+1,\\
\big\lc \frac{N(a,f,k-1)}{a}\big\rc\big(a+\big\lc \frac fk\big\rc\big) &\text{for } k>a+1,
\end{cases}
$$
and $n\ge N(a,f,r)$, then Forcer wins $\AFm(\F,a,f)$.  
%(and the assumption that Avoider starts the game is irrelevant). 

Assume that $n=N(a,f,r)$, $r\ge 3a$, and $a,r$ can depend on $f$. Additionally, let $ra=o(f)$.
We will show that 
\beq{nsmall}
n< \Big(\frac{3f}{ar}+1\Big)^{r-a},\quad\text{provided $f$ is sufficiently large.}
\eeq
Clearly it will imply that $\F$ satisfies the assumption of Theorem \ref{awfopt}.  
It will also complete our proof because of the above mentioned result by Ferber, Krivelevich and Naor.

By the definition of $N(a,f,k)$, we have $N(a,f,k)>f$ and for $k>a+1$
\beqa
N(a,f,k)&<&\Big(\frac{N(a,f,k-1)}{a}+1\Big)\Big(a+\frac fk+1\Big)\\
&\le& N(a,f,k-1)\Big(\frac{f}{ak}+2\Big)+a+\frac{f}{k}+1\\
&<& N(a,f,k-1)\Big(\frac{f}{ak}+2\Big)+a+\frac{N(a,f,k-1)}{k}+1\\
&<&N(a,f,k-1)\Big(\frac{f}{ak}+5\Big),
\eeqa
where in the last inequality we assumed that $a<f$.
Hence, for $ra=o(f)$ we obtain
\beqa
N(a,f,r)&<&N(a,f,a+1)\Big(\frac{f+o(f)}{a}\Big)^{r-a-1}\prod_{k=a+2}^r\frac1k\\
&=&\Big(f+1+\Big\lc\frac{f}{a+1}\Big\rc\Big)\Big(\frac{f+o(f)}{a}\Big)^{r-a-1}\prod_{k=a+2}^r\frac1k\\
&=&\frac{a+2}{a+1}(f+o(f))\Big(\frac{f+o(f)}{a}\Big)^{r-a-1}\prod_{k=a+2}^r\frac1k\\
&=&\Big(\frac{f+o(f)}{a}\Big)^{r-a}a(a+2)\prod_{k=a+1}^r\frac1k\\
&=&\Big(\frac{f+o(f)}{a}\Big)^{r-a}a(a+2)\frac{a!}{r!}.
\eeqa

Thus for sufficiently large $f$ 
\beqa
\frac{N(a,f,r)}{\Big(\frac{3f}{ar}+1\Big)^{r-a}}
&<&(1+o(1))^{r-a}\,\frac{a!a(a+2)r^{r-a}}{r!3^{r-a}}
<\frac{a!a(a+2)r^{r-a}}{r!e^{r-a}}\\
&<&\frac{a!a(a+2)e^a}{\sqrt{2\pi r}\cdot r^a}
<\frac{a!a(a+2)}{\sqrt{6a\pi}\cdot a^a},
\eeqa
where in the last inequality we used the assumption that $r\ge 3a$.
By routine calculations we check that the right-hand side of the obtained 
inequality is less than 1 for every $a\ge 1$. 

Hence (\ref{nsmall}) holds and the proof of Theorem \ref{awfopt} is complete.
\end{proof}


\subsection{Winning criteria for Forcer}\label{fwin}

In this section we present a few winning criteria for Forcer in $\AF(\F,a,f)$, which
are slight modifications of Beck's winning condition from \cite{TTT}. 
Let $\FA(\F,a,f)$ denote the game which differs from $\AF(\F,a,f)$ by only one rule, in
$\FA(\F,a,f)$ Forcer is the first player.
  
\begin{theorem}[implicit in \cite{TTT}]\label{bc}
Suppose that 
\beq{bfwin}
T_{f/a+1}(\F)=\sum_{D\in E(\F)}\Big(\frac fa +1\Big)^{-|D|}>\frac{f^2a^2}{(f+a)^3}\,\Delta_2(\F)|V(\F)|
\eeq
and $f+a$ divides $|V(\F)|$. Then Forcer has a winning strategy for $\FA(\F,a,f)$. 
\end{theorem}

Beck proved that (\ref{bfwin}) guarantees the win of Maker in $\MB(\F,a,f)$ 
(cf.~\cite{TTT}, Theorem 2.2) and remarked that by a very similar proof, one can show
the analogous result for Forcer in Avoider-Forcer games.  
It follows from the proof of Beck's Theorem 2.2 in \cite{TTT} that the divisibility assumption 
in Theorem \ref{bc} is quite important, though irrelevant in the case of Maker-Breaker games.

We can formulate a theorem similar to Theorem \ref{bc} if Avoider 
is the first player, provided he takes the last unoccupied vertex in the game. 
Forcer can simply ignore the first move of Avoider, pretend he starts the game, 
and use a winning strategy guaranteed by Theorem \ref{bc}. 

\begin{cor}
Suppose that 
$$
T_{f/a+1}(\F)>\frac{f^2a^2}{(f+a)^3}\,\Delta_2(\F)|V(\F)|
$$
and $f+a$ divides $|V(\F)|-a$. Then Forcer has a winning strategy for $\AF(\F,a,f)$.
\end{cor}

The technique of the proof of Theorem \ref{bc} allows us to solve the above divisibility problems
in the following way.

\begin{theorem}\label{bcc}
If
$$T_{f/a+1}(\F)>
\frac{f^2a^2}{(f+a)^3}\,\Delta_2(\F)|V(\F)|+\Delta(\F)\frac{fa}{f+a}\,,$$
then Forcer has a winning strategy for $\AF(\F,a,f)$, $\FA(\F,a,f)$ and $\AFm(\F,a,f)$.
\end{theorem}

\begin{proof}
Let $T=T_{f/a+1}$.
The key realization for the proof of Theorem \ref{bc} (and the proof of 
Beck's Theorem 2.2 in \cite{TTT})
is that Forcer in $\FA(\F,a,f)$ can play so that
for every $i$, if $|V(\F(i))|\ge a+f$, then
\begin{equation}\label{incr}
T(\F(i+1))\ge T(\F(i))-\Big(\frac{fa}{f+a}\Big)^2\,\Delta_2(\F).
\end{equation}
Forcer in $\AF(\F,a,f)$ can use this strategy as well
by ignoring the first move of Avoider. Furthermore, the same Forcer's strategy guarantees
the property (\ref{incr}) in $\AFm(\F,a,f)$ since 
the assumption that Avoider can take more than $a$ vertices per turn is not relevant
for the proof of Theorem \ref{bc}.

Therefore, if $\F'$ is the position before the last move of 
Forcer in $\AF(\F,a,f)$, or $\FA(\F,a,f)$, or $\AFm(\F,a,f)$, we have 
$$T(\F')> T(\F)-\Big(\frac{fa}{f+a}\Big)^2\,\Delta_2(\F)\frac{|V(\F)|}{f+a}\,.$$
Consequently, by the assumption of Theorem \ref{bcc} we obtain
$$T(\F')>\Delta(\F)\frac{fa}{f+a}\,.$$

Now we consider the effect of Forcer's last move. 
Every nonisolated vertex $x$ of $\F'$ belongs to at most $\Delta(\F)$ edges 
of size at least one, so 
$T(\F'_x)\le \Delta(\F)/(f/a+1)$. 
Forcer in his last move takes at most $f$ (remaining) vertices and hence 
the weight $T$ of the hypergraph obtained at the end of the game is not less than
$$T(\F')-f\frac{\Delta(\F)}{f/a+1}=T(\F')-\Delta(\F)\frac{fa}{f+a},$$
which is positive. 

We conclude that the end position is a win for Forcer. 
\end{proof}


%Theorem \ref{bcc} will be sufficient to prove the first part of Theorem \ref{smallf}, 
%but not strong enough for the second part, in the case of graphs with more than three vertices.


%%%%%%% kdeg %%%%%%%%%%%%%%%%%%%%%%%

\section{Degree games}\label{kdeg}

\subsection{Big degree games}

Let $b$ be a natural number. We have two players; Balancer who takes 
exactly $b$ free edges of $K_n$ per turn and 
Unbalancer who takes 1 free edge of $K_n$ per turn. 
Let $d_B(v)$ denote the number of 
Balancer's edges incident to $v\in V(K_n)$ at the end of the game. 
Balancer tries to get the degree balance roughly $b:1$, 
i.e.~he wants to obtain the number
$$\max\limits_{v\in V(K_n)}\Big|d_B(v)-\frac{b(n-1)}{b+1}\Big|$$ 
as small as possible.
We call this game {\sl the discrepancy $(b:1)$ game} on $K_n$. By default 
Balancer is the first player. However, we will also consider the discrepancy $(b:1)$ games 
in which Unbalancer starts the game.

The discrepancy $(b:1)$ game  on $K_n$ belongs to a much more general class of  
discrepancy $(b:u)$ games on hypergraphs, with $u\ge 1$, studied by Beck \cite{TTT}.  
Below we present a special case of Beck's result. 

\begin{theorem}[\cite{TTT}, Thm.~27.5]\label{discr}
Let $b=b(n)=o(n/\ln n)$ and $b+1\mid \binom n2$. Then for some constants $c,c'>0$
Balancer as the first player has a strategy in the discrepancy $(b:1)$ game  on $K_n$ 
such that for every $x\in V(K_n)$ 
\beq{discrerr}
\frac{b(n-1)}{b+1}-c'\sqrt{\frac{n\ln n}{b+1}}\le d_B(x)\le \frac{b(n-1)}{b+1}+c\sqrt{\frac{n\ln n}{b+1}}.
\eeq
\end{theorem}

\noindent
{\bf Remark.} In the cited theorem of Beck there is no divisibility assumption, however, the method of 
the proof requires that every move of Balancer is followed by Unbalancer's move. 
%Let us recall that in the proof of Theorem \ref{discr} Balancer in every turn minimizes 
%some weight function so that the function
%$$W(i)=
%does not increase.

We can solve
the problem of the last turn and get rid of the assumption $b+1\mid \binom n2$ by replacing 
the condition (\ref{discrerr}) by 
$$
\frac{b(n-1)}{b+1}-c'\sqrt{\frac{n\ln n}{b+1}}-b\le d_B(x)\le 
\frac{b(n-1)}{b+1}+c\sqrt{\frac{n\ln n}{b+1}}+b,
$$  
since in the last move Balancer cannot change degrees in his graph more than by $b$. 

If we assume that Balancer in the discrepancy game is the second player, we can ignore the first 
move of Unbalancer and obtain almost the same condition (\ref{discrerr}) for Balancer's degrees, provided
$b+1\mid \binom n2-1$. The forgotten move of Unbalancer can influence Balancer's degrees only by one,
which is asymptotically irrelevant.  
Again we can get rid of the assumption $b+1\mid \binom n2-1$ if we change the degree bounds by $b$.
Summarizing, we obtain the following corollary.

\begin{cor}\label{beckcor}
Let $b=b(n)=o(n/\ln n)$. Then for some constants $c,c'>0$
Balancer as the second player in the discrepancy $(b:1)$ game on $K_n$ 
has a strategy such that for every $x\in V(K_n)$ 
$$
\frac{b(n-1)}{b+1}-c'\sqrt{\frac{n\ln n}{b+1}}-b\le d_B(x)
\le \frac{b(n-1)}{b+1}+c\sqrt{\frac{n\ln n}{b+1}}+b.
$$
\end{cor}

We are ready to justify Theorem \ref{degbig}, which says that for $d=d(n)=\omega(\sqrt n)$ 
$$\fl_{\D d n}=(1+o(1))\frac nd\quad\text{and}\quad\fu_{\D d n}=(1+o(1))\frac nd\,.$$
 
\begin{proof}[Proof of Theorem \ref{degbig}.]
Let $d=d(n)=\omega(\sqrt n)$. Since $\fl_{\D d n}\le\fu_{\D d n}<n/d$, 
it is enough to prove that $\fl_{\D d n}\ge (1+o(1))\frac nd\,$. 

Assume that Forcer has a winning strategy for $\AF(\D d n,1,f)$. 
Of course $f\le \fu_{\D d n}<n/d$.
Additionally, by (\ref{ae07dconn}) we know that if $f\le n/(2d)-1$, then 
Forcer can force Avoider to build 
a $d$-edge-connected spanning graph and therefore he can win $\AF(\D d n,1,f)$.
Therefore we assume that $n/(2d)\le f<n/d$. 

We have $f=\Theta(n/d)=o(\sqrt n)=o(n/\ln n)$, so
Forcer in $\AF(\D d n,1,f)$ can use the strategy of
Balancer described in Corollary \ref{beckcor} with $b=f$. This way
at the end of the game $\AF(\D d n,1,f)$
the maximum degree of Forcer's graph is not greater than 
$\frac{(n-1)f}{f+1}+c\sqrt{\frac{n\ln n}{f+1}}+f$ for some constant $c>0$. It means that 
the minimum degree of Avoider's final graph is not less than
$$\frac{n-1}{f+1}-c\sqrt{\frac{n\ln n}{f+1}}-f> \frac{n-1}{f+1}-c\sqrt{2d\ln n}-\frac nd\,.$$
The latter expression is not less than $d$ for
$$f\le \frac{n-1}{d+c \sqrt{2d\ln n}+n/d}-1,$$
so for $d=\omega(\sqrt n)$ we obtain 
$$f\le(1+o(1))\frac nd\,.$$

Consequently, Avoider loses $\AF(\D d n,1,f)$ for every such $f$, which means that 
$\fl_{\D d n}\le (1+o(1))\frac nd$.  
\end{proof}


\subsection{Proof of Theorem \ref{deg1}}

Let $n\ge 3$ and $f>\lf\frac{n-1}{2}\rf$. It is easy to calculate that at the end of the game $\AF(\D{1}n,1,f)$
Avoider will have at most $n-2$ edges occupied. 
We will show that 
Avoider wins by building first a tree as big as possible 
and then by continuing the play almost arbitrarily. 

Avoider starts with selecting any edge of $K_n$ and then, in every position in which Avoider's edges
span a tree $T$, he selects any free edge from $E(V(T),V(K_n)\setm V(T))$, if possible;
by $E(A,B)$ we denote the set of all edges $vv'$ with $v\in A$ and $v'\in B$. 

If he is able to continue to build his tree until the end of the game, 
then clearly at least one vertex in Avoider's graph remains isolated.
By Avoider's graph at a given moment of the game we mean a graph with the vertex-set $V(K_n)$ 
and with the edges selected
by Avoider so far. Therefore we can assume that in some turn 
Avoider cannot increase his tree. 

Let $k$, with $2\le k\le n-2$, be the first turn in which Avoider cannot extend his tree
$T$, i.e.~$|V(T)|=k$ and all the edges from $E(V(T),V(K_n)\setm V(T))$ have been selected by Forcer.
Then the number of edges Forcer has selected so far is
$$(k-1)f\ge |E(V(T),V(K_n)\setm V(T))|=k(n-k)$$
and hence $n-k\le f-1$. 
We will consider two cases: $n-k>2$ and $n-k=2$.

Suppose that $n-k>2$. For $i\ge k$, in his $i$th move 
Avoider selects arbitrarily a free edge from $E(V(T),V(T))$ as long as there is any.
Let $t$ be the last turn in which such free edges exist (and $t\ge k-1$). 
Then we have at most $\binom{n-k}{2}$ free edges left and $n-k$ isolated vertices in Avoider's graph. 
By simple calculations one can check that if $3\le n-k\le f-1$, then 
$\binom {n-k}2\le (f+1)\lf\frac{n-k-1}{2}\rf$. 
Hence after turn $t$ the game will last at most $\lf\frac{n-k-1}{2}\rf$ turns. 
We infer that Avoider will leave one of his $n-k$ isolated 
vertices untouched, no matter how he plays in the remaining turns. 
Thus Avoider wins the game.   

Now consider the case $n-k=2\,$. Since $k\ge 2$, we have $n\ge 4$. 
We have assumed that after turn $k-1$ the game has not ended yet, 
which implies that $(k-1)(f+1)<\binom n2$. Additionally, the game lasts no more than $n-2$ turns
so the $k$th turn is the last one. Let us recall that after $k-1$ turns there are two isolated
vertices in Avoider's graph, say $v$ and $v'$. If there is any free edge except of $vv'$,
Avoider in his last move selects it and wins the game. Suppose that $vv'$ is the only free edge
before the $k$th move of Avoider. Then $(k-1)(f+1)=\binom n2-1$. 
By solving this equation for $k=n-2\ge 2$ 
we obtain that $f+1=(n+1)(n-2)/(2(n-3))$, so either $n=f=4$ or $n=7$ and $f=4$.

In view of the above analysis, we conclude that Avoider wins $\AF(\D{1}n,1,f)$ for every 
$f>\lf\frac{n-1}{2}\rf$, provided $n\neq 4,7$. Hereby the proof is complete.

\medskip\noindent {\bf Remark.} 
For $n=7$ the above argument implies that $\fu_{\D{1}n}\le 4$. It appears that
$\AF(\D{1}7,1,4)$ is a win for Forcer. Forcer wins the game if he stands by the following rules.

\begin{enumerate}[1)]
\item\label{part1}
As long as there are at least two isolated vertices in Avoider's graph:
\begin{itemize}
\item
He prevents Avoider from building any cycle.
\item
In every move, if possible, Forcer selects free edges $vv'$ such that $v$ and $v'$ 
have positive degree in Avoider's graph; 
if there are no more of these edges, he finishes his move by selecting edges 
with exactly one endpoint of positive degree in Avoider's graph.
\end{itemize}
\item
At the moment the sixth vertex, say $v_6$, of positive degree appears in Avoider's
graph and there is still one isolated vertex $v_7$ in Avoider's graph, 
Forcer continues to play arbitrarily, leaving $v_6v_7$ free as long as possible.
\end{enumerate}
We skip the proof that such a strategy can be carried out by Forcer, 
but we will verify that it is a winning strategy for him.
Note that there are five edges in Avoider's final graph, and it contains no cycle
by Forcer's strategy. Therefore, it has at least six vertices of positive degree. 
Consider the moment the sixth vertex, say $v_6$, of positive degree appears in Avoider's
graph. Then if no vertex is isolated in Avoider's graph, Forcer wins
the game. Thus suppose there is still one isolated vertex $v_7$ in Avoider's graph. 
It follows from \ref{part1}) that the edge $v_6v_7$ is free. 
Forcer can continue to play arbitrarily, leaving $v_6v_7$ free until Avoider selects a free edge incident to $v_7$
(notice that Avoider selects the last free edge in the game). Thereby Forcer wins $\AF(\D{1}7,1,4)$.   


\subsection{Proof of Theorem \ref{deg2}}

Throughout this section we assume that $d\ge 2$. Additionally, we consider $f\ge n/(2d)$ only,
because otherwise, in view of (\ref{ae07dconn}), Forcer wins $\AF(\D dn,1,f)$. 
Another assumption is that $f+1\le (n-1)/d\,$; otherwise the game $\AF(\D dn,1,f)$ lasts
less than $nd/2$ turns and Avoider trivially wins.   

The idea of the proof is quite simple. We will show that 
Avoider can build a spanning tree with many leaves. If $f$ is greater than, roughly,
$\frac{n}{\sqrt{(d-1)^2+1}+1}$, there will be too few moves left for Avoider to increase 
the degree of every leaf by $d-1$.  

Let us assume that Forcer has a winning strategy for $\AF(\D dn,1,f)$. 
In the lemma below by {\sl a greedy algorithm} we mean any strategy of  
Avoider such that after every his move the graph
induced by Avoider's edges is a tree.

\begin{lemma}\label{tree}
If Forcer has a winning strategy for $\AF(\D dn,1,f)$, then Avoider can build a spanning 
tree within the first $n-1$ turns of the game by using any greedy algorithm. 
\end{lemma} 

\begin{proof}
Suppose for contradiction that Avoider builds greedily his tree, but 
after $k-1<n-1$ turns he got stuck. Then $n-k\le f-1$, as we already calculated in the proof of 
Theorem \ref{deg1}. Avoider can win the game continuing the play in the following way. 
Let $T$ be his tree built within $k-1$ first moves.
Avoider takes free edges with both endpoints in $V(T)$ as long as possible. 
Then he forgets about the set $V(T)$ and transforms the game into $\AF(\D d{n-k},1,f)$,
played on the complete graph $K_{n-k}$ with the vertex-set $V(K_n)\setm V(T)$, 
possibly with some edges of $K_{n-k}$ occupied already by Forcer. 
Such a game, for $d\ge 2$ and $n-k\le f-1$, has less than $(n-k)d/2$ turns. 
Therefore at the end of the game at least one vertex of $K_{n-k}$ will have 
degree less than $d$ in Avoider's graph, which contradicts the assumption that Forcer 
wins. 
\end{proof}

Now we describe how Avoider builds a rooted spanning tree in $\AF(\D dn,1,f)$. It is a greedy, 
BFS-like algorithm. Starting with any vertex $v_0$, the root, 
in consecutive turns $j\ge 1$ Avoider   
increases his tree on the vertex-set $\{v_0,v_1,\ldots,v_{j-1}\}$ 
by a vertex $v_j$ in the following way.
Avoider finds the smallest $i\le j-1$ such that for some $x\not\in\{v_0,v_1,\ldots,v_{j-1}\}$
the edge $v_ix$ is free. 
Then he selects arbitrarily one such free edge 
and denotes its end (other than $v_i$) by $v_j$. 
We know by Lemma \ref{tree} that Avoider can continue building his tree for $j=1,\ldots,n-1$.

Consider the situation after the $(n-1)$st turn. Let $T$ be the spanning tree of Avoider and $L$ be
the set of its leaves. Throughout the rest of the proof the terms: leaves, parents, children, internal vertices, 
refer always to $T$. By the level of a vertex of $T$ we mean the distance in $T$ 
between $x$ and $v_0$. We say that $v_i$ {\sl is younger} than $v_j$ if $i>j$. 
By $L_k$ we denote the set of $k$ youngest leaves of $T$, for $k=1,\ldots,|L|$.
{\sl Avoider's degree} of a vertex $x$ at a given moment of the game is the number of edges 
incident to $x$, selected by Avoider so far. 

The following two lemmata will allow us to prove that $T$ has many leaves. 

\begin{lemma}\label{free}
Let $k\ge 3$. Suppose that $\binom k2\le f+1$ and there are $k$ vertices in $L$ with
at most $t$ free edges of $K_n$ incident to each of them. If 
$$t\le \Big(d-1-\frac2k\Big)(f+1),$$
then Avoider has a strategy such that at the end of $\AF(\D dn,1,f)$ there is a vertex of degree less
than $d$ in Avoider's graph.
\end{lemma}

\begin{proof}
Let $L'\subs L$ be a set of $k$ vertices satisfying the assumptions of the lemma. Avoider continues the 
game in the following way. In the first stage, as long as possible, he selects free edges not 
incident to any vertex from $L'$.  
After the first stage there are at most $tk$ free edges of $K_n$ left. In the second stage
Avoider selects free edges from $E(L',V(K_n)\setm L')$, as long as there are any. Note that every such move 
of Avoider increases the degree of only one vertex in $L'$ and after the second stage there are at most 
$\binom k2\le f+1$ free edges left. Thus we have at most one turn left after the second stage. In that turn 
Avoider increases by one the degree of two vertices of $L'$. 

Summarizing,  after the first stage the game lasts no longer than $\lc tk/(f+1)\rc$ turns 
and the sum of Avoider's degrees of vertices in $L'$ increases at most by $\lc tk/(f+1)\rc+1$.
Therefore, if $tk\le ((d-1)k-2)(f+1)$, then at least one vertex from $L'$ has degree less than $d$
at the end of $\AF(\D dn,1,f)$.
\end{proof}  


\begin{lemma}\label{inter}
Let $3\le k\le |L|$ and $x\in L_k$. 
Then there are less than $3k$ internal vertices $y$ such that the edge $xy$ is free. 
\end{lemma}

\begin{proof}
Let us start with the following observation, which is a result of the strategy of Avoider. 
We omit its straightforward inductive proof.
 
\medskip\noindent
{\it Observation.} 
Suppose that $x,y\in V(T)$ and $y\not\in L$. If an edge $xy$ is free, then $y$ is younger than 
the parent of $x$ and the level of $y$ differs from the level of $x$ by at most one.

\medskip
Suppose now that $x\in L_k$ and $l$ is the level of $x$. Since there are less than $k$ leaves younger 
than $x$, at level $l-1$ we have less than $k$ internal vertices younger than the parent of $x$.
Also there are less than $k$ internal vertices at level $l$, and at level $l+1$ too.  
Thus, by the above Observation, there are less than $3k$ internal vertices $y$ such that the edge $xy$ 
is free. 
\end{proof}

Observe that $|L|\ge d+1\ge 3$. This fact is obvious if $d=3$ because  
of the greedy strategy of Avoider and the assumption that $d(f+1)\le n-1$.
Also in the case of $d=2$ Avoider's tree has at least three leaves; from the greedy 
strategy of Avoider we infer that if he has selected only two edges incident to the root $v_0$,
then the child $v_1$ has degree greater than two in Avoider's graph. 
Therefore we can apply Lemmata \ref{free} and \ref{inter} with $k=3$. 

By Lemma \ref{free} and the assumption that Avoider cannot win the game, we obtain that 
for some $x\in L_3$ the number of all free edges incident to $x$ is greater than
$\big(d-1-\frac2{3}\big)(f+1)=(d-\frac 53)(f+1)\,.$ 
Furthermore, by Lemma \ref{inter}, less than nine free edges join $x$ with internal vertices.
Consequently
$$|L|>\Big(d-\frac 53\Big)(f+1)-9> 5\sqrt f$$
for sufficiently big $f$ or, equivalently, for big $n$ (we assumed that $n/(2d)\le f<n/d$).

In view of the above inequality we can apply Lemmata \ref{free} and \ref{inter} again, with 
$k=\lc\sqrt f\,\rc$. Hence for some $x\in L_k$ there are more than
$(d-1-\frac2{k})(f+1)-3k>(d-1)f-5\sqrt f\,$ 
leaves adjacent to $x$ with a free edge. We conclude that
$$|L|>(d-1)f-5\sqrt f.$$

Let us recall that so far we have analyzed $(n-1)$ turns, so in the game there are
$\lc \binom n2/(f+1)\rc-(n-1)$ turns left. We also assumed that
Forcer has a winning strategy. Hence Avoider's degree of every vertex in $L$ 
has to increase during these remaining turns from 1 up to $d$, which requires at least $|L|(d-1)/2$ moves. 
Therefore  
$$\Big\lc\frac{\binom n2}{f+1}\Big\rc-(n-1)\ge \frac12|L|(d-1)>\frac12(d-1)^2f-\frac52(d-1)\sqrt f\,,$$
then we obtain  
$$f<\frac{n}{\sqrt{(d-1)^2+1}+1}+o(n),$$
which proves that $\fu_{\D dn}<\frac{n}{\sqrt{(d-1)^2+1}+1}+o(n)$.


%%%%%%%%%%%%%%%%%%%%%%%% smallg %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Small-graph games}\label{small}

In strict Avoider-Forcer games on $K_n$ the number of free vertices before the last turn
usually plays an important role. We need the following number theory facts.

\begin{fact}\label{div}
Let $r<2$ be a rational number and $c>0$ be an integer. 
\begin{itemize}
\item[(i)]
There are infinitely many natural numbers $n$ such that 
$q\mid \binom n2$ for some $q$ with $cn^{r}<q< 2cn^{r}$.
\item[(ii)]
There are infinitely many natural numbers $n$ such that 
$q\mid \binom n2-1$ for some $q$ with $cn^{r}< q< 4cn^{r}$.
\end{itemize}
\end{fact}

\begin{proof}
Let us fix natural numbers $c,r_1,r_2$ and let $r=r_1/r_2<2$. 

In order to prove (i), for every integer $k\ge 2$ we put $n-1=(4c)^{kr_2}$ and 
define $q=2c(n-1)^r=2c(4c)^{kr_1}$ if $r<1$, or $q=2c(n-1)^{r-1}n=2c(4c)^{k(r_1-r_2)}n$ if $r\ge 1$. 
Then we obtain $cn^r<q<2cn^r$ and $q\mid\binom n2$. Thus we have
infinitely many $n$ satisfying (i).

To show (ii), for every integer $k\ge 2$ we put $n-2=(4c)^{kr_2}$ and 
define $q=2c(n-2)^r$ if $r<1$, or $q=2c(n-2)^{r-1}(n+1)$ if $r\ge 1$. 
By simple calculations one can verify that $cn^r<q<4cn^r$, and
$q\mid\binom n2-1$ since $\binom n2-1=(n+1)(n-2)/2\,$. This proves (ii).
\end{proof}

\begin{fact}\label{log}
Let $\delta\in(0,1)$ and $N,q>0$ be integers such that $N^\delta< q<\delta N/(2\ln N)$. 
Then,  if $N$ is sufficiently large, there exists 
an integer $k$ such that $q\le k\le 2\delta^{-1}q\ln q$ and the remainder of the division of $N$ by $k$
is greater than $q$.  
\end{fact}

\begin{proof}
Suppose that for every integer $k$ from the interval $[q,2\delta^{-1}q\ln q]$ the remainder of the division
of $N$ by $k$ is at most $q$. In the interval $[q,2\delta^{-1}q\ln q]$ there are more than $(q+1)/\delta$ primes 
(for big $N$), so more than $1/\delta$ of them are equivalent modulo $N$. 
It means that for some $r\le q$, $t>1/\delta$ and some primes $p_1,\ldots,p_t\ge q$,
we have $p_i\mid N-r$ for $i=1,\ldots,t$.
Hence $p_1\cdot\ldots\cdot p_t\mid N-r$ and we conclude that
$N>q^t>q^{1/\delta}$. Therefore, if $q>N^\delta$, we come to a contradiction.   
\end{proof}


\subsection{Proof of Theorem \ref{smalla}}

Let us begin by a trivial observation. If Avoider 
can avoid building a subgraph of $G$ in $K_n$, then he avoids building the graph $G$ as well.
Therefore, without loss of generality, while proving (\ref{fplus}) we can assume that the maximum $m'(G)$ 
is attained by $G$. 
Furthermore, (\ref{fminln})--(\ref{defence}) obviously hold if $G$ is a matching (with at least two edges) 
so while proving (\ref{fminln})--(\ref{defence}) we will assume that $G$ contains two adjacent edges, and  
the maximum $m(G)$ is attained by $G$.   

In order to prove (\ref{fplus}), observe that there are $O(n^{v(G)})$ copies of $G$ in $K_n$. 
Hence there exists a constant $c>0$ (which depends on $G$)
such that if $f=\lceil cn^{1/m'(G)}\rceil=\lceil cn^{v(G)/(e(G)-1)}\rceil$, then
$$\sum_{A\in E(\FGn)}\Big(\frac{f}{e(G)}+1\Big)^{-e(G)+1}<1.$$
We have $\rank(\FGn)=e(G)$ so Avoider has a winning
strategy for both $\AF(\FGn,1,f)$ and $\AFm(\FGn,1,f)$, based on the first part of Theorem \ref{awf}. 
This proves that $\fm_{\FGn}=O(n^{1/m'(G)})$ and $\fu_{\FGn}=O(n^{1/m'(G)})$.

To prove (\ref{fminln}), similarly observe that there is a constant $c\ge 1$
such that if $f=\lceil cn^{1/m(G)}\rceil=\lceil cn^{v(G)/e(G)}\rceil$, then 
$$\sum_{A\in E(\FGn)}\Big(\frac{f}{e(G)}+1\Big)^{-e(G)}<1.$$

Note that $m(G)>1/2$ for $G$ containing two adjacent edges, and the assumptions of Fact \ref{log} 
are satisfied for $\delta=1/(2m(G))$, $N=\binom n2$ and $q=f$, provided $n$ is sufficiently large. 
Thus there exists an integer $f'$ such that $f\le f'+1\le 4m(G)f\ln f$ and the remainder of 
a division of $\binom n2$ by $f'+1$ is greater than $f$. Hence, in the course of the game $\AF(\FGn,a,f')$,
before every move of Avoider there are at least $f+1$ free vertices of the hypergraph.
By the second part of Theorem \ref{awf},  we conclude that Avoider will never occupy any edge 
entirely. It means that $\fl_{\FGn}<f'=O(n^{1/m(G)}\ln n)$. 

The proof of part (\ref{fmin}) is similar to the previous one. We find an integer constant $c>0$ such that
if $f\ge cn^{1/m(G)}-1$, then 
$\sum_{A\in E(\FGn)}\Big(\frac{f}{e(G)}+1\Big)^{-e(G)}<1$. Based on the first part of 
Fact \ref{div}, we can argue that there are infinitely many natural numbers $n$ such that for some $f$
with $cn^{1/m(G)}< f+1< 2cn^{1/m(G)}$ we have $f+1\mid \binom n2$.
For every such $n$ and $f$, in view of the second part of Theorem \ref{awf}, 
Avoider wins $\AF(\FGn,1,f)$. Therefore $\fl_{\FGn}< 2cn^{1/m(G)}$. 

Finally, part (\ref{defence}) is an immediate consequence of the second part of Theorem \ref{awf}.     



\subsection{Proof of Theorem \ref{smallf}} 

To prove part (i), observe that for some constant $c$ and every sufficiently large $n$,
if $f<c n^{1/2}$, then the inequality in Theorem \ref{bcc} holds with $a=1$
and $\F=\F_{K_3,n}$. This is why Forcer in $\AF(\F_{K_3,n},1,f)$ has a winning strategy. 

Now we will prove part (ii). Let $G$ be a graph with at least two edges. 
The key ingredient of the proof
is a theorem by Saxton and Thomason \cite{container1} about $H$-free hypergraphs, 
which is a consequence of their much more general result on the so-called hypergraph containers. 
We should mention that another version of the hypergraph container theorem was independently proved by 
Balogh, Morris and Samotij \cite{container2}.
Below we present the theorem by Saxton and Thomason in a simplified form, for $G$-free graphs.  

\begin{theorem}[\cite{container1}, Thm 1.3]\label{cont}
Let $G$ be a graph with $e(G)\ge 2$ and let $\eps>0$. For some constant $c>0$ 
and sufficiently large $n$ there exists a collection $\mathcal{C}$ of subgraphs of $K_n$ such that
\begin{enumerate}[(a)]
\item 
for every $G$-free subgraph $F$ of $K_n$ there exists $C\in \mathcal{C}$ with $F\subs C$,
\item 
$e(C)\le (1-1/(\chi(G)-1)+\eps)\binom n2$ for every $C\in \mathcal{C}$,
\item
$\ln|\mathcal{C}|\le c n^{2-1/m_2(G)}\ln n$. 
\end{enumerate}
\end{theorem}

Let a family $\mathcal{C}$ and a constant $c>0$ be as described in the above 
theorem for \mbox{$\eps<1/(\chi(G)-1)$}. 
Observe that if the end position of  $\AF(\FGn,1,f)$ or $\AFm(\FGn,1,f)$ is a win for Avoider, 
then Avoider's graph is contained in some $C\in\mathcal{C}$. Equivalently, Forcer has selected all edges
in the set $E(K_n)\setm E(C)$. Hence, Forcer has a winning strategy for $\AF(\FGn,1,f)$ (or $\AFm(\FGn,1,f)$)
if he can win playing Avoider's role in $\AF(\F,f,1)$ (or $\AFm(\F,f,1)$), where $V(\F)=E(K_n)$ and
$E(\F)=\{E(K_n)\setm E(C)\colon C\in\mathcal{C}\}$. 

Let $\delta>0$ be a constant such that $(1/(\chi(G)-1)-\eps)\binom n2>\delta n^2$. 
By Theorem \ref{cont} we have 
$$\ln|E(\F)|\le c n^{2-1/m_2(G)}\ln n\quad\text{and}\quad 
|D|\ge \Big(\frac{1}{\chi(G)-1}-\eps\Big)\binom n2>\delta n^2$$ 
for every $D\in E(\F)$. Thus
\beqa
\sum_{D\in E(\F)}\Big(\frac 1f +1\Big)^{-|D|+f}<
|E(\F)|\Big(\frac 1f +1\Big)^{-\delta n^2+f}<
e^{c n^{2-1/m_2(G)}\ln n}\cdot 2^{-\delta n^2/f+1},
\eeqa
provided that $\delta n^2>f$. Calculations show that the right-hand side of the above
inequality is less than 1 if $f<c'n^{1/m_2(G)}/\ln n$, where $c'>0$ is some constant and $n$
is sufficiently large. 

Therefore, for $f<c'n^{1/m_2(G)}/\ln n$, the assumption of the first part of Theorem \ref{ae07}
is satisfied (with $a=f$), so Avoider in $\AF(\F,f,1)$ and $\AFm(\F,f,1)$ has a winning strategy.
It means that Forcer has a winning strategy for $\AF(\FGn,1,f)$ and $\AFm(\FGn,1,f)$, which 
completes the proof of Theorem \ref{smallf}.

%%%%%%%%%%%%% Ack %%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Acknowledgements}
I would like to thank the referees for 
their very thorough comments, which greatly improved
the paper.

%%%%%%%%%%%%%  bibliography  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{10}

\bibitem{container2}
J.~Balogh, R.~Morris, and W.~Samotij.
\newblock Independent sets in hypergraphs.
\newblock preprint, \arxiv{1204.6530}. 

\bibitem{beckwf}
J.~Beck.
\newblock Remarks on positional games.~I.
\newblock {\em Acta Math.~Acad.~Sci.~Hungar.}, 40:65--71, 1982.

\bibitem{TTT}
J.~Beck.
\newblock {\em Combinatorial games: Tic-tac-toe theory}. 
\newblock Encyclopedia of Mathematics and its Applications, no. 114, 
Cambridge University Press, Cambridge, 2008. xiv+732~pp.

\bibitem{mbtl}
\newblock M.~Bednarska and T.~{\L}uczak.
\newblock Biased positional games for which random strategies are nearly optimal.
\newblock {\em Combinatorica}, 20:477--488, 2000.

\bibitem{CE}
\newblock V.~Chv\'atal and P.~Erd\H os.
\newblock Biased positional games.
\newblock {\em Annals of Discrete Math.}, 2:221--228, 1978.

\bibitem{aebox}
\newblock A.~Ferber, M.~Krivelevich, and A.~Naor.
\newblock Avoider-Enforcer games played on edge disjoint hypergraphs.
\newblock {\em Dicrete Math.}, 313:2932--2941, 2013.

\bibitem{GSz}
\newblock H.~Gebauer and T.~Szab\'o. 
\newblock Asymptotic random graph intuition for the biased connectivity game. 
\newblock {\em Random Struct.~Algor.}, 35:431--443, 2009.

\bibitem{planar}
\newblock D.~Hefetz, M.~Krivelevich, M.~Stojakovi\'c, and T.~Szab\'o.
\newblock Planarity, colorability and minor games.
\newblock {\em SIAM Journal on Discrete Mathematics}, 22:194--212, 2008.

\bibitem{ae09}
\newblock D.~Hefetz, M.~Krivelevich, M.~Stojakovi\'c, and T.~Szab\'o.
\newblock Avoider-Enforcer: The rules of the game.
\newblock {\em J.~Combinatorial Theory Ser.~A}, 117:152--163, 2010.

\bibitem{ae07}
\newblock D.~Hefetz, M.~Krivelevich, and T.~Szab\'o. 
\newblock Avoider-Enforcer games.
\newblock {\em J.~Combinatorial Theory Ser.~A}, 114:840--853, 2007.

\bibitem{kriv}
\newblock M.~Krivelevich. 
\newblock The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n.
\newblock {\em Journal of the American Mathematical Society}, 24:125--131, 2011.

\bibitem{cover}
\newblock M.~Krivelevich and T.~Szab\'o.
\newblock Biased positional games and small hypergraphs with large covers. 
\newblock {\em Electronic Journal of Combinatorics}, 15:publ.~R70, 2008. 

\bibitem{container1}
\newblock D.~Saxton and A.~Thomason. 
\newblock Hypergraph containers.
\newblock preprint, \arxiv{1204.6595}. 

 
\end{thebibliography}

\end{document}









