% guidelines for LaTeX formatting: http://www.integers-ejcnt.org/after.html \documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \begin{document} % my definitions \newtheorem{theorem}{Theorem} \newcommand{\brm}{\smallskip\noindent{\bf Remark.} } \newcommand{\erm}{\smallskip} \newcommand{\bpf}{\smallskip\noindent{\it Proof.} } \newcommand{\qed}{\nolinebreak\mbox{\hspace{5 true pt}% \rule[-0.85 true pt]{3.9 true pt}{8.1 true pt}}} \newcommand{\epf}{\qed \medskip} \newcommand{\claim}[1]{\smallskip\noindent{\bf Claim #1.}} \newcommand{\case}[1]{\smallskip\noindent{\bf Case #1.}} \newcommand{\Phase}[1]{\smallskip\noindent{\sc Phase~#1.}} \newcommand{\C}[1]{{\protect\cal #1}} \newcommand{\Lsym}{L_{\mbox{\scriptsize\rm sym}}} \newcommand{\blue}{{\mathrm{blue}}} \newcommand{\red}{{\mathrm{red}}} \begin{center} {\bf BREAKING SYMMETRY ON COMPLETE BIPARTITE GRAPHS OF ODD SIZE} \vskip 20pt {\bf Oleg Pikhurko\footnote{This research was carried out when the author was supported by a Research Fellowship, St.\ John's College, Cambridge, UK.}}\\ {\smallit Department of Mathematical Sciences\\ Carnegie Mellon University\\ Pittsburgh, PA 15213-3890}\\ {\tt http://www.math.cmu.edu/$\tilde{\ }$pikhurko/}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 10/25/02, Revised: 10/24/03, Accepted: 12/3/03, Published: 12/4/03} \vskip 30pt \centerline{\bf Abstract} \noindent Players $\C A$ and $\C B$ alternatively colour edges of a graph $G$, red and blue respectively. Let $\Lsym(G)$ be the largest number of moves during which $\C B$ can keep the red and blue subgraphs isomorphic, no matter how $\C A$ plays. This function was introduced by Harary, Slany and Verbitsky who in particular showed that for complete bipartite graphs we have $\Lsym(K_{m,n})=\frac{mn}2$ if $mn$ is even and that $\Lsym(K_{2m+1,2n+1})\ge \max(m,n)$. Here we prove that $$ \Lsym(K_{2m+1,2n+1})=O(n),\quad \mbox{if $m\le n\le m^{O(1)}$,} $$ answering a question posed by Harary, Slany and Verbitsky. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#G04\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} Let $G$ be a graph. The following \emph{symmetry breaking-preserving game} on $G$ was introduced by Harary, Slany and Verbitsky~\cite{harary+slany+verbitsky:02,harary+slany+verbitsky:02:tcs}. We have two players, $\C A$ and $\C B$, who alternatively select a previously uncoloured edge of $G$ and colour it red and blue respectively. Player $\C A$ starts the game. A move of $\C A$ followed by a move of $\C B$ is called a \emph{round}. Clearly, we have the same number of red and blue edges after every round. The aim of Player~$\C B$ is to keep the red and blue subgraphs isomorphic after every round of the game; as soon as $\C B$ fails to do so, he loses. Let $\Lsym(G)$ be the maximum number of moves during which $\C B$ can keep the red and blue subgraphs isomorphic, no matter how $\C A$ plays. Equivalently (see~\cite[Proposition~2.1]{harary+slany+verbitsky:02:tcs}) $\Lsym(G)$ is the smallest $k$ such that $\C A$ can guarantee his win in at most $k+1$ moves. It is not quite clear how to define $\Lsym(G)$ in the cases when $\C B$ can preserve the symmetry until the players run out of edges; following~\cite{harary+slany+verbitsky:02:tcs} we define $\Lsym(G)=\lfloor e(G)/2\rfloor$ then. One of the motivations of Harary, Slany and Verbitsky for introducing these notions was that $\Lsym(G)$ is clearly a lower bound on how long the second player can survive in any \emph{graph avoidance game} on $G$. (The rules of the avoidance game are the same except that the player who first constructs a monochromatic copy of a certain forbidden subgraph loses.) As it is observed in~\cite{harary+slany+verbitsky:02}, if $G$ has an involutary automorphism $\psi$ without fixed edges, then $\Lsym(G)=e(G)/2$. Indeed, every orbit of the induced action $\psi^*$ on $E(G)$ consists of two edges, so $\C B$ can use the \emph{copycat strategy} of choosing $\psi^*(e)\in E(G)$ where $e$ is the edge previously coloured by $\C A$. The determination of $\Lsym(G)$ is suddenly getting rather complicated and deep when we consider graphs which do not admit a copycat strategy but for which this cannot be derived by looking at a part of the graph. For example, when one considers the path $P_n$ with $n$ vertices, one has to know (the parity of) its order $n$ in order to ascertain the existence of an appropriate automorphism $\psi$. So, if $\C A$ follows some `local' strategy, $\C B$ might put up a strong resistance by playing copycat on a few separate parts of the graph. The surprising (at least to me) result of Harary, Slany and Verbitsky~\cite[Corollary~3.7 \& Proposition~3.8]{harary+slany+verbitsky:02:tcs} states that $$ (0.5+o(1))\, \log_2 n \le \Lsym(P_{2n})\le (3.5+o(1))\, (\log_2 n)^2. $$ Its proof exploits some beautiful connections to the so-called \emph{Ehrenfeucht-Fra\"\i ss\'e game}. Complete bipartite graphs of even size clearly admit a copycat strategy. The following argument from~\cite{harary+slany+verbitsky:02:tcs} shows that \begin{equation}\label{eq:Lower} \Lsym(K_{m,n})\ge \max({\textstyle \frac{m-1}2,\frac{n-1}2}),\quad \mbox{for odd $mn$.} \end{equation} Indeed, let $X\subset V(K_{m,n})$ be the bigger part of $K_{m,n}$. Starting with $\psi$ being the identity automorphism, $\C B$ uses the $\psi$-copycat strategy, that is, responds with $\psi^*(e)$ to the previous move $e$. This works unless $\psi^*(e)=e$ in which case $\C B$ locally modifies $\psi$ so that it exchanges $x$ and $y$ now, where $\{x\}=X\cap e$ and $y\in X$ is a vertex not incident to any coloured edge. Such $y$ always exists during the first $(|X|-1)/2$ rounds during which $\psi$ remains an involutary automorphism of $K_{m,n}$ swapping the blue and red subgraphs. Harary, Slany and Verbitsky~\cite[Question~4.3]{harary+slany+verbitsky:02:tcs} asked for the rate of growth of the function $\Lsym(K_{n,n})$ for odd $n$. The following more general result implies that $\Lsym(K_{m,n})$ grows linearly in $n$ if $m\le n\le m^{O(1)}$ and $mn$ is odd. \begin{theorem}\label{th:KmnUpper} Let odd integers $m$ and $n$ and an integer $k\ge8$ satisfy \begin{equation}\label{eq:m} 51\le m\le n\le \frac{(m-2k-3)^{k}}{(k+1)!\,m}. \end{equation} Then we have \begin{equation}\label{eq:Lsym} \Lsym(K_{m,n})\le k(n-m+3)+2m+14. \end{equation} In particular, if $m=n$, then letting $k=8$ we obtain \begin{equation}\label{eq:Upper} \Lsym(K_{n,n})\le 2n+38,\quad \mbox{for odd $n\ge 51$.} \end{equation} \end{theorem} In Section~3 we present the bound~(\ref{eq:Lsym}) as a more digestible, explicit function of $m$ and $n$. Let us describe the main idea behind the proof of Theorem~\ref{th:KmnUpper}. In outline, $\C A$ builds a red graph which has no non-trivial automorphism. If $\C B$ has not lost yet, the isomorphism $\psi$ between the red and blue graphs is unique and $\C B$ is \emph{forced} to play the $\psi^*$-copycat strategy now. As the total number of edges is odd, $\psi^*$ has at least one odd orbit $D\subset E(G)$. No matter how $D$ has been coloured, Player~$\C A$ can beat the $\psi^*$-copycat strategy on $D$ with at most two moves. So, if $\psi$ remains the unique isomorphism during these two moves of $\C A$, then $\C B$ loses. This method might be applicable to many graphs with odd size. Here is its concrete realisation for complete bipartite graphs. \vskip 30pt \section*{\normalsize 2. Proof of Theorem~\ref{th:KmnUpper}} We will describe the appropriate strategy of $\C A$ which consists of a few phases. Assume that $\C B$ keeps the red and blue subgraphs isomorphic throughout our strategy. Let $V\cup V'=V(K_{m,n})$ be the vertex classes, where $|V|=m$. \Phase{1} $\C A$ builds a red cycle of length $2l\in[2m-6,2m-2]$, say visiting vertices $x_1,x_1',\dots,x_l,x_l'$ in this order, plus one edge from some vertex $y_0\in Y$ to $X'$, where we denote $X=\{x_1,\dots,x_l\}\subset V$, $X'=\{x_1',\dots,x_l'\}\subset V'$, $Y=V\setminus X$, and $Y'=V'\setminus X'$. The red/blue subgraph will have maximum degree at most $2$ at any moment before the end of Phase~1, so in particular $\C A$ can easily create a red path of length $2m-7$ by choosing vertices $x_1,x_1',\dots,x_{m-3},x_{m-3}'$ one by one in this order. If the edge $\{x_1,x_{m-3}'\}$ is available, then $\C A$ colours it and we are done because the addition of an edge between $X'$ and $Y$ is always possible as $m-3>2$. Otherwise, $\C A$ extends the path by two more edges. Now, if $\{x_1,x_{m-2}'\}$ is available, then $\C A$ selects it and we are done again. Otherwise, $\C A$ can add $x_{m-1}$ to the path: indeed, the vertex $x_{m-2}'$ sends a blue edge to $x_1$, so it sends at most one blue edge to $V\setminus X$. If $\{x_{m-1},x_1'\}$ is available, then $\C A$ selects it, obtaining the desired configuration (up to relabelling). Otherwise, the edge $\{x_{m-1},x_1'\}$ is blue and $\C A$ can extend the path to $x_{m-1}'$. In the next move $\C A$ colours the edge $\{x_1,x_{m-1}'\}$ which cannot be blue because we have already encountered two blue edges incident to $x_1$. Finally, $\C A$ connects some $y_0\in Y$ to $X'$, obtaining the desired configuration in all cases. \Phase{2} $\C A$ connects $Y$ to $X'$. The vertex $y_0\in Y$ will play a special role. Assume that $x_1'$ is the vertex in $X'$ connected to $y_0$ by a red edge. Consider first the case when $y_0$ is incident to at least one blue edge. By reversing, if necessary, the direction of the red $2l$-cycle, we can assume that $y_0$ has at least one blue neighbour \emph{outside} $\{x_1',\dots,x_{10}'\}$. In the next five moves $\C A$ colours $\{y_0,x_i'\}$ for the smallest possible index $i\ge 2$ each time. Suppose that the last such edge was $\{y_0,x_s'\}$. When $\C A$ was colouring it, at most $5$ edges incident to $y_0$ were blue of which at most $4$ lie in $X_0'=\{x_1',\dots,x_s'\}$. Hence $s\le 10$. In the next three moves $\C A$ colours $\{y_0,x_i'\}$, where $i$ is the smallest available index with $i\ge 2s$ except, when colouring the third edge in the case $s=6$, the additional condition on $i$ is that the indexes of the last three red neighbours of $y_0$ do not form an arithmetic progression. (Note that for $s\ge 7$ the indexes of the \emph{first} six neighbours of $y_0$ cannot form a six-term arithmetic progression as $s\le 10$.) Let $t>2s$ be the largest index of a red neighbour of $y_0$ and let $X_1'=\{x_{2s}',\dots,x_t'\}$. We claim that $t\le 26$. If $s\ge 7$, then $y_0$ sends at most $8-(s-6)=14-s$ blue edges to $X_1'$ because $y_0$ sends $s-6$ blue edges to $X_0'$; thus \begin{equation}\label{eq:t} t-2s+1=|X_1'|\le 3+(14-s), \end{equation} which gives the required in view of $s\le 10$. If $s=6$, then we have to add $1$ to the bound~(\ref{eq:t}), still obtaining the claimed inequality $t\le 26$. If $y_0$ is not incident to a blue edge at the end of Phase~1, then this stays so, in whichever manner we add red edges incident to $y_0$. In particular, $\C A$ can connect $y_0$ to $$ \{x_1',x_2',\dots,x_6',x_{12}',x_{13}',x_{15}'\} $$ and we have $s=6$ and $t=15$. Next, $\C A$ connects the vertices of $Y\setminus\{y_0\}$ to $X'$, by five edges each, so that distinct vertices of $Y$ have disjoint neighbourhoods in $X'$, which is possible as $l> 2\cdot9+5\cdot(|Y|-1)$. The first two phases last for $r_2=2l+9+5(m-l-1)$ rounds. \Phase{3} If $m=n=l+1$, then $\C A$ connects the (unique) vertex of $Y'$ to arbitrary $12$ vertices of $X$. Otherwise, $\C A$ picks vertices of $Y'$ one by one and connects each selected vertex by $k$ edges to $X$. Suppose that $\C A$ has already dealt with $y_1',\dots,y_i'\in Y'$ and connected the next vertex $y'\in Y'$ to a set $H\subset X$ of size $h\in[0,k-1]$. Let $\Gamma_\red(y)$ (resp.\ $\Gamma_\blue(y)$) denotes the red (resp.\ blue) neighbourhood of a vertex $y$. We claim that $f$, the number of vertices in $F=\Gamma_\blue(y')\cap X$, will be at most $k+1$ when we deal with the vertex $y'$. This is true for $i\le 3$ when the maximum degree of the blue graph is at most $\max(k,9)$. If $i\ge 4$, then the isomorphism between the red and blue graphs must respect the classes $V$ and $V'$ because the non-trivial red component has at least $l+i>|V|$ vertices in $V'$. So the blue degree of $y'$ is at most the maximum red degree of a vertex in $V'$ which is $k$, giving the desired bound on $f$. Here is the strategy: $\C A$ connects $y'$ to a vertex $x\in X\setminus (F\cup H)$ such that $\mu(H\cup\{x\})$ is minimum, where $$ \mu(Z)=\sum_{j=1}^{i} c_{|Z\setminus \Gamma_\red(y_j')|},\quad Z\subset X, $$ where $c_0=l$, $c_1=1$, and all other $c$'s are zero. In other words, $$ \mu(Z)=l\, \left| \left\{j\in[i]\mid Z\subset \Gamma_\red(y_j')\right\}\right| + \left| \left\{j\in[i]\mid |Z\setminus \Gamma_\red(y_j')|=1\right\}\right|. $$ It is easy to see that \begin{eqnarray*} \sum_{x\in X\setminus(F\cup H)} \mu(H\cup\{x\}) &\le& \sum_{j\in[i]\atop H\subset\Gamma_\red(y_j')} (c_0(k-h)+c_1(l-k))\\ &+& \sum_{j\in[i]\atop |H\setminus \Gamma_\red(y_j')|=1} c_1(k-h+1)\ \le\ (k-h+1) \mu(H), \end{eqnarray*} by straightforwardly comparing the corresponding terms. Hence, $\C A$ can choose an $x\in X\setminus (F\cup H)$ such that $$ \mu(H\cup\{x\})\le \frac{k-h+1}{l-f-h}\, \mu(H)\le \frac{k-h+1}{m-2k-3}\, \mu(H).$$ As $\mu(\emptyset)=li1$ and let $e\in D$. Now $e'=\psi^*(e)$ and $e''=(\psi^*)^{-1}(e)$ are two distinct edges belonging to $D$. Suppose first that $e=\{x_i,x_j'\}$ and that both $C\cup\{e,e'\}$ and $C\cup\{e,e''\}$ have a $2l$-cycle passing through the edge $e$. Trivial considerations show that \begin{equation}\label{eq:ePePP} \left\{e',e''\right\}=\left\{\,\{x_j,x_{i-1}'\},\,\{x_{j+1},x_i'\}\,\right\}. \end{equation} (Of course, we do all index calculations modulo $l$.) If $\psi(V)=V$, then~(\ref{eq:ePePP}) means that for some $\delta=\pm1$ we have $\psi^\delta(x_{i})=x_{j+1}$, $\psi^\delta(x_j')=x_i'$, $\psi^{-\delta}(x_i)=x_j$ and $\psi^{-\delta}(x_j')=x_{i-1}'$. But then $\psi^\delta$ maps the red edge $\{x_j,x_j'\}$ into the red edge $\{x_i,x_i'\}$, a contradiction. In the same way we obtain a contradiction in the case $\psi(V)=V'$. Thus, by the first part of Claim~1, we can assume that we can recover $C$ from knowing, for example, $A\cup\{e,e'\}$. Now, $\C A$ selects $e'$ to which, by Claim~2, $\C B$ is forced to reply by colouring $\psi^*(e')$. Then $\C A$ selects $e\not=\psi^*(e')$. Claim~1 implies that $A$ is the unique subgraph of $A\cup\{e,e'\}$ isomorphic to $A$ and the argument of Claim~2 shows that $\C B$ loses. Let us count the total number $r_4$ of rounds. If $n=m=l+1$, then $$ r_4\le 2(m-1) +9+12+2\le 3(n-m+k)+2m+15, $$ as $k\ge 8$. Otherwise, $$ r_4\le 2l+9+5(m-l-1)+k(n-l)+2\le k(n-m+3)+2m+15, $$ where we used the inequality $l\ge m-3$. This finishes the proof of Theorem~\ref{th:KmnUpper} as $\Lsym(K_{m,n})\le r_4-1$. \vskip 30pt \section*{\normalsize 3. Concluding Remarks} It is not hard to convert our strategy into an algorithm which has running time $O(mn)$ per one move of $\C A$. Unfortunately, not for every pair $(m,n)$ an integer $k$ satisfying~(\ref{eq:m}) can be found. For example, if $n>2^m$, then any subgraph of $K_{m,n}$ contains two vertices in $V'$ with the same neighbourhood in $V$, which ruins our strategy. The value of $n$ can range up to $$ \max_{k\ge 8} \frac{(m-2k-3)^k}{(k+1)!\, m}= (1.531...+o(1))^m.$$ The optimal choice is to take the smallest integer $k\ge 8$ satisfying~(\ref{eq:m}). If $m$ is large, then the following formulae can be routinely verified. If $\log n/\log m< 7-o(1)$, then $k=8$. If $7-o(1)\le \log n/\log m=O(1)$, then $$ \frac{\log n}{\log m}+1< k< \frac{\log n}{\log m}+3. $$ If $O(\log m)<\log n=o(m)$, then $$ k=(1+o(1))\, \frac{\log n}{\log m-\log \log n}. $$ If $(1+o(1))^m