% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P9}{20(2)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
%\usepackage{amsthm,amsmath,amssymb}
\usepackage{amsmath,amssymb,latexsym,color,epsfig,a4, enumerate}
\usepackage{bbm}
\usepackage{a4wide}


% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\newcommand{\I}[1]{{\mathbb #1}}
\newcommand{\nlln}{\mbox{$n \frac{ \log \log n}{\log n}$}}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\setall}[2]{\{#1:\;#2\}}
\newcommand{\stack}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\lfrac}[2]{\left(\frac{#1}{#2}\right)}


\DeclareFontFamily{OT1}{pzc}{}
\DeclareFontShape{OT1}{pzc}{m}{it}{<-> s * [1.10] pzcmi7t}{}
\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}

\def\({\left(}
\def\){\right)}
\def\eps{\varepsilon}
\def\cB{{\cal B}}
\def\LARG{\mbox{LARGE}}
\def\SMALL{\mbox{SMALL}}
\def\cX{{\cal X}}
\def\cD{{\cal D}}
\def\cE{{\cal E}}
\def\cA{{\cal A}}
\def\cF{{\cal F}}
\def\cT{{\cal T}}
\def\qwert{2^{\tilde O(1/\ep^2)}}
\def\cond{{\rm Cond}}
\def\hu{\hat{u}}
\def\bC{{\bf C}}
\def\bT{{\bf T}}
\def\hDD{\hat{{\bf D}}}
\def\bM{{\bf M}}
\def\DD{{\bf D}}
\def\norm{\hbox{Norm}}
\def\half{{\textstyle{1\over2}}}
\def\bR{{\bf R}}
\def\recip#1{{1\over#1}}
\def\dij{\hat{d}_{i,j}}
\def\vol{{\rm Vol}}
\def\for{\hbox{  for  }}
\def\hT{\hat{T}}
\def\bA{{\bf A}}
\def\bW{{\bf W}}
\def\bhW{\hat{\bW}}
\def\hc{\hat{c}}
\def\ep{\epsilon}
\def\ind{{\rm ind}}
\def\hw{\hat{w}}
\def\bs{\bar{\sigma}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\cF{{\cal F}}
\def\cK{{\cal K}}
\def\F{\Phi}
\def\E{{\bf E}}
\def\cN{{\cal N}}
\def\Ex{{\bf E}}
\def\cS{{\cal S}}
\def\cP{{\cal P}}
\def\cQ{{\cal Q}}
\def\ind{{\rm ind}}
\def\bn{\bar{n}}
\def\bv{\bar{\n}}
\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\D{\Delta}
\def\e{\epsilon}
\def\f{\phi}
\def\g{\gamma}
\def\G{\Gamma}
\def\k{\kappa}
\def\la{\lambda}
\def\K{\Kappa}
\def\z{\zeta}
\def\th{\theta}
\def\TH{\Theta}
\def\m{\mu}
\def\n{\nu}
\def\p{\pi}
\def\P{\Pi}
\def\r{\rho}
\def\R{\Rho}
\def\s{\sigma}
\def\S{\Sigma}
\def\t{\tau}
\def\om{\omega}
\def\OM{\Omega}
\def\bigmid{\rule[-3.5mm]{0.1mm}{9mm}}
\def\N{{\cal N}}
\def\Pr{\mbox{{\bf Pr}}}
\def\CG{{\cal G}}
\def\CA{{\cal A}}
\def\whps{{\bf whp }}
\def\whp{{\bf whp}}
\def\Prob{\ensuremath{{\mathbb P}}}
\def\he{\hat{\e}}
\def\BD{{\bf D}}
\def\bW{{\bf W}}
\def\bB{{\bf B}}
\def\hr{\hat{r}}
\def\hR{\hat{R}}
\def\cf{{\cal F}}



\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{definition}[theorem]{Definition}

\numberwithin{equation}{section}

\newcommand{\brac}[1]{\left( #1\right)}
\newcommand{\bfrac}[2]{\brac{\frac{#1}{#2}}}
\newcommand{\ratio}[2]{\mbox{${#1\over #2}$}}
\newcommand{\bbD}[1]{\bar{{\bf D}}^{(#1)}}
\newcommand{\gap}[1]{\mbox{\hspace{#1 in}}}
\newcommand{\bD}[1]{{\bf D}^{(#1)}}
\newcommand{\hbD}[1]{\hat{{\bf D}}^{(#1)}}
\newcommand{\bTT}[1]{{\bf T}^{(#1)}}
\newcommand{\limninf}{\mbox{$\lim_{n \rightarrow \infty}$}}
\newcommand{\proofstart}{{\bf Proof\hspace{2em}}}
\newcommand{\tset}{\mbox{$\cal T$}}
\newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}}
\newcommand{\bfm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\reals}{\ensuremath{\mathbbm{R}}}
\newcommand{\expect}{\mbox{\bf E}}
\newcommand{\Exp}{\ensuremath{\mathbbm{E}}}
\newcommand{\card}[1]{\mbox{$|#1|$}}
\newcommand{\scaps}[1]{\mbox{\sc #1}}
\newcommand{\rdup}[1]{{\mbox{$ \lceil #1 \rceil $}}}
\newcommand{\rdown}[1]{{\mbox{$ \lfloor #1 \rfloor $}}}
\newcommand{\mnote}[1]{\marginpar{\footnotesize\raggedright#1}}
\newcommand{\rt}{\right}
\newcommand{\lt}{\left}
\def\cH{{\cal H}}
\def\cG{{\cal G}}
\def\cM{{\cal M}}
\newcommand{\re}{\mbox{\rm e}}
\newcommand{\setm}{\setminus}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\gnp}{\ensuremath{\mathcal{G}_{n,p}}}
\newcommand{\nat}{\ensuremath{\mathbbm{N}}}
\newcommand{\Deg}{\ensuremath{\mathpzc{Deg}}}
\newcommand{\Bin}{\ensuremath{\mathrm{Bin}}}

%\newenvironment{proof}{\noindent{\bf Proof\,}}{\hfill$\Box$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf The biased odd cycle game}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 


\def\mark#1{$^{#1}$}


\author{Asaf Ferber\mark{1}
\and
Roman Glebov\mark{2}
\and
Michael Krivelevich\mark{1} \mark{3}
\and
Hong Liu\mark{4}
\and
Cory Palmer\mark{4} \mark{5}
\and
Tom\'a\v s Valla\mark{6}
\and
M\'at\'e Vizer\mark{7}
}


% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Oct 19, 2012}{Apr 8, 2013}{Apr 17, 2013}\\
}%\small Mathematics Subject Classifications: 

\begin{document}

\footnotetext[1]{
School of Mathematical Sciences,
Raymond and Beverly Sackler Faculty of Exact Sciences,
Tel Aviv University,
Tel Aviv, 69978, Israel.
{\tt \{ferberas,krivelev\}@post.tau.ac.il}}
\footnotetext[2]{Institut f\"{u}r Mathematik,
Freie Universit\"at Berlin,
Arnimallee 3-5, D-14195 Berlin, Germany,
{\tt glebov@math.fu-berlin.de}.
Research supported by DFG within the research training group ``Methods for Discrete Structures''.}
\footnotetext[3]{Research supported in part by USA-Israel BSF Grant 2010115 and by grant 1063/08 from the Israel Science Foundation.}
\footnotetext[4]{Department of Mathematical Sciences,
\small University of Illinois at Urbana-Champaign,
\small Urbana, Illinois 61801 USA.
{\tt \{hliu36,ctpalmer\}@illinois.edu}}
\footnotetext[5]{Research supported in part by OTKA Grant NK78439.}
\footnotetext[6]{Czech Technical University in Prague,
Faculty of Information Technology,
Th\'akurova 9, 160~00, Prague~6, Czech Republic,
{\tt tomas.valla@fit.cvut.cz}.
Supported by the Centre of Excellence -- Inst.\ for Theor.\ Comp.\ Sci., Prague (project P202/12/G061 of GA~\v{C}R).}
\footnotetext[7]{Alfr\'ed R\'enyi Institute of Mathematics,
P.O.B. 127, Budapest H-1364, Hungary.
{\tt vizer.mate@renyi.mta.hu}}



\maketitle


\begin{abstract}
In this paper we consider biased Maker-Breaker games played on the
edge set of a given graph $G$. We prove that for every $\delta>0$
and large enough $n$, there exists a constant $k$ for which if
$\delta(G)\geq \delta n$  and $\chi(G)\geq k$, then Maker can build
an odd cycle in the $(1:b)$ game for $b=O\left(\frac{n}{\log^2
n}\right)$. We also consider the analogous game where Maker and
Breaker claim vertices instead of edges. This is a special case of
the following well known and notoriously difficult problem due to
Duffus, {\L}uczak and R\"{o}dl: is it true that for any positive
constants $t$ and $b$, there exists an integer $k$ such that for
every graph $G$, if $\chi(G)\geq k$, then Maker can build a graph
which is not $t$-colorable, in the $(1:b)$ Maker-Breaker game played
on the vertices of $G$?

  % keywords are optional
  \bigskip\noindent \textbf{Keywords: Maker-Breaker games, DLR conjecture, odd cycle game} 
\end{abstract}

\section{Introduction}
Let $X$ be a finite set and let $\mathcal{F}\subseteq 2^X$ be the
family of subsets of $X$. Let $a$ and $b$ be positive integers. In an
$(a:b)$ \emph{Maker-Breaker} game $(X,\mathcal{F})$, two players,
\emph{Maker} and \emph{Breaker}, take turns claiming previously
unclaimed elements of $X$. The game ends when every element of $X$
has been claimed by a player. Maker claims exactly $a$ board
elements per turn and Breaker claims exactly $b$ board elements per
turn. Unless explicitly stated otherwise, we will assume that Maker
is the first player. Maker wins the game if he is able to fully
claim some element of $\mathcal{F}$; otherwise Breaker wins. The set
$X$ is often referred to as the \emph{board} of the game and the
members of $\mathcal{F}$ are referred to as the \emph{winning sets}.

It is natural to play a Maker-Breaker game on the edge set of a
given graph $G$. In this case the board is $X=E(G)$ and the winning
sets are all the edge sets of subgraphs $H\subseteq G$ which possess
a graph property $\mathcal P$ of special interest. For example, in
the \emph{connectivity} game, the winning sets are all the edge sets
of subgraphs $H\subseteq G$ which contain a spanning tree of $G$. Given a
positive integer $k$, in the \emph{non-$k$-colorability} game,
$\mathcal {NC}_k(G)$, the winning sets are all the edge sets of
subgraphs $H\subseteq G$ which are not $k$-colorable. Since a graph
$G$ is not $2$-colorable if and only if it contains an odd cycle, we
refer to $\mathcal {NC}_2(G)$ as the \emph{odd cycle game}.

The following question is due to Duffus, {\L}uczak and R\"{o}dl
\cite{DLR}:

\begin{question}\label{conj1}
Is it true that for any positive integers $k$ and $b$, there exists
an integer $r=r(k,b)$ such that Maker has a winning strategy for the
$(1:b)$ game $\mathcal {NC}_k(G)$, played on any graph $G$ such that
$\chi(G)\ge r$?
\end{question}

Not much is known about Conjecture~\ref{conj1}. By a \emph{strategy
stealing} argument the answer for Question~\ref{conj1} is ``yes" for
$b=1$ and any $k$ (for more details the reader is referred to
\cite{AHK}). Note that strategy stealing is a purely existential
argument; we do not know any explicit strategy for Maker to win the
game with these parameters.

For any $b \geq 2$ and any $k \geq 2$ Question~\ref{conj1} is open.
Two partial results were obtained in~\cite{AHK}. The first result
shows that $\chi(G) = \Omega(\log (|V(G)|))$ suffices to ensure
Maker's win. The second result shows that if $\chi(G) \geq r$ holds
in some robust way, then Maker has a winning strategy for the game
on $G$. However, no bounds on $\chi(G)$ which do not depend on
$|V(G)|$ are known.

In \cite{DLR}, Duffus, {\L}uczak and R\"{o}dl ask the following
question:

\begin{question} \label{conj2}
Is it true that there exists an integer $k$ such that for all graphs
$G$ with $\chi(G)\geq k$, Maker has a strategy to claim an odd cycle
in the game where Maker claims one vertex each turn and Breaker
claims two?
\end{question}

In this paper we partially answer Questions~\ref{conj1} and
\ref{conj2} for the case where Maker's goal is to build an odd cycle
(a non-2-chromatic graph), playing on a graph $G$ with high minimum
degree. Our main results are the following:

\begin{theorem}\label{main1}
For every $0<\delta<1$, there exists an integer $n_0=n_0(\delta)$
for which the following holds. Suppose that:

\begin{enumerate}

\item $G$ is a graph with $|V(G)|=n\geq n_0$, and

\item $\delta(G)\ge \delta n$, and

\item $\chi(G)>32/\delta$.
\end{enumerate}

Then for every $b\le \frac{\delta^2 n}{6400(\log_2 n)^2}$, Maker has
a winning strategy in the $(1:b)$ game $\mathcal {NC}_2(G)$.


\end{theorem}

The next result shows that the bound on the chromatic number of $G$
can be lowered to the optimal $\chi(G)\ge 3$ if $G$ has high
connectivity instead of high minimum degree. In particular, $O(\log
n)$-connectivity suffices in a game with a constant Breaker's bias.
(This is because every $k$-chromatic graph $G$ contains a
$k$-color-critical subgraph $G_0\subset G$, and every
$k$-color-critical graph is $(k-1)$-edge-connected.
Thus Theorem~\ref{main3} can be applied to $G_0$.)
This reproves Theorem 1.6 of \cite{AHK} for the odd cycle game.
\begin{theorem}\label{main3}
For every positive integer $b$, there exists an integer $n_0=n_0(b)$
for which the following holds. Suppose that:

\begin{enumerate} [$(i)$]

\item $G$ is a graph with $|V(G)|=n\geq n_0$, and

\item $G$ is $\left(10^4\log_2 n\cdot b^2(\log_2
b)^2\right)$-edge-connected, and

\item $\chi(G)\ge 3$.
\end{enumerate}
Then Maker has a winning strategy in the $(1:b)$ game $\mathcal {NC}_2(G)$.
\end{theorem}

The following theorem is the ``vertex version" of Theorem!\ref{main1},
where instead of claiming edges, Maker and Breaker
claim vertices of the graph $G$.

\begin{theorem}\label{main2}
For every $0<\delta<1$ and for every positive integer $b$, there
exists an integer $n_0=n_0(\delta,b)$ for which the following holds.
Suppose that:

\begin{enumerate} [$(i)$]

\item $G$ is a graph with $|V(G)|=n\geq n_0$, and

\item $\delta(G)\geq \delta n$, and

\item $\chi(G)>2(b+1)/\delta$.
\end{enumerate}

Then Maker has a winning strategy in the $(1:b)$ odd-cycle game
played on $V(G)$. Furthermore, the odd cycle that Maker builds is of
constant size (depending only on $\delta$).

\end{theorem}

\subsection{Notation}

The notation in this paper is standard and follows that of \cite{D}.
In particular we use the following. Given a graph $G$, denote by
$V(G)$ and $E(G)$ its sets of vertices and edges, respectively. For
two subsets $A,B\subseteq V(G)$, let $E_G(A,B)$ be the set of edges
in $E(G)$ with one endpoint in $A$ and one endpoint in $B$. For a
vertex $v\in V(G)$ and a subset $U\subseteq V(G)$, denote by
$d_G(v,U)$ the number of edges from $v$ to $U$. Denote by $G[U]$ the
induced subgraph on $U$ and set $U^c=V(G)\setminus U$. We also
denote $N_G(U)=\{v\in V(G):\exists u\in U. vu\in E(G)\}$.

\bigskip
\bigskip
The remainder of the paper is organized as follows. In
Section~\ref{sec:aux}, we will list some tools to be used in our
arguments. Theorems~\ref{main1} and \ref{main3} are proved in
Section~\ref{main-pf}. Theorem~\ref{main2} is proved in
Section~\ref{main2-pf}.


\section{Preliminaries}\label{sec:aux}

The following lemma shows that if $G$ is a graph with high minimum
degree and high chromatic number, then it contains a subgraph which
is highly connected and is only one edge far from being bipartite.
This is a key ingredient in the proof of Theorem~\ref{main1}.

\begin{lemma} \label{key1}
Let $0<\delta<1$ and let $n$ be a sufficiently large integer.
Suppose that $G$ is a graph on $n$ vertices with $\delta(G)\geq
\delta n$ and $\chi(G)>32/\delta$. Then there exist two disjoint
subsets $A,B\subseteq V(G)$ such that the bipartite graph $H=(A\cup
B,E_G(A,B))$ is $\delta^2 n/64$-connected and $E_G(A)\neq
\emptyset$.
\end{lemma}

To prove Lemma~\ref{key1} we use the following lemma due to Bohman,
Frieze, Krivelevich and Martin \cite{BFKM} which enables us to
partition a dense graph into a few vertex disjoint subgraphs which
are highly connected:

\begin{lemma}[Lemma 1 in \cite{BFKM}] \label{lem1}
Let $H$ be a graph on $n$ vertices with minimum degree $k>0$. Then
there exists a partition $V(H)=V_1\cup\ldots\cup V_t$ such that for
every $1\le i\le t$ the set $V_i$ has at least $k/8$ vertices and
the induced subgraph $H[V_i]$ is $k^2/(16n)$-vertex-connected.
\end{lemma}

For the convenience of the reader we include the proof of Lemma~\ref{lem1}.

\textbf{Proof.} Recall a classical result of Mader (see~\cite{D}) stating that
every graph of average degree at least $k$ has a $k/4$-vertex-connected subgraph.

Let $(C_1,\ldots,C_t)$ be a family of disjoint subsets of $V(H)$ with
the property that each induced subgraph $H[C_i]$ is $k/8$-connected
and that, among all such families of subsets, the set of vertices
$$C:=\bigcup_{i=1}^t C_i$$
is maximal. According to Mader's Theorem, $t>0$. Also, $|C_i|\ge k/8$ for all $i$ and thus $t\le 8n/k$.

Let now $(V_1,\ldots,V_t)$ be a family of disjoint subsets of $V(H)$
such that $C_i\subseteq V_i$, the induced subgraph $H[V_i]$ is
$k^2/(16n)$-connected for all $1\le i\le t$ and that among all such
families the set of vertices
$$U:=\bigcup_{i=1}^t V_i$$
is maximal. We claim that $U=V(H)$. Assume to the contrary that
there exists a vertex $v\in U^c$. If $|N_H(v)\cap V_i|\ge k^2/(16n)$
for some $i$, then adding $v$ to $V_i$ can be easily seen to keep
$H[V_i]$ $k^2/(16n)$-connected, contradicting the maximality of $U$.
Thus $v$ has less than $k^2/(16n)$ neighbors in each of the $t\le
8n/k$ sets $V_i$, and therefore $d(v,U^c)>k-(8n/k)(k^2/(16n))=k/2$.
We conclude that the minimum degree of the induced subgraph $H[U^c]$
is at least $k/2$. Applying Mader's Theorem, this time to $H[U^c]$,
unveils a $k/8$-connected subgraph disjoint from $C$, a
contradiction of the choice of $(C_1,\ldots,C_t)$. Hence the family
$(V_1,\ldots,V_t)$ indeed covers all the vertices of $H$ and thus forms
a required partition. {\hfill $\Box$ \medskip}

\textbf{Proof of Lemma~\ref{key1}.} Let $V(G)=X_1\cup X_2$ be a
partition such that for every $X_i\in \{X_1,X_2\}$ and for every
$v\in X_i$, $d(v,X_{3-i})\ge d(v)/2$ (easily obtained by taking a
partition which maximizes $|E(X_1,X_2)|$). Consider the bipartite
subgraph $G'\subseteq G$ obtained by removing all the edges inside
$X_1$ and $X_2$; clearly $\delta(G')\ge \delta(G)/2\ge \delta n/2$.
Now, applying Lemma~\ref{lem1} to $G'$, we get a partition
$V(G')=V_1\cup\ldots\cup V_t$ with
$$|V_i|\ge \left(\frac{\delta n}{2}\right)/8=\frac{\delta n}{16},$$
hence
$$t\le \frac{n}{\delta n/16}=\frac{16}{\delta},$$
and the induced subgraph $G'[V_i]$ is $\left(\delta
n/2\right)^2/(16n)=\delta^2 n/64$-connected, for every
$1\le i\le t$. Since $\chi(G)>32/\delta\ge 2t$, we conclude that there
exists $1\leq i\leq t$ for which $G[V_i]$ is not $2$-colorable, since otherwise
giving distinct sets of $2$ colors to each $G[V_i]$ yields a proper
$2t$-coloring, a contradiction.
Recall that $G'[V_i]$ is bipartite, so we can denote its parts by $A$
and $B$ in such a way that $E_G(A)\neq \emptyset$. This completes
the proof. {\hfill $\Box$ \medskip}





The following theorem of Alon, Hefetz and Krivelevich \cite{AHK} enables Maker to win the
$(1:b)$ connectivity game played on the edge set of some given graph
$G$, provided that $G$ is a highly edge-connected graph. It will
be useful in the proof of Theorems~\ref{main1} and~\ref{main3}.

\begin{theorem}\label{edge-conn}
Let $G=(V,E)$ be a graph on $n$ vertices and let $b\ge 2$ and
$k=k(n)\ge \log_2 n$ be integers. If $G$ is $(100kb\log_2
b)$-edge-connected, then in the $(1:b)$ game played on $E(G)$, Maker
(as a first or second player) has a strategy for building a
$k$-edge-connected spanning subgraph of $G$. In particular, Maker
can build a connected spanning subgraph of $G$.
\end{theorem}

For the proof of Theorem~\ref{main2} we need the following lemmas:

\begin{lemma} \label{key2}
Let $0<\delta<1$, $b$ be a positive
integer and $n$ be a sufficiently large integer. Suppose that
$G$ is a graph on $n$ vertices with $\delta(G)\geq \delta n$ and
$\chi(G)>2(b+1)/\delta$. Then there exist two disjoint subsets
$A,B\subseteq V(G)$ such that the bipartite graph $H=(A\cup
B,E_G(A,B))$ satisfies

\begin{enumerate} [$(i)$]
\item $|E_H(U,U^c)|= \Omega(n^{3/2})$ for every $U\subseteq A\cup B$
of size $\delta n/2\leq |U|\leq |A\cup B|-\delta n/2$;
\item $\delta(H)\ge\delta^2 n/2$;
\item all but $o(n)$ vertices in $H$ have degree at least $(1-o(1))\delta
n/2$; and
\item $\chi(G[A])> b+1$.
\end{enumerate}
\end{lemma}

In a similar way as the proof of Lemma~\ref{key1}, Lemma~\ref{key2}
is an immediate consequence of the following:

\begin{lemma}\label{keylemma}
Let $0<\delta< 1 $ and let $n$ be a sufficiently large integer. Let
$G$ be a graph on $n$ vertices with $\delta(G)\geq \delta n$. Then
there exists a partition $V(G)=V_1\cup\ldots\cup V_t$ which
satisfies:
\begin{enumerate}[$(i)$]
\item $|V_i|\geq \delta n(1-o(1))$ for every $1\leq i\leq t$;
\item $\delta(G[V_i])\ge \delta^2 n$ for every $1\leq i \leq t$;
\item all but $o(n)$ vertices in $G[V_i]$ have degree at least $\delta n(1-o(1))$ for every $1\leq i\leq
t$; and
\item $|E_G(A,B)|= \Omega(n^{3/2})$ for every partition $V_i=A\cup B$ for which $\delta n \leq |A|\leq |V_i|-\delta
n$ and for every $1\leq i\leq t$.
\end{enumerate}

\end{lemma}

\textbf{Proof.} We construct the partition in the following way:
initially, let $V_1:=V(G)$ and $U:=\emptyset$. Assume we have a
partition $V(G)=V_1\cup\cdots \cup V_k$ and a current set $U$
(notice that $U$ will be modified during the iterations). If there
exists an index $1\leq i\leq k$ and a partition $V_i=A\cup B$ for
which $|A|,|B| \ge \delta n$ and $e(A,B)< n^{3/2} $,
then we break $V_i$ into $A\cup B$ and define a new partition
$V_1\cup\cdots \cup V_{i-1}\cup A \cup B \cup V_{i+1}\cup \cdots
V_k$. Notice that there are at most $n^{3/4}$ vertices $v$ in $X\in
\{A, B\}$ such that $d(v,X)< d(v,V_i)-n^{3/4}$. Otherwise, we get
that $e(A,B)\geq n^{3/2}$, a contradiction. We add these at most
$2n^{3/4}$ vertices to $U$. Since none of the $V_i$'s is ever
smaller than $\delta n$, we get that this procedure stops after at
most $1/\delta$ iterations. Let $V(G)=V_1\cup \ldots \cup V_t$ be
the final partition and let $U$ be the corresponding set of vertices
with (possibly) small degrees inside their parts. Notice that for
every $i\in [t]$ and every $v\in V_i\setminus U$, we have
$d(v,V_i)\geq \delta n - t n^{3/4}=\delta n(1-o(1))$. By the
previous argument, in every iteration we increase $|U|$ by at most
$2n^{3/4}$, hence $|U|\leq 2n^{3/4}/\delta$. Now for every vertex
$v\in U$, choose a part $V_j$, $1\le j\le t$, for which
$d(v,V_j)\geq \delta^2 n$ and move $v$ to $V_j$ (recall that
$d_G(v)\geq \delta n$ and that $t\leq 1/\delta$). We get a final
partition which satisfies properties $(i)-(iv)$. {\hfill $\Box$
\medskip}

For the next lemma, we need to define an auxiliary game. Given a
graph $H$ and a subset $M \subseteq V(H)$, consider the
Maker-Breaker game $\mathcal G(H,M)$ played on $V(H)$, in which the
winning sets are all subsets $T\subseteq V(H)$, such that $H[T\cup
M]$ is a connected subgraph of $H$ or it contains a triangle.

\begin{lemma}\label{key3}
Let $H=(A\cup B,E_G(A,B))$ be a graph satisfying $(i)-(iii)$ of
Lemma~\ref{key2}. Let $M\subseteq V(H)$ be any subset that can be
partitioned to $M=D\cup R$, where $D$ is any dominating set of size
$O(\log n)$, and such that for each vertex $v\in D$ there exists
$u\in R$ with degree at least $(1-o(1))\delta n/2$ such that $uv\in
E(H)$. Then, for any constant $b$, Maker can win the $(1:b)$ game
$\mathcal G(H,M)$ within $O(\log n)$ moves.
\end{lemma}

\textbf{Proof.} First, notice that since $|D|=O(\log n)$ we conclude
that there are at most $O(\log n)$ components in $H[M]$. Now, in
order to complete the proof, it suffices to prove that Maker can
merge two components of $H[M]$ within two rounds, by claiming extra
vertices.

Let $C$ be a component of $H[M]$. Recall that $C$ spans an edge
$xy$, where $x\in D$ with $d(x)\ge \delta(H)\ge \delta^2 n/2$ and
$y\in N_H(x)\setminus D$ with $d(y)\geq(1-o(1))\delta n/2$. Let
$U=C\cup N_H(C)$. We may assume that $|N_H(x)\cup N_H(y)|\ge \delta
n/2$, since otherwise $|N_H(x)\cap N_H(y)|=d(x)+d(y)-|N_H(x)\cup
N_H(y)|\ge (1-o(1))\delta^2 n/2$, and Maker can claim a vertex in
$N_H(x)\cap N_H(y)$ to complete a triangle. Hence $|U|\ge
|N_H(x)\cup N_H(y)|\ge \delta n/2$. We consider two cases depending
on the size of $U^c$.

\textbf{Case 1:} $|U^c|\ge \delta n/2$. Then by Lemma~\ref{key2}
(i), $|E_H(U,U^c)|=\Omega(n^{3/2})$. Note that edges between $U$ and
$U^c$ can only go from $N_H(C)\setminus C$ to $U^c$. Therefore,
since $|N_H(C)\setminus C|\le n$, there exist $\Omega(\sqrt{n})$
many vertices $z\in N(C)\setminus C$ with
$d(z,U^c)=\Omega(\sqrt{n})$. Since Breaker's bias $b$ is a constant,
Maker can claim such a $z$ and one of its neighbors in $U^c$, say
$z'$, in two rounds. Since $z'\in U^c$, $z'$ is not adjacent to any
vertex in $C$. However, $D\subset M$ is a dominating set of $H$,
thus $z'$ is adjacent to some vertex in $M$ contained in a component
of $H[M]$ other than $C$. Thus after claiming $z$ and $z'$, Maker
merges two components of $H[M]$.

\textbf{Case 2:} $|U^c|<\delta n/2$. We are done if $U^c$ is empty,
thus $U^c$ is not empty and contains some component of $H[M]$, call
it $C'$. Similarly, $C'$ contains two adjacent vertices $x',y'$ such
that $d(x')\ge \delta^2 n/2$ and $d(y')\ge (1-o(1))\delta n/2$. We
may assume that $|(N(C)\cap N(C'))\setminus (C\cup C')|=o(n)$, since
otherwise Maker can merge two components in just one move by
claiming a vertex in $N(C)\cap N(C')$. Thus all but $o(n)$ vertices
in $N(x')\cup N(y')$ are in $U^c$. But $|U^c|<\delta n/2$, thus
$|N(x')\cap N(y')|\ge (1-o(1))\delta^2 n/2$. Then Maker can easily
claim a vertex in $N_H(x)\cap N_H(y)$ to complete a triangle.
{\hfill $\Box$
\medskip}



\section{Proofs of Theorems~\ref{main1} and~\ref{main3}}\label{main-pf}

In this section we prove Theorems~\ref{main1} and~\ref{main3}.

\textbf{Proof of Theorem~\ref{main1}.} First we describe a strategy for Maker and then
prove it is indeed a winning strategy. At any point during the game,
if Maker cannot follow the proposed strategy, then he forfeits the
game. Maker's strategy is divided into the following two stages:

\textbf{Stage I:} Let $H=(A\cup B, E_G(A,B))$ be a subgraph of $G$
as described in Lemma~\ref{key1} and let $e\in E_G(A)$. In his first
move, Maker claims the edge $e$.

\textbf{Stage II:} In this stage, Maker builds a connected spanning
subgraph of $H$.

Notice that if Maker can follow the proposed strategy then he wins
the game. Indeed, if Maker has built a connected spanning subgraph
of $H$, then since $H$ is a bipartite graph and $e$ is in one of its
sides then adding $e$ to Maker's graph creates an odd cycle. It thus
suffices to prove that indeed Maker can follow the proposed strategy
without forfeiting the game. We consider each stage separately.

\textbf{Stage I:} Follows immediately from Lemma~\ref{key1} and
since Maker is the first player to claim an edge.

\textbf{Stage II:} Apply Theorem~\ref{edge-conn} on $H$ with $b\le
\frac{\delta^2 n}{6400(\log_2 n)^2}$ and $k=\log_2 n$, then
$$100k\cdot b\cdot\log_2 b\le 100\log_2 n\cdot \frac{\delta^2 n}{6400(\log_2 n)^2}\cdot\log_2 n\le \frac{\delta^2 n}{64}.$$
Thus $H$ is $(100kb\log_2 b)$-edge-connected, and Maker has a
winning strategy for the $(1:b)$ $k$-edge-connectivity game played
on $E(H)$. In particular, Maker can build a connected spanning
subgraph of $H$.
{\hfill $\Box$ \medskip}

The idea for Theorem~\ref{main3} is similar, we provide only a sketch here.

\textbf{Proof of Theorem~\ref{main3}:} Let $G$ be a graph which satisfies
the conditions of Theorem~\ref{main3}. Set $k:=100\log_2 n\cdot
b\log_2 b$, then $G$ is $(100kb\log_2 b)$-edge-connected. Now we
consider two cases:

\textbf{Case 1:} Suppose that there exists a spanning subgraph
$G'\subseteq G$ that is bipartite and $k$-edge-connected. Then since
$\chi(G)\ge 3$, at least one side of $G'$ spans an edge in $G$.
Maker, in his first move, claims such an edge. Starting from his
second move, Maker plays a connectivity game on $E(G')$. Let
$k'=\log_2 n$, then $G'$ is $k=(100k'b\log_2 b)$-edge-connected.
Thus by Theorem~\ref{edge-conn}, Maker can build a
$k'$-edge-connected spanning subgraph $G''\subseteq G'$. Then $G''$
together with the first edge Maker claimed contains an odd cycle.

\textbf{Case 2:} Suppose that all spanning subgraphs of $G$ that are
$k$-edge-connected are non-bipartite. Then Maker plays the
$k$-connectivity game on $E(G)$. By Theorem~\ref{edge-conn}, he can
build a $k$-edge-connected spanning subgraph of $G$, which is, under
the assumption of Case 2, non-bipartite as desired. {\hfill $\Box$
\medskip}




\section{Proof of Theorem~\ref{main2}} \label{main2-pf}

In this section we prove Theorem~\ref{main2}.

\textbf{Proof.} First we describe a strategy for Maker and then
prove it is indeed a winning strategy. At any point during the game,
if Maker cannot follow the proposed strategy, then he forfeits the
game. Maker's strategy is divided into the following four stages:

\textbf{Stage I:} Let $H=(A\cup B, E_G(A,B))$ be a subgraph of $G$
as described in Lemma~\ref{key2}. In his first two moves, Maker
claims two adjacent vertices, $u$ and $v$, in $A$.

\textbf{Stage II:} In this stage, Maker claims a dominating set $D$
of $H$ of size $100\log n/\delta^2$.

\textbf{Stage III:} Let $D'=D\cup\{u,v\}$. In this stage, for every vertex
$w\in D'$, Maker claims a distinct vertex $z\in N(w)\setminus D'$ with
$d_H(z)=(1-o(1))\delta n/2$.

\textbf{Stage IV:} Let $M$ be the set of vertices that Maker has
claimed so far. In this stage Maker claims a set of vertices
$T\subseteq V(H)$ of size $O(\log n)$, for which $H[M\cup T]$ is
connected.


Notice that if Maker can follow the proposed strategy then he has
claimed an odd cycle. Indeed, if Maker connects $M$ in $H$, in
particular Maker has built a $(u,v)$-path, say $P$, in $H$. Then
since $H$ is a bipartite graph and $u$ and $v$ are in the same
partition class, $P$ is of even length. Thus $P$, together with the
edge $uv$ that he claimed in Stage I, form an odd cycle claimed by
Maker. Furthermore, we will show that Maker can also ensure an odd
cycle of constant length.

We prove that indeed Maker can follow the proposed strategy without
forfeiting the game.



\textbf{Stage I:} By Lemma~\ref{key2} (iv) we have $b+1< \chi(G[A])\le
\Delta(G[A])+1$. Hence $\Delta(G[A])\ge b+1$, namely there is a star
with $b+1$ leaves in $G[A]$. Since Breaker can only claim $b$
vertices at each round, Maker can claim the center of this star in
his first move and then claim one of its leaves in his second move.

\textbf{Stage II:} We show that by claiming vertices uniformly at
{\bf random}, after claiming $100\log n/\delta^2$ vertices, with
high probability (that is, with probability $1-o(1)$), Maker claims
a dominating set $D$ of $H$ against any strategy of Breaker. Since
the game of claiming a dominating set of $H$ in $100\log n/\delta^2$
moves is a finite, perfect information game (and therefore --
deterministic), it follows that Maker has a deterministic strategy
for claiming such a $D$ (although we do not describe it here). It
suffices to show that a set $D$ of $100\log n/\delta^2$ vertices
chosen uniformly at random from $V(H)$ is with high probability a
dominating set of $H$. Fix a vertex $x\in V(H)$, since $\delta(H)\ge
\delta^2 n/2$, the probability that no vertex from $N_H(x)$ is
chosen is at most $(1-\delta^2/2)^{100\log n/\delta^2}$. Applying
the union bound we get
$$\mathbb{P}\mbox{[$D$ is not a dominating set of $H$]}\le n\cdot (1-\delta^2/2)^{100\log n/\delta^2}\le n\cdot e^{-\frac{\delta^2}{2}\cdot 100\log n/\delta^2}=o(1).$$

It could happen that some vertex that Maker wants to claim, when
building $D$, is already taken by Breaker. However, Stages I and II
take only $|D|+2=O(\log n)$ rounds. Therefore, during the first two
stages Breaker claims $O(\log n)=o(n/\log n)$ many vertices. It thus
follows that, in each move, the probability that Maker will choose a
vertex which has already been claimed by Breaker is at most
$o(1/\log n)$. Hence, with probability $1-o(1)$ Maker never chooses
any vertex that Breaker has already claimed.

\textbf{Stage III:} By Lemma~\ref{key2} (ii) and (iii), every $w\in
D'$ has $\Theta(n)$ many neighbors, all but $o(n)$ of which have
degree $(1-o(1))\delta n/2$. Since $|D'|=O(\log n)=o(n)$, Maker can
secure such a distinct neighbor for each vertex in $D'$.

\textbf{Stage IV:} Let $F$ be the set of vertices that Breaker has
claimed in Stage I, II and III. Notice that $|F|=O(\log n)=o(n)$ has
negligible size. Applying Lemma~\ref{key3} to $H\setminus F$ gives
us the desired result.

We will finish the proof by showing that the odd cycle that Maker built is of constant length. Observe that with high probability $D$ from Stage II has the following property:

\textbf{(P1)} \quad$\forall v\in V(H)$, $d(v,D)\ge 25\log_2 n$.

Consider a vertex $v$ in $H$. Since $\delta(H)\ge \delta^2 n/2$, for
every vertex Maker has claimed in $D$, the probability that it is a
neighbor of $v$ is at least $\delta^2/2$. Thus the expected number
of neighbors of $v$ in $D$ is at least $\delta^2/2\cdot
|D|=\delta^2/2\cdot 100\log_2 n/\delta^2=50\log_2 n$. Thus a
standard Chernoff bound argument implies \textbf{(P1)}.

By \textbf{(P1)}, the minimum degree of Maker's graph is
$\Omega(\log n)$. On the other hand, Maker's graph is of order
$O(\log n)$, since the whole game ends in $O(\log n)$ rounds.
Therefore Maker's graph (even minus the special edge $uv$) is
connected and is of linear minimum degree (with respect to the order
of the graph), which implies that its diameter is constant
(see e.g, \cite{west} Problem 2.1.65). Therefore, removing the edge $uv$,
taking a shortest path between $u,v$ and adding $uv$ back, we obtain
an odd cycle of constant length. {\hfill $\Box$
\medskip}



\textbf{Acknowledgments:} A major part of this work was done when
the authors participated in the 4th Eml\'ekt\'abla workshop at Lake
Balaton. The authors wish to thank Bal\'azs Patk\'os and
D\"om\"ot\"or P\'alv\"olgyi for organizing this very nice event.

\begin{thebibliography}{99}

\bibitem{AHK}
N. Alon, D. Hefetz and M. Krivelevich, \emph{Playing to retain the
advantage}. Combinatorics, Probability and Computing 19 (2010),
481--491.


\bibitem{BFKM}
T. Bohman, A. Frieze, M. Krivelevich and R. Martin, \emph{Adding
random edges to dense graphs}. Random Structures and Algorithms 24
(2004), 105--117.

\bibitem{D}
R. Diestel, \textbf{Graph Theory}. Springer-Verlag, 4th edition,
(2010).

\bibitem{DLR}
D. Duffus, T.  {\L}uczak and V. R\"odl, \emph{Biased positional
games on hypergraphs}, Studia Scientarum Matematicarum Hungarica 34
(1998), 141--149.

\bibitem{west}
D. B. West, \textbf{Introduction to Graph Theory}. Prentice Hall,
2001.


\end{thebibliography}

\end{document}
