\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P10}{20(3)}{2013}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx, epsfig}
\usepackage{color}
\usepackage{array}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\abs}[1]{\left\vert #1 \right\vert}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\paren}[1]{\left( #1 \right)}
\newcommand{\rest}[2]{#1\vert_{#2}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\conjecturesize}{t_n}
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\vmod}[2]{#1_{(#2)}}


\DeclareMathOperator{\shannon}{c_0}
\DeclareMathOperator{\con}{con}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\bad}{bad}
\DeclareMathOperator{\fan}{Fan}
\DeclareMathOperator{\ex}{ex}



\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem*{cl}{Claim}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{goal}[theorem]{Goal}
\newtheorem{definition}[theorem]{Definition}
\newtheorem*{lrc}{Lonely runner conjecture}

\newcommand{\eqd}{\buildrel d \over =}
\newcommand{\zeet}{{\mathbb Z}^{2}}
\newcommand{\reet}{{\mathbb R}^{2}}
\newcommand{\zee}{{\mathbb Z}}
\newcommand{\ree}{{\mathbb R}}
\newcommand{\reep}{{\mathbb R^+}}
\newcommand{\pee}{{\mathbb P}}
\newcommand{\nee}{{\mathcal N}}
\newcommand{\dee}{{\mathcal D}}
\newcommand{\bee}{{\mathcal B}}
\newcommand{\oee}{{\mathcal O}}
\newcommand{\aee}{{\mathcal A}}
\newcommand{\hee}{{\mathcal H}}
\newcommand{\gee}{{\mathcal G}}
\newcommand{\tee}{{\mathcal T}}
\newcommand{\lee}{{\mathcal L}}
\newcommand{\e}{\epsilon}
\newcommand{\neara}{150 \rho^{3} (\log{\rho}+1) }
\newcommand{\nearb}{R}
\newcommand{\nearc}{R - 3 \rho^{3}}
\newcommand{\vp}{\varphi_{C_{m}}}

\newcommand{\mnote}[1]{\marginpar{
\footnotesize\raggedright\linepenalty=5000 #1}}


\def\D{\Delta}
\def\d{\delta}

\title{\bf On the Independence Numbers\\ of the Cubes of Odd Cycles}

\author{Tom Bohman \thanks{Supported in part by
NSF grant DMS 0401147.}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Carnegie Mellon University\\[-0.8ex]
\small Pittsburgh, U.S.A.\\
\small\tt tbohman@moser.math.cmu.edu\\
\and Ron Holzman \thanks{Research supported by the
Fund for the Promotion of Research at the Technion and by the P. and
E. Nathan Research Fund.}\\
\small Department of Mathematics\\[-0.8ex]
\small Technion--Israel Institute of Technology\\[-0.8ex]
\small Haifa, Israel\\
\small\tt holzman@tx.technion.ac.il\\
\and Venkatesh Natarajan\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Carnegie Mellon University\\[-0.8ex]
\small Pittsburgh, U.S.A.}
\date{\dateline{Aug 3, 2012}{July 24, 2013}{Aug 2, 2013}\\
\small Mathematics Subject Classifications: 05C38, 05C69}

\begin{document}

\maketitle

\begin{abstract}
%\noindent
%Motivated by the problem of determining the
%Shannon capacities of
%odd cycles,
We give an upper bound on the independence number of the cube of
the odd cycle \( C_{8n + 5} \). The best known lower bound is
conjectured to be the truth; we prove the conjecture in the case
\( 8n+5\) prime and, within 2, for general \(n\).
%
%This upper bound gives the independence number if \( 8n+5\) is
%prime. If \( 8n+5\) is not prime then gap between the upper bound
%given here and best known lower bound is 2.
%The proof of the upper bound uses a stability result for
%independent sets in the squares of odd cycles.
\end{abstract}





\section{Introduction}
Let \( G_1= (V_1,E_1) \) and \( G_2 = (V_2,E_2) \) be graphs.  The
product of \(G_1\) and \(G_2\) is the graph \(G_1 \times G_2\) which
has vertex set \( V_1 \times V_2 \) and  an edge between distinct
vertices \( (x_1,x_2) \) and \( (y_1, y_2)\) if and only if
% For \( d \ge 1 \) let \( G^d \) be the
%graph with vertex set \( V^d \) and an edge between vertices \(
%(x_1, \dots , x_d) \) and \( (y_1, \dots, y_d) \) if and only if
\( x_i = y_i \) or \( \{x_i,y_i\} \in E_i \) for \(i =1,2 \).  For
\( d \ge 1 \) the graph power \( G^d \) is the product of \(G\) with
itself \(d\) times. The Shannon capacity of \(G \) is
\[ c(G) =
\sup_d  \left( \alpha \big( G^d \big) \right)^{1/d} \]
where \( \alpha(H) \) is the size of the largest
independent set in graph
\(H\).  This graph invariant was introduced by Shannon in 1956
and gives a measure of the optimal zero-error
performance of an associated memoryless
communication channel \cite{Sh}.

Determining the Shannon capacity of an arbitrary graph is a notoriously hard problem. Shannon himself gave an upper bound, which may be stated in graph thoretic notation as $c(G) \le \alpha^*(G)$, where $\alpha^*(G)$ is the fractional vertex packing number. (The latter is a natural linear
programming relaxation of the independence number; namely, $\alpha^*(G)$ is the
maximum, over all assignments of non-negative real weights to the
vertices of \(G\) with the property that the sum of weights over any
clique is at most 1, of the sum of weights of the vertices of \(G\).)
 This upper bound was discussed in detail in \cite{ros}. A better upper bound $c(G) \le \theta(G)$ is given by the Lov\'asz theta function \cite{L}. Another upper bound, which is not comparable with the former two, was given by Haemers \cite{hae}.
(For a survey of zero-error
information theory see \cite{KO}.  For recent progress on the
sums of disjoint channels using linear algebraic
methods see \cite{noga1}, \cite{al2}.)


Motivated in part by the problem of determining the Shannon
capacities of graphs, Berge introduced the notion of a perfect
graph \cite{B}.  A graph \(G\) is perfect if \( \omega(H) =
\chi(H) \) for every induced subgraph \(H\) of \(G\), where \(
\omega(H) \) is the size of the largest clique in \(H\) and \(
\chi(H) \) is the chromatic number of \(H\). Perfect graphs are
known to satisfy \( c(G)= \alpha(G)\). Berge conjectured that
a graph is perfect if and only if it does not contain an odd cycle
of length five or more, or the complement of such a graph, as an
induced subgraph. This long standing conjecture, known as the
strong perfect graph conjecture, was recently proved
by Chudnovsky, Robertson, Seymour and Thomas
\cite{crst} (for an overview of the proof, see \cite{gerard}).  It
follows from this result that the odd cycles of length five or
more and their complements are the minimal graphs for which the
determination of the Shannon capacity is nontrivial.
The best known upper bounds on the Shannon capacities of these
graphs are given by the Lov\'asz theta function.
%\begin{gather*}
%c( C_{2n+1} ) \le \vartheta( C_{2n+1} ) = \frac{ (2n+1) \cos
%\left( \pi / (2n+1) \right) }{1 + \cos\left( \pi/(2n+1) \right)} =
%n + \frac{1}{2} - O(1/n),\\ \c( \overline{C}_{2n+1} ) \le
%\vartheta( \overline{C}_{2n+1} ) = \frac{1 + \cos\left( \pi/(2n+1)
%\right)} { \cos \left( \pi / (2n+1) \right) } = 2 + O(1/n^2).
%\end{gather*}
%Since \( \alpha( C_5^2) = 5 \),
This upper bound suffices to
establish the Shannon capacity of \( C_5 \), which is self
complementary: \(  c( C_5) = c( \overline{C}_5)=
\sqrt{5} \). However, the Shannon capacities of odd cycles and the
complements of odd cycles on seven or more vertices remain
unknown.

In this paper we focus on odd cycles (for recent progress on the
complements of odd cycles see \cite{withron}) and consider the
following question: For fixed values of \(d\) and \(\ell\) what is
\( \alpha( C_{2\ell+1}^d ) \)? This question was first addressed
some time ago by Baumert, McEliece, Rodemich, Rumsey, Stanley and
Taylor \cite{BMRRST} and Hales \cite{H}.  In \cite{BMRRST} it is
noted that this question is equivalent to the following natural
question: How many \(d\)-dimensional cubes of side length \(2\) can
we pack into a \( d\)-dimensional torus of side length \( 2\ell+1
\)?

While there are a number of constructions (see \cite{BMRRST}, \cite{Bo2}, \cite{cgr}, \cite{H}) that give lower bounds on
\( \alpha( C_{2\ell+1}^d ) \),
there are essentially no upper bounds that take into account the
special structure of odd cycles. We get an upper bound on \( \alpha
( C_{2\ell+1}^d ) \) by appealing to either the Lov\'asz theta
function,
\begin{equation}
\label{eq:lov}
\alpha( G^d) \le \vartheta( G)^d,
\end{equation}
or the well-known inequality (proved below in Section~\ref{sec:prelim}):
\begin{equation}
\label{eq:frac}
\alpha( G \times H) \le \alpha(G) \alpha^*(H).
\end{equation}
The only choice
of parameters \(d,\ell\) for which we have an upper bound on \(
\alpha( C_{2\ell+1}^d ) \) that is better than that given by
(\ref{eq:lov}) and (\ref{eq:frac}) (other than two specific small
examples) is the case \( d \ge 3 \) and \( \ell \equiv 2^{d-2} \mod
2^{d-1} \).  Here Baumert et al. \cite{BMRRST} proved that the independence number is at most the bound
given by (\ref{eq:frac}) minus 1. On the other hand, there are
values of parameters \( d,\ell \) where (\ref{eq:lov}) or
(\ref{eq:frac}) give the truth:
\begin{align}
\alpha\left( C_5^{2j} \right) & = 5^j =  \vartheta( C_5 )^{2j}  \label{eq:l} \\
\alpha\left( C_{k2^d+1}^d \right) & = k ( k 2^d+1)^{d-1} = 2^{d-1}k
\left( \frac{ k2^d + 1}{2} \right)^{d-1}
= \alpha( C_{k 2^d+1}) \alpha^*\left(  C_{k2^d+1}^{d-1} \right) \label{eq:h} \\
\alpha\left( C_{k2^d+3}^d \right) & = \frac{  k ( k 2^d+3)^d + 1}{ k2^d + 1 }
= \left\lfloor  \left( \frac{  2 k ( k 2^d+3)^{d-1} + 1}{ k2^d + 1 } \right)
\left( \frac{ k2^d+3}{2} \right)      \right\rfloor  \label{eq:bmrrst} \\
& \hskip5cm = \left\lfloor \alpha\left( C_{k2^d+3}^{d-1} \right)
\nonumber \alpha^*( C_{k2^d+3} ) \right\rfloor
\end{align}
Equation (\ref{eq:l}) was established in the celebrated paper of
Lov\'asz \cite{L}.  Hales \cite{H} and Baumert et al. \cite{BMRRST}
independently established (\ref{eq:h}), and Baumert et al.
\cite{BMRRST} proved (\ref{eq:bmrrst}).

Given this state of affairs, the first interesting case is \(
\alpha ( C_{8n+5}^ 3) \). \noindent Setting
\[ t_n = (8n+5)\frac{(2n+1)(8n+5)-1}{2}, \]
we can summarize the current state of our understanding as
follows: \begin{equation} \label{eq:state}
  \conjecturesize
%(8n+5)^2 n + (8n+5)(4n+2)
\le \alpha \left( C_{8n+5}^3 \right)
\le \conjecturesize + 4n + 1
%(8n+5)^2n + (8n+5)(4n+2) + 4n+1
. \end{equation} The lower bound is given by construction
\cite{BMRRST},\cite{Bo2} (for the sake of completeness one of these
constructions is reproduced in Subsection~\ref{sec:construct}
below). The upper bound is one less than the bound given by
(\ref{eq:frac}) (as established in \cite{BMRRST}). (For small values
of \(n\) the Lov\'asz theta function gives a slightly better upper
bound.) Baumert et al. \cite{BMRRST} conjectured that \( \alpha( C_{8n+5}^3 ) = t_n
\) for all \(n\).

Now, we are ready to state our main results.
\begin{theorem}
\label{thm:easy} If \( 8n+5 \) is prime then \( \alpha\left(
C_{8n+5}^3 \right) =
%(8n+5)^2 n + (8n+5)(4n+2)
\conjecturesize  \).
\end{theorem}
\noindent
This settles the above conjecture for an infinite sequence of cycle lengths. In particular, it yields $\alpha (C_{13}^3) = 247$. (Codenotti et al. \cite{cgr} used a computer search to establish the best previously known upper bound of $251$ for this value.) Natarajan \cite{venky} has recently settled the conjecture for another infinite sequence; namely, he proved that
if \( 2n+1 \) is prime then
\( \alpha\left( C_{8n+5}^3 \right) =
%(8n+5)^2 n + (8n+5)(4n+2)
\conjecturesize
\). For general $n$, we obtain an upper bound which differs from the conjectured value by $2$.
\begin{theorem}
\label{thm:main}
For all $n$,
\[ \alpha\left( C_{8n+5}^3 \right) \le
%(8n+5)^2 n + (8n+5)(4n+2)
\conjecturesize
+ 2. \]
\end{theorem}

Our proofs are based on a dimension-reduction technique, which may be briefly explained as follows. We consider the two-dimensional slices of $C_{8n+5}^3$, which we call `planes'. Each of them consists of the vertices that have, in a given coordinate (the `direction' of the plane), one of two consecutive values, and arbitrary values in the other two coordinates. Given an independent set $S$ in $C_{8n+5}^3$, its intersection with each plane projects onto an independent set in $C_{8n+5}^2$. If $S$ contains more than $t_n$ vertices, then a calculation shows that in each direction there must be at least two planes for which this projection yields a maximum independent set in $C_{8n+5}^2$, and for most planes it yields independent sets of size at least $\alpha(C_{8n+5}^2)-1$. Now, the structure of maximum independent sets in $C_{8n+5}^2$ is well understood (due to \cite{BMRRST}). Our proof of Theorem~\ref{thm:easy} consists of showing that, when $8n+5$ is prime, six planes with this structure -- two in each of the three directions -- cannot fit together. This is no longer true when $8n+5$ is composite, and therefore we consider in the proof of Theorem~\ref{thm:main} also those planes with $\alpha(C_{8n+5}^2)-1$ vertices of $S$. We have obtained a full characterization of these almost maximum independent sets. This may be viewed as a stability result, essentially showing that all almost maximum independent sets are slightly modified maximum ones. The proof of Theorem~\ref{thm:main} then consists of showing that many planes in every direction, each of them having the structure of a maximum independent set or a slight modification of it, cannot fit together. Because the statement of the above-mentioned stability result is complicated and its proof is tedious, they do not appear in this version of the paper; only the relevant consequences for the proof of Theorem~\ref{thm:main} are stated. The interested reader is referred to the original, much longer version of the paper (available from the first author's home page). We emphasize that the proof of Theorem~\ref{thm:easy} does not require this stability result; the proof of Theorem~\ref{thm:easy} is short and completely contained herein. For other applications of stability methods in extremal combinatorics, in
particular in the context of hypergraph Tur\'an theory, see for
example \cite{stabkm}, \cite{stabks}, \cite{stabs}.

Although our main results only deal with three dimensions and cycles of length $5(\bmod 8)$, we believe that the methods developed here are of interest for the more general problem of giving upper bounds on the independence numbers of powers of odd cycles. Good upper bounds for arbitrary powers of odd cycles (at least of certain lengths) would lead to improved upper bounds on, or even a determination of, the Shannon capacities of these graphs. This is the ultimate goal, yet it looks pretentious at this stage. While the dimension-reduction technique described above is available in all dimensions, the structural information about the lower-dimensional objects is not (it could possibly be achieved inductively). For many cycle lengths, there are not even good-looking constructions, the optimality of which one could hope to prove; such is the case with $C_7$. Still, we have had some success applying similar methods to higher powers. In \cite{bhn} we gave a complete classification of all maximum independent sets in powers of odd cycles of the form $C_{k2^d+1}^d$. In other (unpublished) work, we used stability results for large independent sets in $C_9^2$ and $C_9^3$ to establish the upper bound $\alpha(C_9^4) \le 350$. As $\alpha(C_9^3)=81$ by (\ref{eq:h}), this shows that $(\alpha(C_9^4))^{1/4}<(\alpha(C_9^3))^{1/3}$, and thus offers some support for our conjecture that the Shannon capacity of $C_9$ is attained in the third power.

The remainder of this paper is organized as follows.  In
Subsection~\ref{sec:construct} we give a construction that achieves
the lower bound in (\ref{eq:state}).  In Section~\ref{sec:prelim} we
introduce some preliminary facts, including the classification of
maximum independent sets in \( C_{4m+1}^2 \). Theorem~\ref{thm:easy} is proved in Section~\ref{sec:proofeasy}.  The proof of Theorem~\ref{thm:main} is
described in Section~\ref{sec:proofits}, omitting the details of the stability part (as explained above).
\subsection{Construction}
\label{sec:construct}

The construction we give here is taken from \cite{Bo2}.

We assume $n \ge 1$, and identify \( C_{8n+5} \) and \( {\mathbb
Z}_{8n+5} \) in the natural way.  Define
\[ J = \left\{ (x,y,z)
\in {\mathbb Z}_{8n+5}^3 : 4x + 2y + z = 0 \right\}, \] where the
operation is taken over \( {\mathbb Z}_{8n+5} \).  Note that \(J\)
is an independent set as the difference of a pair of distinct
elements of \(J\) is in \(J\) and therefore not in the set
\(\{-1,0,1\}^3 \). We will make use of the stronger property that no
pair of distinct elements of \(J\) have difference in the set \(
[-2n,2n] \times \{-1,0,1\}^2 \). This property allows us to form an
independent set by replacing each element \(a\) of \(J\) with a
collection of vertices `centered' at \(a\).  Let \( e_1 \) be the
first standard basis vector and for \(i \ge 1\) let
\[
P_i = \left\{(-i+1) e_1, (-i+3) e_1, \dots , (i-3)e_1, (i-1)e_1
\right\}.\]  Note that \( |P_i| = i \) and that \( P_i\) is an
independent set.  Define the parity of \( (x,y,z) \in J \) to be the
parity of \(z\). Our independent set of size $t_n$ is the following:
\[
I = \left( \bigcup_{ a \in J: \ a  \text{ is even}} a + P_{n}
\right) \cup \left( \bigcup_{ a \in J: \ a \text{ is odd}} a +
P_{n+1}\right).
\]
Since no pair of distinct elements of \(J\) have difference in \(
[-2n,2n] \times \{-1,0,1\}^2 \), if \( a,b \) are distinct elements
of $J$ then no vertex in \( a + P_{n} \) is adjacent to a vertex in
\(b + P_n \) or in $b + P_{n+1}$. So, we can restrict our attention
to odd \(a,b\) with the same third coordinate and second coordinate
differing by 1. Such pairs of vertices differ by \(4n+2\) in the
first coordinate.


%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
\section{Preliminaries}
%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
\label{sec:prelim}

\subsection{Proof of inequality (\ref{eq:frac})}
\label{subsec:proofineq}

We consider an independent set $S$ in the product $G \times H$ of graphs $G$ and $H$. To every vertex $y$ of $H$ we assign the weight $w(y)=|S \cap (G \times \{y\})|/\alpha(G)$. If $K$ is a clique in $H$ then the first coordinates of the vertices in $S \cap (G \times K)$ must form an independent set in $G$; therefore we have $\sum _{y \in K}w(y) \le 1$. Hence this is a fractional vertex packing, and thus its total weight $|S|/\alpha(G)$ is a lower bound on $\alpha^*(H)$. Inequality (\ref{eq:frac}) follows.

Although this inequality is well known, we included the proof because the consideration of sets of the form $G \times K$, where $K$ is a clique in $H$, is the essence of our dimension-reduction technique (see the concept of a slice, which we introduce below).

\subsection{Notational conventions}
\label{subsec:notation}

Throughout the
paper we discuss products and powers of
odd cycles, in many cases restricting attention to cycle lengths
having certain residues modulo $4$ or $8$. In an attempt to reduce
confusion, we use $\ell$ to write an arbitrary odd length as
$2\ell+1$, we use $m$ when we care about the residue modulo $4$,
e.g., $4m+1$, and we use $n$ when we care about the residue modulo
$8$, e.g., $8n+5$.

We identify the vertices of \( C_{2\ell+1} \) with the elements of
\( {\mathbb Z}_{2\ell+1} \) throughout.  Unless otherwise noted,
operations on vertices are taken over this ring.

We use the standard notation $[d]=\{1,\ldots,d\}$.

\subsection{Slices}
\label{subsec:slices}

Consider the graph \(G= \prod_{i=1}^d
C_{2\ell_i+1} \).  Given a set \( I \subseteq [d] \) and a vector
\( {\bf x} \in \prod_{i\in I} {\mathbb Z}_{2\ell_i+1} \), the {\bf
slice} of \(G\) given by \(I = \{s_1, \dots, s_k \}\) and \( {\bf
x} = ( x_1, \dots, x_k) \) is the set of vertices
\[ \left\{ (v_1, \dots , v_d) \in G:  v_{s_i} \in \{ x_i, x_i+1\}
\text{ for } i = 1 ,\dots, k \right\}. \] Note that when we drop
the coordinates in \(I\) this slice projects onto the graph \(
\prod_{i \not\in I} C_{2\ell_i+1} \).  Furthermore, if \( S \) is
an independent set in \(G\) then \(S\) intersected with the slice
maps onto an independent set in \( \prod_{i \not\in I}
C_{2\ell_i+1} \) under this projection. The {\bf dimension} of the
slice given by \(I\) and \({\bf x} \) is \( d -|I| \). Here we
will work extensively with two special cases of slices.
\begin{definition}
Consider the graph \( C_{2\ell+1}^3 \). Let \( d \in [3] \) and \(
y \in {\mathbb Z}_{2\ell+1} \). We define the {\bf dual plane}
\[ P_{y,d} = \left\{ (x_1, x_2, x_3) \in  {\mathbb Z}_{2\ell+1}^3
:  x_d \in \{y,y+1\} \right\}. \] If \( S \subset C_{2\ell+1}^3 \)
is an independent set then we set \( S_{y,d} = S \cap P_{y,d} \).
Note that we can view \( S_{y,d} \) as an independent set in \(
C_{2\ell+1}^2 \) by simply dropping coordinate \(d\).
\end{definition}
\begin{definition}
Consider the graph \( G = C_{2\ell_1+1} \times C_{2\ell_2+1} \)
and $S$ an independent set in $G$.  The $r$th {\bf dual row} is
the set of all $(x,y) \in S$ so that $y \in \{ r, r + 1 \} $.
Similarly, the $c$th {\bf dual column} is the set of all $(x,y)
\in S$ so that $x \in \{ c, c+1 \} \). A {\bf dual line} is a dual
row or a dual column.
\end{definition}

\subsection{Holes}
\label{subsec:holes}

The property of being an independent set may be defined by the system of constraints requiring that at most one vertex be picked from every maximal (with respect to inclusion) clique. In describing a particular independent set, it is useful to note which of these constraints are satisfied as equalities and which of them are not. In the following definition we focus on the latter.
\begin{definition}
Let $G$ be a graph, and let $S$ be an independent set in $G$.  A
set of vertices $K$ is a {\bf hole} of $S$ if $K$ is a maximal
clique in $G$ and $K \cap S = \emptyset$.  We let \( H(S) \)
denote the set of holes of the independent set \(S\). In
$G=\prod_{i=1}^d C_{2\ell_i+1}$ with $\ell_i \ge 2$, the maximal cliques are precisely the maximum cliques, namely they are of the form $K_v := \set{v} + \set{0,1}^d$. By a slight abuse of terminology, we say that $v$ is a hole if $K_v$ is. (In other words, a hole is a $d$-dimensional cube, but by convention, we specify it using the coordinate values of its lower-leftmost vertex.)
\end{definition}
\noindent
Note that if \( S_1 \) and \( S_2\) are independent sets in a product of odd
cycles then \( H(S_1) = H(S_2) \) if and only if \( S_1 = S_2 \).
(To see this, consider the set of 1-dimensional
slices through a clique \( K_v\) that is not a hole.  The holes in
these slices determine the location of the one vertex in \( S \cap K_v \) by parity.)
Also note that the holes in a slice of an independent set \(S\) correspond to
holes in \(H(S) \).

The following facts concerning the parity of the number of holes in certain segments are easy to check (using the observation that every element of $S$ in the interior of the segment accounts for exactly two non-holes).
\begin{lemma}
\label{lemparity} Let $S$ be an independent set in $C_{2 \ell_1+1}
\times C_{2 \ell_2 + 1}$.
\begin{itemize}
\item[(i)] If \( (x_1,y_1), (x_2,y_2) \in S \) where \(x_1 < x_2 \) and \( y_2 \in \{ y_1, y_1+1 \} \) then
\[ \left| \left\{ (x,y_1) \in H(S) : x \in [x_1, x_2] \right\} \right| \equiv x_2 - x_1 \mod 2. \]
\item[(ii)] If \( ( x_1, y_1 ) \in H(S) \) and \( (x_2,y_2) \in S \)
where \(x_1 < x_2 \) and \( y_2 \in \{ y_1, y_1+1 \} \) then
\[ \left| \left\{ (x,y_1) \in H(S) : x \in (x_1, x_2] \right\} \right| \equiv x_2 - x_1 \mod 2. \]
\end{itemize}
\end{lemma}


%
%\begin{corollary}
%\label{cornumvertstonumholes}
%If $S$ is an independent set in $C_{n_1} \times \dots \times C_{n_d}$ then $ H(S)
%\equiv (n_1\cdot\dots\cdot n_d) \bmod (2^d)$.
%\end{corollary}
%

% We might never use this.  Candidate for deletion.
%\begin{lemma}[Even-Even Lemma]
%\label{lemeveneven}
%Let $S$ be any independent set in $G := C_{n_1} \times \dots \times C_{n_d}$.
%Suppose that $(0,\dots,0)$ and $(x_1, \dots, x_d)$ are holes, with $x_i$ even
%for each $i \in [d]$.  Then there is another hole $(y_1, \dots, y_d)$ with
%$0 \leq y_i \leq x_d$ for each $i$.
%\end{lemma}

%\begin{proof}
%Let $\Gamma := \set{(v_1, \dots, v_d) \in V(G)\mid 0 \leq v_i \leq x_i \forall i \in [d]}$. Think of $\Gamma$ in terms of maximal cliques, not vertices.  Color a maximal clique in $\Gamma$ red if the sum of its coordinates is even, and blue of the sum of its coordinates is odd.  The holes $(0,0)$ and $(x_1, \dots, x_d)$ are both red.  Indeed, any clique $(u_1, \dots, u_n)$ with the
% property that, for each $i$, $u_i = 0$ or $u_i = x_i$ is red.  Furthermore, we see that the number of red cliques in $\Gamma$ exceed the number of blue cliques by 1, and two of these cliques -- $(0,0)$, and $(x_1, \dots, x_d)$ -- are already forced to be holes.  Of the remaining cliques in $\Gamma$, one more of these cliques is blue than red.  Any vertices in $S$ is a member of least as many
%red cliques  as blue cliques, and at most one member of any clique can be in $S$.  The result is that there must be a {\em blue} clique that does {\em not} contain any member of $S$, and is therefore a hole.
%\end{proof}



By a similar argument, if $S$ is an independent set in a product of two odd cycles
then every dual line
has an odd number of holes; in particular, every line has a hole.
If the size of the independent set is near the maximum then
most rows and most columns will have only one hole -- a few dual lines
may contain more than one hole.
\begin{definition}
\label{defbadness} Let $S$ be an independent set in $C_{2\ell_1+1}
\times C_{2\ell_2+1}$.  A dual line is {\bf $k$-bad} (or has
badness $k$) in $S$ if it has $2k+1$ holes in $S$.  A dual line is
{\bf full} if it is 0-bad.
\end{definition}

The following simple lemma will help prove that certain
independent sets are significantly below the maximum possible
size:

\begin{lemma}
\label{lemoneodd} Let $S$ be an independent set in $C_{2\ell_1+1}
\times C_{2\ell_2+1}$, and suppose that $(0,0)$ and $(2k+1,1)$ are
holes in $S$.   Suppose further that dual rows 0 and 1 are both full.
Then $S$ contains at most $k$ vertices in row 1.  Consequently,
$\abs{S} \leq \ell_1 \ell_2+k$.
\end{lemma}

\begin{proof}
%\begin{figure}
%\includegraphics{pics/basicpics/oneodd.pdf}
%\caption{\label{figoneodd} Lemma \ref{lemoneodd} with $k=4$.}
%\end{figure}
Suppose that $S$ contains $(x,1)$ for some $x \in [2k+3,2\ell_1]$. If $x$ is odd, Lemma~\ref{lemparity}(ii) applied to dual row $0$ and the hole $(0,0)$ implies another hole in that row. If $x$ is even, Lemma~\ref{lemparity}(ii) applied to dual row $1$ and the hole $(2k+1,1)$ implies another hole in that row. As we assume that both rows are full, we get a contradiction in either case, so $S$ contains no such vertices. Therefore, \( | \{x:
(x,1) \in S \}| \le k \). The final statement follows by noticing
that each dual row contains at most $\ell_1$ vertices from $S$, and applying
this observation to even-numbered dual rows from 2 through
$2\ell_2$.
\end{proof}

\subsection{Maximum independent sets in $C_{4m+1}^2$}
\label{subsec:maxind}

Baumert et al. \cite{BMRRST} characterized the maximum independent sets in $C_{4m+1}^2$. Their characterization may be stated in terms of the hole structure as follows.
\begin{lemma}[Baumert et al.]
\label{lemglobalregularity} Let \(S\) be a maximum independent set
in \( C_{4m+1}^2 \). Then $|S|=m(4m+1)$. Furthermore, there exist \(
\alpha
> 0 \) such that \( \alpha \mid m \), \( \epsilon \in \{\pm 1\} \)
and \( (t_1, t_2) \in {\mathbb Z}_{4m+1}^2 \) such that
\[ H(S) = (t_1, t_2) + \left< (2 \epsilon \alpha, 1) \right>,\]
where \( \left< ( 2 \epsilon \alpha, 1) \right> \) is the cyclic
subgroup generated by  \( ( 2 \epsilon \alpha, 1) \).
\end{lemma}

\begin{proof}
For the reader's convenience, we sketch the proof. Suppose that $S \subset C_{4m+1}^2$ is an independent set of size $m(4m+1)$. Then it has exactly one hole in every dual line. An inclusion-maximal subset of $S$ of the form $\{(x,y),(x+2,y),\ldots,(x+2j,y)\}$ will be called a thread of length $j+1$ in row $y$. The intersection of $S$ with any given row is the union of some number of threads.

Now, assume without loss of generality that the holes in dual rows $0$ and $1$ are at $(0,0)$ and $(2k,1)$ respectively, where $k>0$. Let us compare the thread structure of rows $0$ and $2$. It follows from Lemma~\ref{lemparity} that $\{(2,0),(4,0),\ldots,(2k,0)\}$ and $\{(1,2),(3,2),\ldots,(2k-1,2)\}$ are threads of length $k$ in these two rows, and the other threads in these two rows occupy the same horizontal positions. Thus, the thread structure of row $2$ is obtained from that of row $0$ by a unit shift of one thread. Now we consider the sequence of thread structures of rows $0,2,4,\ldots,4m,1,3,\ldots,4m-1,0$. By the above, each thread structure in this sequence is obtained from its predecessor by a unit shift of one thread. Given that we return to the original thread structure after $4m+1$ steps, it must be the case that in the whole process each thread is shifted to the position of the next thread (in some cyclic order on the threads). It follows that all threads in all rows have the same length, say $\alpha$, and all rows have the same number of threads, say $\beta$. A calculation gives $\alpha \beta =m$, and hence $\alpha \mid m$. We get the statement of the lemma by observing that the $k$ we started with must be equal to $\alpha$, and it must be the same for any choice of two adjacent dual rows.
\end{proof}

\noindent Note that the independent set generated by \( (2 \epsilon
\alpha, 1) \) is also generated by \( (1, - 2 \epsilon \beta\))
where \( \alpha \beta = m \).  So, the number of distinct (up to
isomorphism) maximum independent sets in \( C_{4m+1}^2 \) equals the
number of factorizations \(m = \alpha \beta\) where \( \alpha \le
\beta \).  The {\bf class} of a maximum independent set \(S\) in \(
C_{4m+1}^2 \) is the positive integer \( \alpha \le \sqrt{ m } \)
such that \(S\) is generated by \( (\pm 2\alpha,1) \) or \( (1, \pm
2\alpha) \).  The {\bf orientation} of \(S\) is determined by the
coordinate in which this generator has a 1.  So, if \( \alpha|m \),
\( \alpha \le \sqrt{m} \) and \( \gamma \in \{1,2\} \) then there
are (up to translations) two maximum independent sets in \(
C_{4m+1}^2\) of class \( \alpha \) and orientation \( \gamma \). An example of a maximum independent set in $C_{25}^2$ of class $2$ and orientation $1$ is given in Figure~1.

\begin{figure}[!t]
\begin{center}
\includegraphics{C25Picture.eps}
\end{center}
\caption{\label{figureon} A maximum independent set in $C_{25}^2$ of class $2$. The holes are marked with x's.}
\end{figure}

\section{Proof of Theorem~\ref{thm:easy}}
\label{sec:proofeasy}

Let \(S\) be an independent set in \(C_{8n+5}^3 \).  The
plane \( P_{x,d} \) is {\bf full} if \( S_{x,d} \) is a maximum
independent set in \( C_{8n+5}^2 \).  We begin with a simple
counting observation.
\begin{lemma}
\label{lemhavefullplanesbasic} Let $S$ be an independent set in
$C_{8n+5}^3$ so that $\abs{S} = \conjecturesize + k$. Then, for each
$d \in [3]$,  there are at least $2k$ distinct values of $x$ so that
$P_{x,d}$ is full.
\end{lemma}
\noindent In other words, if the size of the independent set
exceeds the best known lower bound then there are (at least two) full planes `in
each direction.'  Since each hole in \( C_{8n+5}^3 \) is a hole in
three dual planes, we can use Lemma~\ref{lemglobalregularity} to
relate the structure of intersecting full planes.  To express
this, we introduce notation that takes advantage of
Lemma~\ref{lemglobalregularity}. For each $i \in [3]$, let $e_i$
be the $i^{\rm th}$ standard basis vector.
\begin{definition}
\label{defpxij} Let $S$ be an independent set in $C_{8n+5}^3$, and
suppose that $P_{x,d}$ is full. Let $ \{i, j\} = [3] \setminus
\{d\}$. Then $\Delta_{x,d,i}$ is defined to be the unique even
integer (possibly negative) such that if $v = (x_1, x_2, x_3)$ is
a hole with $x_d = x$ then $v + e_i + \Delta_{x,d,i}e_j$ is also a
hole.
\end{definition}
\noindent Thus, $\D_{x,d,i}$ corresponds to $2\epsilon \alpha$ in the notation of Lemma~\ref{lemglobalregularity}. Note that \( \D_{x,d,i} \) is invertible in \( {\mathbb
Z}_{8n+5} \) and \( \D_{x,d,j} = \D_{x,d,i}^{-1} \).

Let
$S$ be an independent set in $C_{8n+5}^3$ such that $P_{0,d}$ is
full for each $d \in [3]$ and  let $(x,0,0)$ be a hole in $S$.
Then, it follows from Definition~\ref{defpxij} that we have
\begin{multline*}
(x,0,0) \in H(S) \  \Rightarrow \
(0,-\Delta_{0,3,1}x,0) \in H(S) \   \Rightarrow
\\ (0,0,-\Delta_{0,1,2}(-\Delta_{0,3,1}x)) \in H(S)
 \ \Rightarrow \
( -\Delta_{0,2,3}(-\Delta_{0,1,2}(-\Delta_{0,3,1}x)),0,0) \in H(S).
\end{multline*}
Since $P_{0,2}$ is full,  $(x,0,0)$ is the {\em only} hole in row 0 of
$S_{0,2}$, implying $x = -\Delta_{0,2,3}\Delta_{0,1,2}\Delta_{0,3,1}x $.
We have proved the following.
\begin{lemma}
\label{lemjumpproducts} If $S$ is an independent set in
$C_{8n+5}^3$, $P_{0,d}$ is full for each $d \in [3]$ and $(x,0,0)$
is a hole in $S$ then
\begin{equation}
\label{eq:circle}
-\Delta_{0,1,2}\Delta_{0,2,3}\Delta_{0,3,1}x = x.
\end{equation}
\end{lemma}
\noindent
In some very special cases this observation alone is
enough to determine the independence
number of \( C_{8n+5}^3 \).

Suppose, for example, that $8n+5$ and $2n+1$ are both prime (e.g.,
\(n=1,3,6\)) and that \(S\) is an independent set in \( C_{8n+5}^3
\) such that $\abs{S} > \conjecturesize$.  By Lemma
\ref{lemhavefullplanesbasic}, without loss of generality $P_{0,d}$
is full for all $d \in [3]$ and $(x,0,0)$ is a hole for some $x
\not= 0$ (here we use the existence of at least two full planes for $d=1$). Since $2n+1$ is prime, we also have $\Delta_{0,1,2},
\Delta_{0,2,3}, \Delta_{0,3,1} \in \set{\pm 2, \pm (4n+2)}$.  Then
Lemma~\ref{lemjumpproducts} implies
\begin{equation}
\label{eqn:bothprime}
8x = \pm x  \ \ \ \ \ \text{ or }  \ \ \ \ \
2x = \pm x.
\end{equation}
Since $8n+5$ is prime, $x$ is coprime to $8n+5$, and we have a contradiction in either case.

When $2n+1$ is not prime, we can no longer restrict
$\Delta_{x,i,j}$ to such a small set of values.  However, if
$8n+5$ is prime, we need only ensure that the coefficient of $x$
in \eqref{eq:circle} is not 1.  It turns out that this is the
case.
\begin{lemma}
\label{lemproductnot1}
If $x_i$ is an even divisor of $4n+2$ for
each $i \in [3]$ then $x_1x_2x_3 \not\equiv \pm 1 \bmod(8n+5)$.
\end{lemma}
\begin{proof}
Assume for the sake of contradiction that $x_1x_2x_3 \equiv \pm 1
\bmod(8n+5)$.  Without loss of generality, \( x_i >0 \) for each \(
i \in [3] \). Let $y_i = (8n+4)/x_i$ for $i \in [3]$. Then $y_i =
-(x_i)^{-1}$ in the ring $\mathbb{Z}_{8n+5}$, for each $i \in [3]$.
Furthermore, for each $i \in [3]$, $y_i$ is {\em also} an even
divisor of $4n+2$. Therefore, for any distinct $i,j,k \in [3]$, we
have:
\begin{eqnarray}
\label{eqntech1}
x_ix_j &\equiv& \pm y_k \bmod(8n+5), \\
\label{eqntech2}
x_k &\equiv& \pm y_iy_j \bmod(8n+5).
\end{eqnarray}
For each $i$, either $x_i \leq \sqrt{8n+5}$ or $y_i \leq
\sqrt{8n+5}$, so either two of the $x$'s or two of the $y$'s are
at most $\sqrt{8n+5}$.  If two of the $x$'s (say, $x_i$ and $x_j$)
are at most $\sqrt{8n+5}$ we have either $x_ix_j = y_k$ or $x_ix_j
= (8n+5) - y_k$.  The former case yields a contradiction because
$x_ix_j$, being the product of two even numbers, is a multiple of
four, whereas $y_k$, dividing $4n+2$, is not a multiple of four.
The latter case yields a contradiction because $(8n+5) - y_k$ is
odd, and $x_ix_j$ is even.  The case where two of the $y$'s are at
most $\sqrt{8n+5}$ is handled similarly, using \eqref{eqntech2}.
\end{proof}
\begin{corollary}
\label{corholefromplanenotprime} Let $S$ be an independent set in
$C_{8n+5}^3$, and assume that $P_{0,d}$ is full for each $d \in
[3]$, and $(x,0,0)$ is a hole such that \( x \neq 0 \).
Then $\gcd(x,8n+5) > 1$.
\end{corollary}
\begin{proof}
Lemma~\ref{lemjumpproducts} implies that
$x(1 + \Delta_{0,1,2}\Delta_{0,2,3}\Delta_{0,3,1}) = 0 $.
Lemma~\ref{lemproductnot1} implies that the second factor is not 0, thus
requiring that the first factor be a zero divisor in $\mathbb{Z}_{8n+5}$.
\end{proof}
\noindent Note that Theorem~\ref{thm:easy} follows from Lemma~\ref{lemhavefullplanesbasic} and Corollary~\ref{corholefromplanenotprime}.

\section{Proof of Theorem~\ref{thm:main}}
\label{sec:proofits}

So far, our techniques only utilize the positions of holes in full
planes, and operate by showing that there is no way to place these
holes in a manner consistent with Lemma~\ref{lemglobalregularity}.
These techniques alone are insufficient when $8n+5$ is not prime --
for example, in $C_{21}^3$ it is possible, for each $d \in [3]$, to
have two values of $x$ so that $P_{x,d}$ is full, and place the
holes in all of the full $P_{x,d}$ in a seemingly consistent manner.
To prove Theorem~\ref{thm:main}, then, we will look also at planes that are just short of being full. It turns out that the structure of such planes is essentially governed by Lemma~\ref{lemglobalregularity} as well, with certain types of modifications allowed. Moreover, when such a plane lies right next to a full plane, then (subject to certain provisions) the maximum independent sets underlying the two of them must be of the same class and orientation, which in turn constrain the class and orientation of full planes in the other directions. Very roughly speaking, these considerations will allow us to derive a contradiction similar to that obtained in the previous section, without assuming the primality of $8n+5$, but we will need a larger number of full planes in each direction (hence the $+2$ in the upper bound that we establish).

Motivated by this discussion, we introduce the following terminology. Let $S$ be an independent set in $C_{8n+5}^3$. To each full plane $P_{x,d}$ we assign a class and orientation, namely those of the maximum independent set $S_{x,d}$. The plane $P_{x,d}$ is {\bf almost full} if $|S_{x,d}|=\alpha(C_{8n+5}^2)-1$. The plane \(
P_{x,d} \) is {\bf good} if \( P_{x,d} \) is full and \( P_{x-1,d}
\) or \( P_{x+1,d} \) is full or almost full; it is {\bf solid} if
\( P_{x,d} \) is full and \( P_{x-1,d} \) and \( P_{x+1,d} \) are
both full or almost full.

In the proof of Theorem~\ref{thm:main}, we consider a large independent set $S$ in $C_{8n+5}^3$, and gradually establish facts about the number of good planes in each direction and their classes, leading to a contradiction in the end. To facilitate the understanding of the structure of the proof, we break it into several steps. The title of each subsection states, rather informally, what is established in that step.

\subsection{There are many good planes in each direction}
\label{many}

Here we prove a refinement of Lemma~\ref{lemhavefullplanesbasic}, guaranteeing planes that are not only full but actually good, and showing that their number must be even larger in certain circumstances (namely, if some planes contain independent sets that are significantly smaller than the maximum). The following function measures the size of the independent sets in the various planes, normalized so that almost full planes get the value zero.
For \(d \in [3] \) define \(
\delta_{S,d} : {\mathbb Z}_{8n+5} \to {\mathbb Z} \) by
\[ \d_d(x) = \delta_{S,d}(x) = \abs{S_{x,d}} - \alpha( C_{8n+5}^2) + 1. \]
\begin{lemma}
\label{lemnumfullplanes} Let \(S\) be an independent set in \(
C_{8n+5}^3 \) such that \( \abs{S} = \conjecturesize + k \), and
let \( d \in [3]\). Then the number of good planes \( P_{x,d} \)
is at least
%positive streaks is at
%least
%\[ 2k + \paren{\sum_{ x \in {\mathbb Z}_{8n+5}} \delta^\prime_d(x)}
% -  \abs{\set{ x \in {\mathbb Z}_{8n+5} \mid \set{x}
%\text{ is a singleton}}}. \]
%Furthermore, the number of good planes
%\( S_{x,d} \) is at least
\[ 2k + \sum_{ x: \d_d(x) \le -2} (-\delta_d(x)-1)
+ 1_{ \exists x \text{ such that } \d_d(x) < 0}. \]
\end{lemma}
\noindent Before proving this lemma we state some definitions that
will also be used below. Let a {\bf \( \delta_d\)-streak} be a
maximal interval \(I\) in \( {\mathbb Z}_{8n+5} \) such that \(
\delta_d(x) \neq 0 \) for all \( x \in I \), no two consecutive
\(x,y \in I \) have \( \delta_d(x) = \delta_d(y) = 1 \), and no
two consecutive \(x,y \in I \) have \( \delta_d(x), \delta_d(y) <
0 \).
%If \( X \subseteq {\mathbb Z}_{8n+5} \) then we write
%\[ \delta_d(X) = \sum_{x \in X} \delta_d(x). \]
A streak \(I\) is a {\bf singleton} if \( \abs{I} = 1 \) and \(
\d_d(x) = 1 \) for \(x \in I\), and a streak \(I = [a,b]\) is {\bf
positive} if \( \abs{I} > 1 \) and \( \d_d(a) = \d_d(b) = 1 \).
Note that the set of streaks forms a partition of the set of \(x
\in {\mathbb Z}_{8n+5} \) such that \( \delta_d(x) \neq 0 \). Each
singleton streak corresponds to a solid plane. Each positive
streak begins and ends with a good plane. Finally, note that
streaks that are neither positive nor singletons may have good
planes at one end.
\begin{proof}[Proof of Lemma~\ref{lemnumfullplanes}]
Let \(s \) be the number of singleton streaks and \( p \) be the
number of positive streaks in the sequence \( \delta_d(x) \).
Since \( \sum_{x \in {\mathbb Z}_{8n+5}} \abs{S_{x,d}} = 2
\abs{S}\), we have
\begin{equation*}
\begin{split}
2k = \sum_{x \in {\mathbb Z}_{8n+5}} \delta_d(x) \le s + p +
\sum_{x: \d_d(x) \le -2} (\delta_d(x)+1).
\end{split}
\end{equation*}
Note that the number of good planes is at least \(s+2p\).  We get
the statement of the lemma by noting that if there is an \(x\)
such that \( \d_d(x) <0 \) then there is at least one streak that
is not a singleton.  This streak gives an additional good plane
(beyond the accounting already presented).
\end{proof}
%Now, we turn to facts that will apply in cases where we make
%specific assumptions about the structure of $S$.
\noindent Define
\begin{eqnarray*}
X = X_S &=& \set{x \in \mathbb{Z}_{8n+5} \mid P_{x,1} \mbox{ is good}}, \\
Y = Y_S &=& \set{y \in \mathbb{Z}_{8n+5} \mid P_{y,2} \mbox{ is good}}, \\
Z = Z_S &=& \set{z \in \mathbb{Z}_{8n+5} \mid P_{z,3} \mbox{ is
good}}.
\end{eqnarray*}
Note that Lemma~\ref{lemnumfullplanes} implies that if \( |S| \ge
t_n + 3 \) then each of these sets has cardinality at least 6.

\subsection{A good plane of class $1$ implies a high ratio between the numbers of good planes in the other directions}
\label{subsec:ratio}

Supposing that there is a good plane of class $1$, we apply here Lemma~\ref{lemoneodd} to show that some planes in one of the other directions are significantly underused, and hence by Lemma~\ref{lemnumfullplanes} the number of good planes in that direction must be very large to compensate for that.

\begin{lemma}
\label{lem:ron} Let $S$ be an independent set in $C_{8n+5}^3$ such
that $|S| \ge t_n+3$. If \( P_{0,1} \) is good and \( \D_{0,1,2} =
4n+2 \) then
\begin{equation}
\label{eq:bigY} |Y| \ge (n-1)( |Z|-4 ) + 7.
\end{equation}
\end{lemma}
\noindent Before proving Lemma~\ref{lem:ron}, we make (as usual)
some preliminary definitions and observations.  Let $f_S^+, f_S^-: Z
\to \mathbb{Z}_{8n+5}$ be defined by
\begin{eqnarray*}
f^+(z) = f_S^+(z) &=& -2z + \Delta_{z,3,1}, \\
f^-(z) = f_S^-(z) &=& -2z - \Delta_{z,3,1}.
\end{eqnarray*}
Define $Y^+=Y_S^+$ to be the range of $f_S^+$ and $Y^-=Y_S^-$ to be
the range of $f_S^-$.  Note that if $S$ is an independent set so
that $P_{0,1}$ is full with $\Delta_{0,1,2} = 4n+2$, $(0,0,0)$ is a
hole, and $z \in Z$ then $(0,-2z,z)$, $(1,f_S^+(z), z)$, and
$(-1,f_S^-(z), z)$ are holes.
\begin{lemma}
\label{cornonsquaresgivefullplanes} Suppose $P_{0,1}$ is full so
that $\Delta_{0,1,2} = 4n+2$, $(0,0,0)$ is a hole, and $z \in Z$. If
column~1 is full in $P_{f^+(z),2}$ then:
\begin{eqnarray*}
\abs{S_{f^+(z),2}} &\leq& (2n+1)(8n+4) +  \frac{\abs{\Delta_{z,3,1}} - 2}{4} \\
&=& \alpha(C_{8n+5}^2) - ((2n+1) - (\abs{\Delta_{z,3,1}} - 2)/4).
\end{eqnarray*}
In particular, $\abs{S_{f^+(z),2}} \leq \alpha(C_{8n+5}^2) - (n+1)$.
The analogous result holds for $S_{f^-(z),2}$, if column~-1 is full
in $P_{f^-(z),2}$.
\end{lemma}
\begin{proof}
As noted above, $(1,f^+(z),z)$ is a hole. On the other hand, by the definition of $f^+$ and
$\Delta_{0,1,2}$, $(0,f^+(z), z - \Delta_{z,3,1}/2)$ is also a
hole.  Noting that $\abs{\Delta_{z,3,1}/2}$ is odd, we then apply
Lemma~\ref{lemoneodd} to $P_{f^+(z),2}$ to get the first inequality. The second one follows from $\abs{\Delta_{z,3,1}} \leq 4n+2$. The proof for $S_{f^-(z),2}$ is similar.
\end{proof}
\begin{lemma}
\label{lemnotallbad} Suppose $P_{0,1}$ is full so that
$\Delta_{0,1,2}=4n+2$, and $(0,0,0)$ is a hole. Let $y \in Y^+$, and
suppose that column 1 is $k$-bad in $P_{y,2}$. Then:
\begin{displaymath}
\abs{\set{z \in Z \mid f^+(z) = y}} \leq k+1.
\end{displaymath}
A similar result holds for column~-1, using $f^-$ instead of $f^+$.
\end{lemma}
\begin{proof}
Let $z_1, z_2 \in (f^+)^{-1}(\set{y})$.  We have $-2z_1 +
\Delta_{z_1,3,1} = -2z_2 + \Delta_{z_2,3,1}$, whence $z_2 - z_1 =
(\Delta_{z_2,3,1} - \Delta_{z_1,3,1})/2$. Now, $\Delta_{z_2,3,1}$
and $\Delta_{z_1,3,1}$ are both congruent to 2 modulo 4, so it
follows that $z_2 - z_1$ is even.   We order the elements $z_1,
\dots, z_j$ of $(f^+)^{-1}(\set{y})$ so that $z_1 \leq \dots \leq
z_j$ and $z_{i+1} - z_{i}$ is even for \( i =1, \dots, j-1 \). As noted above, $(1,y,z_i)$ is a hole for each $i=1,\ldots,j$.
Consequently, by Lemma \ref{lemparity}, each interval $[z_{i}, z_{i
+ 1}]$ in column $1$ of $P_{y,2}$ contains an additional hole. Since this column is $k$-bad, we get $2j-1 \le 2k+1$, or $j \le k+1$.
\end{proof}
\noindent
\begin{proof}[Proof of Lemma~\ref{lem:ron}]
We assume without loss of generality that $(0,0,0)$ is a hole and
that $P_{1,1}$ is full or almost full. Since $P_{1,1}$ has at most two
column badnesses, it follows from Lemma~\ref{lemnotallbad} that
there are at most four $z \in Z$ such that $f^+(z)$ has the property
that column 1 is bad in $P_{f^+(z),2}$ (note that column $1$ in $P_{f^+(z),2}$ is column $f^+(z)$ in $P_{1,1}$).  Let:
\begin{displaymath}
Z^* := \set{z \in Z \mid \mbox{ column } 1 \mbox{ is full in }
P_{f^+(z),2}}.
\end{displaymath}
We have \( |Z^*| \ge |Z| - 4 \). Note that $f^+$, when restricted
to $Z^*$, is one-to-one. Lemma~\ref{cornonsquaresgivefullplanes}
then implies
\[ \sum_{y : \d_2(y) \le -2 } (-\d_2(y)-1) \ge (n-1)|Z^*| \ge (n-1)( |Z|-4). \]
Appealing to Lemma~\ref{lemnumfullplanes}, we have (\ref{eq:bigY}).
\end{proof}

\subsection{Handling the case $2n+1$ prime}
\label{subsec:prime}

If \( 2n+1 \) is prime and $S$ is an independent set in $C_{8n+5}^3$ so that $|S| \ge t_n+3$, then
every full plane is of class 1 and we get three instances of
(\ref{eq:bigY}) (one in each `direction'). Applying two of these in
succession we have
\[ \max\{ |X|, |Y|, |Z| \} \ge (n-1)(2n+1) + 7. \]
For $n \ge 5$ this is a contradiction, because the lower bound exceeds $8n+5$. As we may assume, by Theorem~\ref{thm:easy}, that $8n+5$ is composite, the only case left is $n=2$. In this case, the lower bound gives $12$ good planes in some direction. Applying Corollary~\ref{corholefromplanenotprime} with some fixed full planes in the other two directions and each of these $12$ full planes, we get a contradiction because $\mathbb{Z}_{21}$ has only $9$ elements that are divisible by $3$ or $7$.

Thus, we may assume from now on that $2n+1$ and $8n+5$ are both composite. We will not use this assumption as such, but only its consequence that $n \ge 10$.

\subsection{Many good planes of classes $> 1$ in different directions can fit together only if they are of the same class (with few exceptions)}
\label{subsec:same}


Now we turn to the good planes that are not of class 1.  In order
to explore the relationships among them, we define an auxiliary
graph.
\begin{definition}
The tripartite directed graph $G_S$ is defined as follows. For
each $d \in [3]$, let
\begin{displaymath}
V_{d} := \set{x \in \mathbb{Z}_{8n+5} \mid P_{x,d} \mbox{ is good
and not of class } 1}.
\end{displaymath}
Set $V(G_S) := \bigcup_{d=1}^3 V_d$.   For any $x_i$ in $V_i$ and
$x_j$ in $V_j$, with $i \not= j$, let $(x_i,x_j)$ be an arc if
$\abs{\Delta_{x_i, i, j}} \leq \abs{\Delta_{x_j,j,i}}$.
\end{definition}
\noindent The relevant feature of $G_S$ is that each node has a large
out-degree to each of the other parts of the tripartition.
\begin{lemma}
\label{lemoutdegreebig} Let $S$ be an independent set in
$C_{8n+5}^3$, $n \ge 8$, such that $|S| \ge t_n+3$. Let $x \in V_i$,
and $j \in [3]$ with $j \not= i$. Then there are at most three $y
\in V_j$ so that $(x,y)$ is not an arc in $G_S$. Furthermore, if
there is an $A \subseteq V_j$ so that $\abs{A} = 3$ and $(x,y)$ is
not an arc for all $y \in A$ then there is a $y \in A$ so that $y +
1 \in A$.
\end{lemma}

\noindent The proof of Lemma~\ref{lemoutdegreebig} is based on a stability result for almost maximum independent sets in $C_{4m+1}^2$ and some fine machinery applying this result to independent sets in $C_{8n+5}^3$, $n \ge 8$, all developed in the original, long version of this paper. We refer the interested reader to that version, and give here only a very rough idea. We consider a full plane, say $P_{0,1}$, and an adjacent almost full plane, say $P_{1,1}$. The structure of $S_{1,1}$ must be a slight modification of the well-understood structure given in Lemma~\ref{lemglobalregularity}. The modification may significantly affect only a few dual columns of $P_{1,1}$; their numbers are collected in the exceptional set $A$ in the statement of the lemma. For any full plane $P_{y,2}$ whose intersection with $P_{1,1}$ is not one of the exceptional columns, we have a good grasp of how its $0$ and $1$ columns look like (as they are in $P_{0,1}$ and $P_{1,1}$). This allows us to identify enough of the structure of $S_{y,2}$ to deduce that $|\Delta_{y,2,1}| \ge |\Delta_{0,1,2}|$. For these reconstruction arguments to work, we need to rule out planes of class $1$ and small values of $n$.
\begin{corollary}
\label{cormostareequal} Let $S$ be an independent set in $C_{8n+5}^3$, $n \ge 8$, such that $|S| \ge t_n+3$. Let $i,j \in [3]$, $i \ne j$, satisfy $|V_i| \ge 4$, $|V_j| \ge 4$. Then there exist subsets $U_i \subseteq V_i$ and $U_j \subseteq V_j$ with $|U_i| \ge |V_i|-3$, $|U_j| \ge |V_j|-3$, so that the numbers $|\Delta_{x_i,i,j}|$ for $x_i \in U_i$ and $|\Delta_{x_j,j,i}|$ for $x_j \in U_j$ are all equal.
\end{corollary}
\begin{proof}
Consider the induced directed graph $G_S[V_i \cup V_j]$. Within any strongly connected component of it, the desired equalities hold by the definition of the arc set. One of these components, say $C$, has no arcs to the other components. It follows from Lemma~\ref{lemoutdegreebig} that $|C \cap V_i| \ge |V_i|-3$ and $|C \cap V_j| \ge |V_j|-3$.
\end{proof}

\subsection{There is a good plane of class $1$ in some direction}
\label{subsec:class1}

Here we use the previous step to get a contradiction if there are at least $5$ good planes of classes $> 1$ in each direction. Since the total number of good planes in each direction is at least $6$, it will follow that there is a good plane of class $1$ (in fact, two of them) in some direction.
\begin{lemma}
\label{lemGsnotmanyverts} Let $S$ be an independent set in $C_{8n+5}^3$, $n \ge 8$, such that $|S| \ge t_n+3$. Then there exists a $d \in [3]$ so that
$\abs{V_d} \leq 4$.
\end{lemma}
\begin{proof}
An observation that we use repeatedly below is that if plane
$P_{x,d}$ is full and $\{i,j\}=[3] \setminus \{d\}$ then
$\Delta_{x,d,i} \Delta_{x,d,j} = -(8n+4)$, and therefore
$|\Delta_{x,d,i}| \le \sqrt{8n+4}$ if and only if $|\Delta_{x,d,j}|
\ge \sqrt{8n+4}$. We start with a technical claim similar to
Lemma~\ref{lemproductnot1}.
\begin{cl}
%\label{lemnotsqrt}
If $P_{0,i}$ is full for each $i$ and $\Delta_{0,i,j} \in \set{\pm
\sqrt{8n+4}}$ for all well-defined choices of $i$ and $j$, then
$(0,0,0)$ is a hole.
\end{cl}
\begin{proof}
By Lemma~\ref{lemjumpproducts}, it is sufficient to show that for
all $n$, $\pm \sqrt{8n+4}^3 \pm 1$ is coprime to $8n+5$. First,
notice that $\sqrt{8n+4}^2 = 8n+4 \equiv -1 \bmod (8n+5)$.
Therefore, it is sufficient to show that $\pm \sqrt{8n+4} \pm 1$
is coprime to $8n+5$. We have $(\sqrt{8n+4} + 1)(\sqrt{8n+4} - 1)
= 8n+3$, which is coprime to $8n+5$. Therefore, $\sqrt{8n+4} + 1$
and $\sqrt{8n+4} - 1$ are coprime to $8n+5$.
\end{proof}




Assume for the sake of contradiction that $\abs{V_d} \geq 5$ for
each $d \in [3]$.

\vskip3mm

\noindent {\bf Case 1: For all $d \in [3]$, $x \in V_d$ implies
$x+1 \notin V_d$.}

\begin{quote}
By Lemma \ref{lemoutdegreebig}, each vertex has arcs leading to
all but at most two vertices in each of the other $V_i$.

Suppose, without loss of generality, that there are three $x \in
V_1$ so that $\abs{\Delta_{x,1,2}} \leq \sqrt{8n+4}$, and let
$T_1$ be the set of all such nodes in $V_{1}$.

Lemma \ref{lemoutdegreebig} implies that each $y \in V_{2}$ is the
tail of some arc directed into $T_1$.   Thus, for each $y \in
V_{2}$, $\abs{\Delta_{y,2,1}} \leq \sqrt{8n+4}$.   Let $x_0 \in
T_1$.  Then there are at least three $z \in V_{3}$ so that
$(x_0,z)$ is an arc -- let $T_3$ be any set of exactly three such
$z$.  Lemma \ref{lemoutdegreebig} implies that for each $y \in
V_{2}$ there is a $z \in T_3$ so that $(y,z)$ is an arc.  There
are thus five arcs from $V_{2}$ to $T_3$, each from a different
vertex in $V_{2}$.  Then there is a $z_0 \in T_3$ so that there are
two $y \in V_{2}$ so that $(y,z_0)$ is an arc -- let $T_2$ be the
set of all $y \in V_{2}$ so that $(y,z_0)$ is an arc.

We have $\abs{\Delta_{x_0,1,3}} \geq \sqrt{8n+4}$ and
$\abs{\Delta_{y,2,3}} \geq \sqrt{8n+4}$ for each $y \in V_{2}$.
These imply, respectively, that $\abs{\Delta_{z_0,3,1}} \geq
\sqrt{8n+4}$ and $\abs{\Delta_{z_0,3,2}} \geq \sqrt{8n+4}$. Thus,
$\abs{\Delta_{z_0,3,2}} = \abs{\Delta_{z_0,3,1}} = \sqrt{8n+4}$.
It then follows that $ \abs{\Delta_{x_0,1,3}} =
\abs{\Delta_{y,2,3}} = \sqrt{8n+4}$ for each $y \in T_2$.  This
contradicts the claim -- one of the intersections of three planes
\( P_{x_0,1} \cap P_{y,2} \cap P_{z_0,3} \) such that \( y \in T_2
\) is not a hole.
\end{quote}

\noindent {\bf Case 2: There is $d \in [3]$ and $x \in
\mathbb{Z}_{8n+5}$ so that $x, x+1 \in V_d$.}
\begin{quote}
The proof in this case is based on similar ideas, but requires additional machinery developed in the original version of this paper. The interested reader is again referred to that version.
\end{quote}
\end{proof}
\noindent We henceforth assume, without loss of generality, that \( |V_1| \le 4 \), \( P_{0,1} \) is
good and \( \D_{0,1,2} = 4n+2 \).

\subsection{All good planes in the other two directions are of classes $> 1$}
\label{subsec:notclass1}

Here we consider an independent set $S$ in $C_{8n+5}^3$, $n \ge 10$, such that $|S| \ge t_n+3$, and the assumptions made at the end of the previous subsection hold. Then inequality (\ref{eq:bigY}) applies and gives severe restrictions on the cardinalities of $Y$ and $Z$. The general idea is that we cannot afford a good plane of class $1$ in another direction, because then the combined restrictions would become untenable. We proceed with several observations, and keep track of the cardinality restrictions that they imply.
\begin{lemma}
\label{lemadjacentynotfull} There is no $y$ so that $P_{y,2}$ and
$P_{y+1,2}$ are both full.
\end{lemma}

\begin{proof}
Assume for the sake of contradiction that there exists $y$ so that
$P_{y,2}$ and $P_{y+1,2}$ are full.  Choose $z_0$ so that
$(0,y,z_0)$ is a hole. Then $(0,y+1,z_0 + (4n+2))$ is a hole, as
is $((4n+2)\Delta_{y,2,3},y, z_0 + (4n+2))$. Since $P_{y,2}$ and
$P_{y+1,2}$ are both full, rows $y$ and $y+1$ are full in $P_{z_0
+ (4n+2),3}$. Furthermore, \( (4n+2) \D_{y,2,3} \) is a divisor of
\( 2n+1 \). Lemmas~\ref{lemoneodd}~and~\ref{lemnumfullplanes}
imply that $\abs{Z} \geq n + 6 \geq 16$. This in turn implies, by (\ref{eq:bigY}), that $|Y| \ge 12n-5 > 8n+5$, a contradiction.
\end{proof}
\noindent
It follows from Lemma~\ref{lemadjacentynotfull} and (\ref{eq:bigY}) that we have
\begin{equation}
\label{eq:tight1} 2n+5 \le |Y| \le 4n + 2 \ \ \ \ \ \ \text{ and }
\ \ \ \ \ \  6 \le |Z| \le 7.
\end{equation}
(Note that we have proved $\abs{S} \leq \conjecturesize + 3$.)

We now consider \( X \).
\begin{lemma}
\label{lem2notadjtofull} None of the good planes $P_{x,1}$ of class $1$ is solid.
%Furthermore, neither $P_{1,1}$ nor $P_{-1,1}$ is full.
\end{lemma}
\begin{proof}
%First, assume for the sake of contradiction that \( P_{1,1} \) is
%full.  Then we have \( Z^* = Z \).  It then follows (as in the
%proof of (\ref{eq:bigY})) that we have \( |Y| \ge (n-1)|Z| + 7 \ge
%6n +1 \).  This contradicts (\ref{eq:tight1}).

Suppose for the sake of contradiction that \( P_{0,1} \) is solid and $(0,0,0)$ is a hole (without loss of generality).
Since $P_{1,1}$ and $P_{-1,1}$ each have at most two column
badnesses, Lemma~\ref{lemnotallbad} implies that there are at least
two $y \in Y^+$ such that column $y$ is full in $P_{1,1}$
(equivalently column $1$ is full in $P_{y,2}$) and there are at
least two $y \in Y^-$ such that column $y$ is full in $P_{-1,1}$.

We first show that no $ y \in Y^+ \cap Y^-$ gives a full column in
both $P_{-1,1}$ and $P_{1,1}$. Suppose that there is $y \in Y^+ \cap
Y^-$ so that both columns $-1$ and $1$ are full in $P_{y,2}$. Then
the proof of Lemma~\ref{cornonsquaresgivefullplanes} implies that
there exist $z$, $a$ and $b$ so that $P_{y,2}$ has holes at $(-1,z +
a)$, $(0,z)$, and $(1,z+ b)$, where $a$ and $b$ are odd numbers in
the interval $[-(2n+1),2n+1]$. These are the only holes in these three columns, and trying to place the vertices of $S_{y,2}$ leads to a
contradiction by parity (i.e., Lemma \ref{lemparity}).

Therefore, there are at least four $y \in Y^+ \cup Y^-$ that have
the property that column 1 or column $-1$ is full in $P_{y,2}$.
It follows that there are at least four values of \(y\) such that \(
\d_2(y) \le -n \).  So, we have \( |Y| \ge 4(n-1) + 7 \).  This
contradicts (\ref{eq:tight1}).
\end{proof}
\noindent Let \(s_X\) and \(p_X\) be the numbers of singleton and
positive streaks, respectively, in the sequence \( \d_1(x) \).
Lemma~\ref{lem2notadjtofull} implies that all good planes of class
1 in \(X\) are in streaks of length at least 2.  Since we assume
\( |V_1| \le 4 \), we have \( s_X \le 4 \).  Since \( p_X + s_X
\ge 6 \) we have \( p_X \ge 2 \) and
\begin{equation}
\label{eq:Xbig}
 |X| \ge 8.
\end{equation}

Now we consider the classes of the good planes in \(Y\) and \(Z\).
\begin{lemma}
\label{lemnotclass1} We have $Y=V_2$ and $Z=V_3$.
\end{lemma}
\begin{proof}
We can immediately conclude that \(Z= V_3 \): If \(Z\) contains a
plane of class 1 then `rotating' the argument above we have \( |Y|
\le 7 \) or \(|X| \le 7\), which is not the case. Next, suppose \(Y\)
contains a plane $P_{y,2}$ of class 1. Then we may assume that $\Delta_{y,2,1}=4n+2$ (if it has the other orientation then the argument above yields $|X| \le 7$, which is not the case). Since \( Z = V_3 \), we have \( |
\D_{z,3,2}| \le \frac{ 4n+2}{3} \) for all \(z \in Z \). So, it
follows from Lemmas~\ref{cornonsquaresgivefullplanes} and \ref{lemnotallbad} that there are
two values of \(x\) such that \( \d_1(x) \le - \frac{5n+1}{3} \).
Thus, we have
\[ s_X + p_X \ge 2\left( \frac{ 5n+1}{3}-1\right) + 6 = \frac{10n+14}{3}. \]
On the other hand, a simple volume argument gives \( p_X \le
\frac{ 8n+5 }{3} \), and therefore
\[ s_X + p_X \le \frac{ 8n+17}{3}. \]
We have a contradiction.  Therefore \( Y=V_2 \).
\end{proof}

\subsection{This configuration is impossible}
\label{subsec:impossible}

Based on all the information we have on the number and classes of good planes, and using Corollary~\ref{cormostareequal}, we will reach a contradiction. Indeed, we know by (\ref{eq:tight1}) and Lemma~\ref{lemnotclass1} that $|V_2| \ge 2n+5 \ge 25$ and $|V_3| \ge 6$. Applying Corollary~\ref{cormostareequal} to $V_2$ and $V_3$, and picking four elements $y_1,y_2,y_3,y_4$ of the set $U_2$ and an element $z$ of $U_3$, we have
\[ \abs{\D_{z,3,2}} =  \abs{\D_{y_1,2,3}} =  \abs{\D_{y_2,2,3}}
=  \abs{\D_{y_3,2,3}} =  \abs{\D_{y_4,2,3}}. \] Let \(
(0,y^\prime,z) \) be the unique hole in the intersection of \(
P_{0,1} \) and \( P_{z,3} \). Lemma~\ref{lemjumpproducts} implies
\[  0 = ( \D_{y_i,2,3} \D_{z,3,1} \D_{0,1,2} + 1 ) ( y^\prime - y_i) = ( \pm(4n+2) + 1) (y^\prime - y_i) \] for $i=1,2,3,4$. But there are at most three values of $y_i$ that satisfy this condition, because \( 4n+3 \) is co-prime to \(8n+5\), and
\[ (4n+1)(y^\prime - y_i) = 0 \ \ \ \ \ \Rightarrow \ \ \ \ \
3( y^\prime - y_i ) = 0. \] This contradiction completes the proof of Theorem~\ref{thm:main}.

%\vspace{15pt}

%\noindent {\bf Acknowledgement}

%\vspace{10pt}

%We thank two anonymous referees for their suggestions regarding the presentati%on.

%
%so that, for at least 23 $y \in V_{2}$,
%$\abs{\Delta_{y,2,3}} = \beta$, and, for at least 3 $z \in V_{3}$,
%$\abs{\Delta_{z,3,2}} = \beta$.
%
%
%It is easy to see that we can choose
%$y_1 \not= y_2 \in V_{2}$ so that $\Delta_{y_1,2,3} = \Delta_{y_2,2,3}
%= \pm \beta$ (indeed, we can choose a subset of $V_{2}$ of size at least
%$\abs{V_{2}}/2$ with this property).    We note then that, for all $x$,
%if $(x,y_1,z^{\prime})$ is a hole then $(x,y_2 - y_1, z^{\prime} - (y_2 - y_1)/2)$
%is a hole.   Further, if $(x,y_1, z)$ is a hole and $(x + \Delta x, y_2, z)$ is a
%hole, then $\Delta x = (y_2 - y_1)\Delta_{z,3,2}$.  We therefore have:
%
%\begin{displaymath}
%(y_2 - y_1)\Delta_{z,3,2}\Delta_{y_2,2,1} = \pm \frac{y_2 - y_1}{2}.
%\end{displaymath}
%Since $\Delta_{y,2,1} = \pm (\Delta_{z,3,2})^{-1}$, we have:
%\begin{displaymath}
%(y_2 - y-1) = \pm \frac{y_2 - y_1}{2},
%\end{displaymath}
%which implies that $3(y_2 - y_1) \equiv 0 \bmod (8n+5)$, so at most three $y \in V_{2}$ can all have the same $\Delta_{y,2,3}$, but this contradicts the ability of finding a set of size $\abs{V_{2}}/2 \geq 11$ with this property.


%
%\vspace{10pt}
%
%\noindent \textbf{Acknowledgment.}






\begin{thebibliography}{99}


\bibitem{noga1} N. Alon, The Shannon capacity of a union,
{\em Combinatorica} {\bf 18} (1998), 301-310.


\bibitem{al2} N. Alon and E. Lubetzky,
Privileged users in zero-error transmission
over a noisy channel, {\em Combinatorica} {\bf 27} (2007), 737-743.

\bibitem{BMRRST} L. Baumert, R. McEliece, E. Rodemich, H. Rumsey,
R. Stanley and H. Taylor, A Combinatorial Packing Problem,
{\em Computers in Algebra
and Number Theory}, Providence,
American Mathematical Society; 1971, pp. 97-108.

\bibitem{B}
C. Berge, {\em Graphs and Hypergraphs.} Amsterdam and London,
North-Holland; New York, American Elsevier, 1973.


\bibitem{Bo2}  T. Bohman, A limit theorem for the Shannon
capacities of odd cycles II, {\em Proceedings of the AMS} {\bf 133} (2005), 537-543.


\bibitem{withron} T. Bohman and R. Holzman, A nontrivial lower
bound on the Shannon capacities of the
complements of odd cycles,
{\em IEEE Transactions on Information
Theory} {\bf 49} (2003), 721-722.

\bibitem{bhn} T. Bohman, R. Holzman and V. Natarajan, Maximum independent sets in certain powers of odd cycles, {\em The Electronic Journal of Combinatorics} {\bf 16} (2009), \#N26.

%
%\bibitem{BRT}
%T. Bohman, M. Ruszink\'o, L. Thoma, Shannon capacity of large odd
%cycles, {\em Proceedings of the 2000 IEEE International Symposium on
%Information Theory}, June 25-30, Sorrento, Italy, p. 179.
%

\bibitem{crst}
M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The
strong perfect graph theorem, {\em Annals of Math} {\bf 164} (2006),
51-229.

\bibitem{cgr}
B. Codenotti, I. Gerace and G. Resta, Some remarks on the Shannon capacity of odd cycles, {\em Ars Combin.} {\bf 66} (2003), 243-257.

\bibitem{gerard}
G. Cornu\'ejols,  The strong perfect graph theorem, {\em Optima}
{\bf 70} (2003), 2-6.



\bibitem{hae}
W. Haemers,
On some problems of Lov\'asz concerning the Shannon
capacity of a graph,
{\em IEEE Transactions on Information Theory}
{\bf 25} (1979), 231-232.
%
%\bibitem{Ha2}
%W. Haemers,
%An upper bound for the Shannon capacity of a graph,
%{\em Colloquia Mathematica Societatis J\'anos Bolyai, 25: Algebraic Methods
%in Graph Theory,} Szeged (Hungary), 1978, 267-272.
%

\bibitem{H}
R. S. Hales, Numerical invariants and the strong product of
graphs, {\em Journal of Combinatorial Theory -- B} {\bf 15}
(1973), 146-155.

\bibitem{stabkm}
P. Keevash and D. Mubayi, Stability theorems for cancellative
hypergraphs, {\em Journal of Combinatorial Theory -- B} {\bf 92}
(2004), 163--175.

\bibitem{stabks}
P. Keevash and B. Sudakov, The Tur\'an number of the Fano plane,
{\em Combinatorica} {\bf 25} (2005), 561-574.

\bibitem{KO}
J. K\"orner and A. Orlitsky, Zero-error information theory, {\em
IEEE Transactions on Information Theory} {\bf 44} (1998),
2207-2229.

\bibitem{L}
L.~Lov\'asz, On the Shannon capacity of a graph, {\em IEEE
Transactions on Information Theory} {\bf 25} (1979), 1-7.


\bibitem{venky}
V. Natarajan, Independent sets in powers of odd cycles and the
global min-cut problem. Ph. D. thesis. Carnegie Mellon University.

%
%\bibitem{MRR}
%R. J. McEliece, E. R. Rodemich and H. C. Rumsey,
%The Lov\'asz bound and some generalizations,
%{\em Journal of Combinatorics, Information and
%Systems Science}
%3 (1978), 134-152.
%
\bibitem{ros}
M. Rosenfeld,
On a problem of C. E. Shannon in graph theory,
{\em Proceedings of the AMS} {\bf 18} (1967), 315-319.


\bibitem{Sh}
C.~E. Shannon, The zero-error capacity of a noisy channel, {\em
IRE Transactions on Information Theory} {\bf 2} (1956), 8--19.

%\bibitem{VZ}
%A.~Vesel, J. Zerovnik,
%Improved lower bound on the Shannon capacity of C7,
%{\em Information Processing Letters} 81(5) (2002), 277-282.

\bibitem{stabs} M. Simonovits, A method for solving extremal
problems in graph theory, {\em Theory of Graphs} (Proc. Colloq.
Tihany 1966) Academic Press, 1968, pp. 279-319.

\end{thebibliography}

\end{document}
