\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\usepackage{tikz}
\usepackage{booktabs}
\usepackage{cite}
\usepackage{subcaption}
\usepackage{float}
\usepackage{tabularx, environ}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\DeclareMathOperator{\kl}{kl}
\DeclareMathOperator{\Tor}{Tor}
\def\NP{{\rm NP}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\captionsetup[subfigure]{labelformat=empty}
% slightly adapted from https://tex.stackexchange.com/a/255679
\makeatletter
\newcommand{\problemtitle}[1]{\gdef\@problemtitle{\raisebox{2pt}{\large #1}}}
\newcommand{\probleminstance}[1]{\gdef\@probleminstance{#1}}
\newcommand{\problemquestion}[1]{\gdef\@problemquestion{#1}}
\NewEnviron{problem}{
\problemtitle{}\probleminstance{}\problemquestion{}
\BODY
\par\addvspace{.5\baselineskip}
\noindent
\begin{tabularx}{\textwidth}{l X c}
\hline \\ [-12pt]
\multicolumn{2}{l}{\@problemtitle} \\
\textbf{Instance:} & \@probleminstance \\
\textbf{Question:} & \@problemquestion \\
\hline
\end{tabularx}
\par\addvspace{.5\baselineskip}
}
\makeatother
\begin{center}
\vskip 1cm{\LARGE\bf
Knights and Liars on Graphs}
\vskip 1cm
\large
Paul Tabatabai and Dieter P. Gruber \\
Polymer Competence Center Leoben GmbH\\
Roseggerstra{\ss}e 12\\
8700 Leoben\\
Austria \\
\href{mailto:paul.tabatabai@pccl.at}{\tt paul.tabatabai@pccl.at} \\
\href{mailto:dieter.gruber@pccl.at}{\tt dieter.gruber@pccl.at}
\end{center}
\vskip .3 in
\begin{abstract}
We discuss the Knights and Liars problem,
which is the problem of maximizing the number of red vertices in a red-blue-coloring
of the vertices on a square grid, such that for each red vertex, exactly half of its neighbors
are red, and for each blue vertex, \emph{not} exactly half of its neighbors
are red.
We discuss the generalization of the problem to arbitrary graphs and discuss three
integer programming formulations, by which we give results for grid graphs, torus grid graphs, triangular grid
graphs, and graphs corresponding to the transitive closure of the boolean lattice.
We give a full combinatorial treatment for two-dimensional grid graphs whose shorter interval-size is less than seven.
We further prove that the decision version of the generalized problem is \NP-complete.
\end{abstract}
\section{Introduction and definitions}
\label{problemformulation}
The Knights and Liars problem was the topic of the mathematical competition \emph{Mathematical Marathon 140},
which Letsko \cite{LetskoMM140} organized. Letsko \cite{LetskoMM140} has compiled an interesting summary of the results obtained
by multiple contributors of the competition and added the corresponding
sequence \seqnum{A289362} to the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{SloaneOEIS}.
The problem is a beautiful mathematical recreation and we find it fitting to introduce it in the following, riddle-esque way,
which has been adapted slightly from Letsko's comment on his OEIS entry.
\begin{quote}
\emph{
Consider a finite square grid, on each point of which
there is either a knight or a liar.
A knight always speaks the truth, a liar always lies.
All occupants of the grid make the same statement:
``Exactly half of my (horizontal and vertical) neighbors are knights.''
What is the maximum possible number of knights on the grid?
}
\end{quote}
We give a more general problem definition, generalizing the Knights and Liars problem to arbitrary
graphs.
\begin{definition}
For a (simple and undirected) graph $G$, call a vertex 2-coloring (we will call the colors red and blue) \emph{red-balanced}
if for each red vertex $v$, exactly half of $v$'s neighbors are
red and if for each
blue vertex $w$, \emph{not} exactly half of $w$'s neighbors are red.
We define the \emph{Knights and Liars number} $\kl(G)$ to be the maximum number of red vertices in a red-balanced coloring
of $G$.
\end{definition}
The Knights and Liars number of a graph is well-defined, because every graph has at least one red-balanced coloring, namely
the coloring, where all isolated vertices are red and all other vertices are blue.
The main focus of this paper is on grid graphs.
In Definition \ref{griddef}, we define grid graphs formally and introduce some notation.
\begin{definition}
\label{griddef}
For $d \geq 2$, let $k_1, k_2, \ldots, k_d \geq 1$ be integers. The \emph{grid graph} (or just \emph{grid})
$G_{k_1,\ldots, k_d}$ is the graph whose vertex set is
$[k_1] \times [k_2] \times \cdots \times [k_d]$ and in which two vertices
form an edge if they differ in exactly one coordinate and if the absolute difference in this coordinate is one.
We call $d$ the \emph{dimension} of the grid and call the integers $k_i$ the \emph{interval-sizes} of the grid.
Sometimes it is convenient notation to identify the grid graph
with its vertex set and to write $[k_1] \times \cdots \times [k_d]$ instead of $G_{k_1, \ldots, k_d}$.
If all interval-sizes are equal, say $k_1 = \cdots = k_d = n$,
we may write
$[n]^d$ to denote the graph $G_{n,\ldots,n}$.
If a vertex $x = (x_1, \ldots, x_d)$ has at least one coordinate $j$ with
$x_j \in \{1, k_j\}$, we say $x$ belongs to the \emph{outer shell} of $G_{k_1, \ldots, k_d}$.
For $d = 2$, we call the outer shell the \emph{border} of the grid.
A vertex that does not belong to the outer shell is called \emph{interior} vertex.
\end{definition}
By thinking of knights as red vertices and liars as blue vertices, the original problem is
equivalent to asking what the value of $\kl(G_{n,n})$ is.
Table \ref{knownvalues} corresponds to the sequence \seqnum{A289362} and
lists all currently known Knights and Liars numbers $\kl(G_{n,n})$.
The bold entries are our contribution. Figures \ref{newexamples} and \ref{oldexamples} show
red-balanced colorings of the grids $G_{n,n}$ with the maximum possible number of red vertices for $4 \leq n \leq 18$.
We computed these colorings using the integer programming approach described in Section \ref{ipsection}.
For visibility reasons, edges are not drawn and blue vertices are drawn at a smaller size.
\begin{table}
\centering
\resizebox{2.5in}{!}{%
\begin{tabular}{cc|cc|cc}
\toprule
$n$ & $\kl(G_{n,n})$ & $n$ & $\kl(G_{n,n})$ & $n$ & $\kl(G_{n,n})$ \\
\midrule
1 & 1 & 7 & 10 & 13 & 58 \\
2 & 0 & 8 & 16 & 14 & 68 \\
3 & 0 & 9 & 28 & 15 & 88 \\
4 & 4 & 10 & 32 & 16 & \textbf{98} \\
5 & 8 & 11 & 40 & 17 & \textbf{110} \\
6 & 10 & 12 & 46 & 18 & \textbf{126} \\
\bottomrule
\end{tabular}
}
\caption{All known Knights and Liars numbers for two-dimensional square grid graphs.}
\label{knownvalues}
\end{table}
\begin{figure}[H]
\centering
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_4.eps}
\subcaption{$\kl(G_{4,4}) = 4$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_5.eps}
\subcaption{$\kl(G_{5,5}) = 8$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_6.eps}
\subcaption{$\kl(G_{6,6}) = 10$}
\end{subfigure} \par\bigskip
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_7.eps}
\subcaption{$\kl(G_{7,7}) = 10$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_8.eps}
\subcaption{$\kl(G_{8,8}) = 16$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_9.eps}
\subcaption{$\kl(G_{9,9}) = 28$}
\end{subfigure} \par\bigskip
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_10.eps}
\subcaption{$\kl(G_{10,10}) = 32$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_11.eps}
\subcaption{$\kl(G_{11,11}) = 40$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_12.eps}
\subcaption{$\kl(G_{12,12}) = 46$}
\end{subfigure} \par\bigskip
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_13.eps}
\subcaption{$\kl(G_{13,13}) = 58$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_14.eps}
\subcaption{$\kl(G_{14,14}) = 68$}
\end{subfigure}%
\begin{subfigure}{.33\textwidth}
\centering
\includegraphics{figures/grid_15.eps}
\subcaption{$\kl(G_{15,15}) = 88$}
\end{subfigure}%
\caption[short]{Red-balanced colorings of $G_{n,n}$ with the
maximum possible number of red vertices for $n = 4, \ldots, 15$.}
\label{oldexamples}
\end{figure}
\begin{figure}[H]
\centering
\begin{subfigure}{0.31\textwidth}
\centering
\includegraphics{figures/grid_16.eps}
\subcaption{$\kl(G_{16,16}) = 98$}
\end{subfigure}%
\begin{subfigure}{0.33\textwidth}
\centering
\includegraphics{figures/grid_17.eps}
\subcaption{$\kl(G_{17,17}) = 110$}
\end{subfigure}%
\begin{subfigure}{0.35\textwidth}
\centering
\includegraphics{figures/grid_18.eps}
\subcaption{$\kl(G_{18,18}) = 126$}
\end{subfigure}
\caption[short]{Red-balanced colorings of $G_{n,n}$ with the
maximum possible number of red vertices for $n = 16, 17, \text{ and } 18$.}
\label{newexamples}
\end{figure}
We will also be interested in torus grid graphs,
which can be thought of as grid graphs in which the neighborhood relation
allows for wrap-around at the borders of the grid.
We define torus grid graphs formally in Definition \ref{torusdef}.
\begin{definition}
\label{torusdef}
For $d \geq 2$, let $k_1, k_2, \ldots, k_d \geq 1$ be integers. The \emph{torus grid graph}
$\Tor_{k_1,\ldots, k_d}$ is the graph whose vertex set is
$[k_1] \times [k_2] \times \cdots \times [k_d]$ and in which two vertices
form an edge if they differ in exactly one coordinate $j$ and if the absolute difference in this coordinate
is either $1$ or $k_j-1$.
We call $d$ the \emph{dimension}
and the integers $k_i$ the \emph{interval-sizes} of $\Tor_{k_1,\ldots, k_d}$.
\end{definition}
Note that in contrast to grid graphs, $d$-dimensional torus grid graphs are $2d$-regular.
\subsection{Relation to the maximum density still life problem}
The Knights and Liars problem on two-dimensional grid graphs
is related to the \emph{maximum density still life} (MDSL) problem.
In Definition \ref{conways}, we define Conway's \cite{WinningWays} Game of Life and still lifes.
The wording is inspired by the definition given by Chu and Stuckey \cite{Chu2012}.
\begin{definition}[Conway's Game of Life and still lifes]
\label{conways}
\emph{Conway's Game of Life} is played on an infinite grid over discrete time steps.
At each time step, each cell (vertex) has exactly one of the states
\emph{alive} or \emph{dead}.
The state of a cell $c$ at time step $t+1$ is determined by the number of live
(orthogonal and diagonal) neighbors of
$c$ at time step $t$:
\begin{enumerate}
\item If $c$ has exactly two live neighbors at time step $t$, then the state of $c$ does not change at time step $t+1$.
\item If $c$ has exactly three live neighbors at time step $t$, then $c$ is alive at time step $t+1$.
\item If $c$ has at least four or at most one live neighbors at time step $t$, then $c$ is dead at time step $t+1$.
\end{enumerate}
If the above rules do not modify the state of any cell, the state of the grid
is called a \emph{still life}.
\end{definition}
Other life-variants, and their corresponding still lifes
can be defined by varying the number of possible states,
the definition of neighborhood, and the cell rules.
The density problem for Conway's Game of Life on the infinite grid was solved by Elkies \cite{Elkies1998},
who proved that the largest possible density
of a still life in Conway's Game of Life is $1/{2}$.
The finite version of this problem is defined in Definition \ref{mdsl}.
\begin{definition}
\label{mdsl}
The ($n \times n$) \emph{maximum density still life (MDSL) problem}
asks for the largest possible density (or maximum possible number)
of live cells in an $n \times n$ sub-region of a still life, such that all cells
outside of the region are dead.
\end{definition}
Formulating the Knights and Liars problem on two-dimensional grid graphs in
terms of still lifes leads to the following set of cell rules,
where only orthogonal neighborhood is considered:
\begin{enumerate}
\item If $c$ has exactly two live neighbors at time step $t$, then $c$ is alive at time step $t+1$.
\item If $c$ does not have exactly two live neighbors at time step $t$, then $c$ is dead at time step $t+1$.
\end{enumerate}
The problem of finding the value $\kl(G_{n+2,n+2})$ is the same as the $n \times n$ MDSL problem for the above cell rules,
i.e., asking for the maximum
number of live cells in an $n \times n$ sub-region of a still life with respect to the above rules, such that
all cells outside of the region are dead.
This holds,
because in any red-balanced coloring of a finite grid (with side-lengths at least 3),
all vertices on the border of the grid are blue
(this important fact is discussed in more detail in Section \ref{upperboundsection}).
This means that the red-balanced colorings
of finite grids (with side-lengths at least 3)
are exactly the red-blue-colorings such that
\begin{enumerate}
\item every red interior vertex has exactly two red neighbors,
\item every blue interior vertex does \emph{not} have exactly two red neighbors, and
\item all vertices on the border are blue.
\end{enumerate}
The first two requirements correspond
to the still life conditions.
The third requirement corresponds to the requirement that all cells outside of the interior (non-border)
region are dead and can not become alive. To see this, note that cells outside of the interior region have at most one orthogonal neighbor
in the interior region.
Chu and Stuckey \cite{Chu2012} solved the MDSL problem for Conway's Game of Life
for all values of $n$. They used different approaches
for various ranges of $n$. For $n \leq 50$,
they used a constraint programming formulation in which they
re-formulated the problem
in terms of \emph{wastage}, by assigning a wastage-score to
each possible $3\times 3$ pattern within a still life
and proving that minimizing the total wastage
is equivalent to maximizing the number of live cells.
It remains open whether a similar re-formulation is possible for the Knights and Liars Problem
(see Section \ref{openproblems} for a list of open problems).
Chu and Stuckey \cite{Chu2012} further list some
previous computational techniques in the literature that have been used to attack the MDSL problem.
Among those, we mention Bosch \cite{Bosch1999}, who computed values for the MDSL problem for Conway's Game of Life by
using two integer programming formulations.
Bosch \cite{Bosch2000} used integer programming to find maximum density still lifes
for two other life variants.
In Section \ref{ipsection} we discuss three integer program formulations IP1, IP2 and IP3
for computing values of the Knights and Liars problem.
The formulation IP1 is a re-discovery of ideas used by Bosch \cite{Bosch1999},
and IP3 has been adapted from Bosch \cite{Bosch1999},
after the authors learned about this related work.
\section{Upper bounds and trivially blue vertices}
\label{upperboundsection}
In the examples shown in Figures and \ref{oldexamples} and \ref{newexamples}, all vertices on the borders of the grids
are blue. This is not by chance: For $m, n \geq 3$,
the border vertices of the grid $G_{m,n}$ are blue in \emph{any} red-balanced coloring.
The degree-three vertices on the border each have three neighbors---an odd number---and must therefore be blue.
The corner vertices of the grid must also be blue,
because the majority of their neighbors (two out of two) have degree three and are blue by the previous argument.
In fact, the generalization of this property holds for \emph{all} grids. We prove this
in Lemma \ref{blueshell}.
\begin{lemma}
\label{blueshell}
Let $G = [k_1] \times \cdots \times [k_d]$ be the grid graph of dimension $d$ with interval-sizes
$k_1, \ldots, k_d \geq 3$. Then, in any red-balanced coloring of $G$, all vertices of the outer shell
of $G$ are blue.
\begin{proof}
In this proof we say \emph{a vertex is blue} to mean that it is blue in any red-balanced coloring
of $G$.
For a vertex $x = (x_1, \ldots, x_d)$ of $G$, and for each $1 \leq i \leq d$, we define
$$\delta(x_i) := \min(x_i - 1, k_i-x_i)$$
to be the distance of $x_i$ to the end-point of the interval $[k_i]$ that is closer to $x_i$.
We further define $\text{dz}(x)$ to be the number of indices $i$ such that the distance
$\delta(x_i)$ is zero.
Note that the vertices $x$ for which $\text{dz}(x) > 0$ are exactly
the vertices of the outer shell of $G$,
and that each vertex $x$ has exactly $2d - \text{dz}(x)$ neighbors in $G$.
It follows that the vertices in the set
$$S_{\text{odd}} :=\left\{x \in V(G) \mid \text{dz}(x) \text{ is odd}\right\}$$
have an odd number of neighbors in $G$ and are thus blue.
For $d = 1$, the set $S_{\text{odd}}$ is the outer shell of $G$.
For $d \geq 2$, it remains to show that the vertices $x$ for which $\text{dz}(x) \geq 2$ is even
are blue.
We prove this for the case where $d \geq 3$ is odd (the argument for even $d$ is similar).
For $n \geq 1$, we define
$$S_n := \left\{x \in V(G) \mid \sum_{i=1}^d \delta(x_i) = n \text{ and } \text{dz}(x) \geq 2 \text{ is even}\right\}.$$
Let $M$ be the largest integer such that $S_M$ is non-empty ($M$ is the sum of the $d-2$ largest values $\lfloor k_i / {2} \rfloor$).
We prove by induction that for every $1 \leq n \leq M$, all vertices in $S_n$ are blue.
Let $x = (x_1, \ldots, x_d)$ be a vertex in $S_1$. We have $\text{dz}(x) = d-1$ and $\delta(x_j) = 1$
for exactly one index $j$. It follows that $x$ has $2d - \text{dz}(x) = d+1$ neighbors,
out of which $d$ are in $S_{\text{odd}}$.
The strict majority of neighbors of $x$ is in $S_{\text{odd}}$,
and it follows that $x$ is blue.
Now let $2 \leq n \leq M$. Assume that all vertices in $S_{n-1}$ are blue.
If $S_n$ is empty, the assertion holds. Otherwise
let $x = (x_1, \ldots, x_d)$ be a vertex in $S_n$.
The vertex $x$ has $\text{dz}(x) \geq 2$ neighbors in $S_{\text{odd}}$.
For each index $i$ with
$\delta(x_i) = \lfloor k_i / {2} \rfloor$ (this is the maximum value $\delta(x_i)$ can take), the vertex $x$ has two neighbors in $S_{n-1}$.
For each index $i$ with $\delta(x_i) = 1$, the vertex $x$ has one neighbor in $S_{\text{odd}}$, and one neighbor in $S_{n+1}$.
For each index $i$ with $2 \leq \delta(x_i) \leq \lfloor k_i / {2} \rfloor -1$, the vertex $x$ has one neighbor in $S_{n-1}$ and one neighbor in $S_{n+1}$.
We showed that the strict majority of neighbors of $x$ is in $S_{\text{odd}} \cup S_{n-1}$, and it follows that $x$ is blue.
The proof for even $d$ works by starting the induction
from the set $S_0$ instead of from $S_1$.
\end{proof}
\end{lemma}
For two-dimensional square grid graphs, Letsko \cite{LetskoMM140} gives the bound
$\kl(G_{n,n}) < \frac{2}{3}n^2$.
We use Letsko's argument for this bound to show a tight version of the bound for
regular graphs.
\begin{proposition}
\label{ub}
For a regular graph $G$, we have the upper bound
$$\kl(G) \leq \frac{2}{3} \left \vert V(G) \right \vert.$$
\begin{proof}
Let $k$ denote the degree of the vertices in $G$ (i.e., $G$ is $k$-regular).
Consider a red-balanced coloring of $G$ in which exactly $r$ vertices are red.
For each vertex $v$ of $G$, let $N_{\text{red}}(v)$
denote the number of red neighbors of $v$ in this coloring.
Since every vertex of $G$ has $k$ neighbors, we have
$$kr = \sum_{v \in V(G)}N_{\text{red}}(v).$$
Each red vertex has exactly $k/{2}$ red neighbors and each blue vertex has at most $k$ red neighbors, giving the bound
$$ kr = \sum_{v \in V(G)}N_{\text{red}}(v) \leq r \frac{k}{2} + \left(\left\vert V(G) \right \vert-r\right)k,$$
from which the proposition follows.
\end{proof}
\end{proposition}
We give some examples of graphs for which Proposition \ref{ub} holds with equality.
For two-dimensional torus grid graphs whose interval-sizes
$m$ and $n$ are both multiples of three, we have $\kl(\Tor_{m,n}) = \frac{2}{3}mn$.
A corresponding coloring can
be constructed by tiling the $3\times 3$ pattern whose main diagonal vertices
are blue, and whose other vertices are red.
Figure \ref{tiling} shows a coloring of the torus grid graph $\Tor_{12,27}$ constructed this way.
\begin{figure}[H]
\centering
\includegraphics{figures/torus_12_27.eps}
\caption{A red-balanced coloring of the torus grid graph $\Tor_{12,27}$ in which the ratio of red vertices is $2/{3}$.}
\label{tiling}
\end{figure}
Similarly, by tiling the same $3 \times 3$ pattern,
the infinite two-dimensional grid graph can also be colored such that the ratio of red vertices is $2/{3}$.
This pattern and its optimality was also known to Elkies \cite{Elkies1998}, who proved that
if $X$ is a subset of the infinite (4-neighborhood) grid such that every $x \in X$ has at most
two neighbors in $X$, then $X$ has density at most $2/{3}$.
The Knights and Liars number of the complete tri-partite graph $K_{n,n,n}$ on $3n$ vertices is $2n$.
In the corresponding coloring,
all vertices of one of the partition sets of $K_{n,n,n}$ are blue,
and the vertices of the other two partition sets are red.
As remarked by the anonymous referee, the bound in Proposition \ref{ub} is tight for the line graph $L(G)$
of every cubic graph $G$ that admits a perfect matching.
To obtain a red-balanced coloring that colors two thirds of the vertices of $L(G)$ red, take
a perfect matching $M$ of $G$, and color all vertices of $L(G)$ corresponding to $M$ blue, and all other vertices red.
Figure \ref{linepetersen} shows such a coloring of the line graph of the Petersen graph.
\begin{figure}[H]
\centering
\includegraphics{figures/line_petersen.eps}
\caption{A red-balanced coloring of the line graph of the Petersen graph, in which 10 out of 15 vertices are red.}
\label{linepetersen}
\end{figure}
Because of Lemma \ref{blueshell}, it is possible to generalize Letsko's \cite{LetskoMM140}
argument for the bound $\kl(G_{n,n}) < \frac{2}{3}n^2$ to arbitrary grid graphs,
and by doing a slightly more involved calculation,
we obtain a bound that is an improvement for the special case of two-dimensional square grid graphs.
\begin{proposition}
\label{boundthm}
Let $G = [k_1] \times \cdots \times [k_d]$ be the grid graph of dimension $d$ with interval-sizes
$k_1, \ldots, k_d \geq 3$. Then
$$ \kl(G) \leq
\frac{2}{3} \prod_{i=1}^d \left (k_i -2 \right )+
\frac{2}{3d}\sum_{i=1}^d \prod_{j \neq i} (k_j - 2).$$
\begin{proof}
Consider a red-balanced coloring of $G$ in which exactly $r$ vertices are red.
For each vertex $v$ of $G$, let $N_{\text{red}}(v)$
denote the number of red neighbors of $v$ in this coloring.
Since every red vertex has $2d$ neighbors in $G$ (this follows from Lemma \ref{blueshell}),
we have
$$2dr = \sum_{v \in V(G)}N_{\text{red}}(v).$$
Every red vertex has exactly $d$ red neighbors and
every blue vertex in the interior of $G$ has at most $2d$ red neighbors.
Since all red vertices are in the interior of the grid, the number of blue vertices in the interior
of the grid is $\prod_{i=1}^d \left( k_i -2 \right ) - r $.
Every (blue) vertex $x = (x_1, \ldots, x_d)$ of the outer shell for which
$x_j \in \{1, k_d\}$ for \emph{exactly one} index $j$, can have at most one red neighbor.
There are $\sum_{i=1}^d 2 \prod_{j \neq i} (k_j - 2)$ such vertices in the outer shell of $G$.
All other vertices of the outer shell only have neighbors in the outer shell (which can not be red).
From these arguments we obtain the bound
\begin{equation}
\label{gridbound}
2dr = \sum_{v \in V(G)}N_{\text{red}}(v) \leq dr + 2d \left (
\prod_{i=1}^d \left( k_i -2 \right ) - r \right) +
\sum_{i=1}^d 2 \prod_{j \neq i} (k_j - 2),
\end{equation}
from which the proposition follows.
\end{proof}
\end{proposition}
For the case of two-dimensional square grids, Proposition \ref{boundthm} is the bound
$$\kl(G_{n,n}) \leq \frac{2}{3}n^2 - 2n + \frac{4}{3} \ \text{ for } n \geq 3,$$
which is tight for $n = 4$ and $n = 5$. For large $n$, we can get close to a red-vertex ratio of $2/{3}$, in the following sense:
Letsko \cite{LetskoMM140} gives a construction by Sergei Polovinkin, showing that for every
$0 < \alpha < 2/{3}$, there exists a natural number $n_{\alpha}$ such that $\kl(G_{n_{\alpha},n_{\alpha}}) \geq \alpha n_{\alpha}^2$.
We proved in Lemma \ref{blueshell} that the vertices of the outer shell of a grid graph are blue in any red-balanced coloring.
The main argument we used in the proof was that if the majority of neighbors of a vertex $x$ is blue in any red-balanced coloring,
the vertex $x$ must also be blue in any red-balanced coloring. This immediately leads to the following
simple method for finding vertices that are blue in any red-balanced coloring for arbitrary graphs $G$.
First, let $B_0$ be the set of odd-degree vertices of $G$.
Then, iteratively for $i \geq 1$,
define $B_i$ as the union of $B_{i-1}$ and the set of vertices of $G$ whose strict majority of neighbors is in $B_{i-1}$.
Stop as soon as $B_{j} = B_{j-1}$ for some $j \geq 1$ and call the resulting set the \emph{trivially blue vertices} of $G$.
For two-dimensional grid graphs, $B_0$ is the set of degree-three vertices of the border of the grid and
$B_1$ is the set of all border vertices (including corner vertices).
Graphs consisting only of trivially blue vertices have Knights and Liars number zero.
Examples of such graphs are the following:
\begin{itemize}
\item Graphs in which every vertex has an odd number of neighbors, such as the complete graph on an even number of vertices and hypercubes of odd dimension.
\item The star graph $S_k$ for $k \geq 3$.
\item Grid graphs in which at least one interval-size is three.
\item Rooted trees with the property that each vertex in the second-to-last level has at least two leaves.
\end{itemize}
Trivially blue vertices can be thought of as vertices that must be colored blue ``for simple reasons''.
In fact, there are graphs \emph{without} trivially blue vertices whose Knights and Liars number is zero.
Figure \ref{kl0example} shows an example of a 4-regular graph on eight vertices for which only
the all-blue coloring is red-balanced.
\begin{figure}[H]
\centering
\includegraphics{figures/kl-0-example.eps}
\caption{A 4-regular graph $G$ with $\kl(G) = 0$.}
\label{kl0example}
\end{figure}
\section[Results for grid graphs whose shorter interval-size is less than seven]{Results for grids $G_{m,n}$ with $m\leq 6$}
\label{leq6}
We discuss the Knights and Liars problem for the non-square grid graph
$G_{m,n}$ for $m \leq 6$.
For $m = 1$, the grid is a path.
In a path with a red-balanced coloring,
red vertices can only appear in pairs of consecutive positions. Two such pairs must be
separated by exactly one blue vertex. The end-points of the path have degree one and must be blue.
It follows that
$\kl(P_{3k+1}) = 2k$ for $k\geq 1$,
and $\kl(P_{n}) = 0$ for all other $n \geq 2$.
Figure \ref{pathexample} shows a red-balanced coloring of the path on $16$ vertices.
\begin{figure}[H]
\centering
\includegraphics{figures/grid_1_16.eps}
\caption{A red-balanced coloring of the path $P_{16}$ with ten red vertices.}
\label{pathexample}
\end{figure}
For $m=2$, only the four corner vertices of the grid have even degree. For $n\geq3$,
coloring the corner vertices of $G_{2,n}$ red leads to a red-balanced coloring,
and it follows that $\kl(G_{2,n}) = 4$ for all $n\geq 3$.
For $m = 3$, we have $\kl\left(G_{3,n}\right) = 0$ for all $n$, because $G_{3,n}$
consists of trivially blue vertices only.
We show that for $4 \leq m \leq 6$, finding a red-balanced coloring
with the maximum number of red vertices is equivalent to a packing problem.
For $m = 4$ (and $n\geq 4$), in a red-balanced coloring of $G_{4,n}$, the only possible connected
subgraph formed by red vertices are $4$-cycles of interior vertices of the grid.
The border vertices of the grid must be blue, and each pair of neighboring $4$-cycles must be
separated by at least two columns of blue vertices. This can be viewed as each $4$-cycle
being enclosed by at least one of its \emph{own} blue columns on both its left and its right.
Thus, for every four columns in the grid, we can color four vertices red and it follows that
for all $n \geq 4$, we have
$$\kl\left(G_{4,n}\right) = 4\left\lfloor \frac{n}{4} \right\rfloor.$$
Figure \ref{4times15grid} shows a red-balanced coloring of the grid
$G_{4,15}$ with the maximum possible number of red vertices.
\begin{figure}[H]
\centering
\includegraphics{figures/grid_4_15.eps}
\caption{A red-balanced coloring of the grid $G_{4,15}$ with 12 red vertices.}
\label{4times15grid}
\end{figure}
For $m=5$ (and $n \geq 5$), we can argue similarly as in the case $m=4$, but now three
different red-colored structures are possible. The possible sub-colorings are shown in
Figure \ref{5packingoptions}.
Note that for $m=5$, a cycle of red vertices enclosing more than two blue vertices
can not occur in a red-balanced coloring,
because there is a blue vertex with two red and two blue neighbors in this pattern.
\begin{figure}[H]
\centering
\includegraphics{figures/height_5_patterns.eps}
\caption{The three possible patterns of red vertices
(up to vertical symmetry of the first pattern) in a red-balanced coloring the grid $G_{5,n}$.}
\label{5packingoptions}
\end{figure}
The three possible configurations contribute 4, 8, and 10 red vertices,
respectively. The problem can thus be solved by maximizing
$4x + 8y + 10z$ such that $x, y$ and $z$ are nonnegative integers with $4x+5y+6z\leq n$.
For $m=6$ (and $n \geq 6$), the relevant configurations are shown in Figure \ref{6packingoptions}.
\begin{figure}[H]
\centering
\includegraphics{figures/height_6_patterns.eps}
\caption{The two relevant patterns (up to vertical shifts of the first pattern) of red vertices in a red-balanced coloring the grid $G_{6,n}$.}
\label{6packingoptions}
\end{figure}
The remaining possible patterns---an $8$-cycle of blue vertices
enclosing a blue vertex and a rotated version of the $10$-cycle from the case $m=5$---are
strictly worse than the $10$-cycle pattern and can thus be ignored. Note that two vertically shifted
$4$-cycles of red vertices can now neighbor each other with just a single blue column separating them,
but the resulting pattern is strictly worse than the $10$-cycle pattern and can thus be ignored as well.
For $n \geq 6$, we have
$$\kl(G_{6,n}) = \begin{cases}
10k +4, & \text{ if } n = 5k + 4; \\
10k, & \text{ if } n = 5k + r, \text{ where } r \leq 3.
\end{cases}$$
The problem is more difficult for $m, n \geq 7$. Figures \ref{7times32grid} and \ref{8times32grid} show examples
of red-balanced colorings with the maximum number of red vertices for grids with $m = 7$ and $m=8$.
\begin{figure}[H]
\centering
\includegraphics{figures/grid_7_32.eps}
\caption{A coloring of $G_{7,32}$ with the maximum possible number of red vertices.}
\label{7times32grid}
\end{figure}
\begin{figure}[H]
\centering
\includegraphics{figures/grid_8_32.eps}
\caption{A coloring of $G_{8,32}$ with the maximum possible number of red vertices.}
\label{8times32grid}
\end{figure}
\section{Exact values for the Knights and Liars problem}
In this section, we discuss integer programming formulations for computing a red-balanced coloring
with the maximum possible number of red vertices for arbitrary graphs.
We were especially interested in
computing Knights and Liars numbers for graph classes with highly regular structures
and consisting of few trivially blue vertices.
In addition to the newly obtained Knights and Liars numbers
for square grids, we give results for
non-square and higher-dimensional grid graphs, torus grid graphs, triangular grid graphs,
and graphs corresponding to the transitive closure of the boolean lattice.
\subsection{Integer programming formulations}
\label{ipsection}
Let $G$ be a (simple and undirected) graph.
For a vertex $v$ of $G$, let $N(v)$ denote the set of neighbors of $v$ in $G$ and write $\deg(v)$ for the degree
of $v$ in $G$.
Let $V_{\text{even}}(G)$ and $V_{\text{odd}}(G)$ denote the set of
vertices of even, and odd degree of $G$, respectively.
For each vertex $v$ of $G$, we define a binary variable
$x_v$ encoding whether $v$ is colored red.
Vertices of odd degree must be colored blue:
\begin{equation}
x_v = 0 \ \text{ for each } v \in V_{\text{odd}}(G)
\end{equation}
If a vertex of even degree is red, exactly
half of its neighbors must be red:
\begin{equation}
\label{redimpl}
x_v = 1 \ \text{ implies } \ \sum_{w \in N(v)} x_w = \frac{\deg(v)}{2}\ \text{ for each } v \in V_{\text{even}}(G)
\end{equation}
We say a vertex of even degree has \emph{high saturation} if the
strict majority of its neighbors is red and that is has \emph{low saturation} if the strict minority of its neighbors is red.
If a vertex of even degree is blue, it must have either high or low saturation:
\begin{align}
x_v = 0 \text{ implies } \left(
\sum_{w \in N(v)} x_w \geq \frac{\deg(v)}{2} + 1
\text{ or }
\sum_{w \in N(v)} x_w \leq \frac{\deg(v)}{2} - 1
\right) \label{highlowimpl} \\
\text{ for each } v \in V_{\text{even}}(G) \nonumber
\end{align}
There are multiple ways to model \eqref{highlowimpl} as a set of linear integer constraints.
In the first approach,
we introduce binary variables $H_v$ and $L_v$ for every vertex $v$ of even degree in $G$.
These variables are used to \emph{imply} that a vertex has high or low saturation, respectively. The implication
\eqref{highlowimpl} is equivalent to the conjunction of the implications \eqref{blueimpl}--\eqref{lowimpl}.
\begin{align}
x_v = 0 \ \text{ implies } & H_v + L_v = 1 \ \text{ for each } v \in V_{\text{even}}(G). \label{blueimpl} \\
H_v = 1 \ \text{ implies } & \sum_{w \in N(v)} x_w \geq \frac{\deg(v)}{2} + 1 \ \text{ for each } v \in V_{\text{even}}(G). \label{highimpl} \\
L_v = 1 \ \text{ implies } & \sum_{w \in N(v)} x_w \leq \frac{\deg(v)}{2} - 1 \ \text{ for each } v \in V_{\text{even}}(G). \label{lowimpl}
\end{align}
We model the implications \eqref{redimpl} and \eqref{blueimpl}--\eqref{lowimpl} as linear inequalities,
resulting in the integer program IP1.
It is easy to see that \eqref{redimpl} is equivalent to the conjunction of \eqref{redlin1} and \eqref{redlin2},
that \eqref{blueimpl} is equivalent to the conjunction of \eqref{bluelin1} and \eqref{bluelin2},
and that \eqref{highimpl} and \eqref{lowimpl}
are equivalent to \eqref{highlin} and \eqref{lowlin}, respectively.
\begin{flalign}
\text{(IP1) max. } \ & \sum_{v \in V(G)} x_v & & \nonumber \\
\text{subject to } \ & x_v = 0 & & \text{for each } v \in V_{\text{odd}}(G). \label{oddzero} \\
& \sum_{w \in N(v)} x_w \leq \deg(v) - \frac{\deg(v)}{2}x_v & & \text{for each } v \in V_{\text{even}}(G). \label{redlin1}
\end{flalign}
\begin{flalign}
\hphantom{subject to} & \sum_{w \in N(v)} x_w \geq \frac{\deg(v)}{2}x_v & & \text{for each } v \in V_{\text{even}}(G). \label{redlin2} \\
& H_v + L_v \leq 1 + x_v & & \text{for each } v \in V_{\text{even}}(G). \label{bluelin1} \\
& H_v + L_v \geq 1 - x_v & & \text{for each } v \in V_{\text{even}}(G). \label{bluelin2} \\
& \sum_{w \in N(v)} x_w \geq \left ( \frac{\deg(v)}{2} + 1 \right) H_v & & \text{for each } v \in V_{\text{even}}(G). \label{highlin} \\
& \sum_{w \in N(v)} x_w \leq \deg(v) - \left(\frac{\deg(v)}{2} +1\right) L_v & & \text{for each } v \in V_{\text{even}}(G). \label{lowlin} \\
& H_v, L_v \in \{0,1\} & & \text{for each } v \in V_{\text{even}}(G). \label{hlvars} \\
& x_v \in \{0,1\} & & \text{for each } v \in V(G). \nonumber
\end{flalign}
Note that the constraint \eqref{bluelin1} can optionally be dropped, because
\eqref{blueimpl} can be replaced by
$$x_v = 0 \ \text{ implies } H_v + L_v \geq 1 \ \text{ for each } v \in V_{\text{even}}(G).$$
Bosch \cite{Bosch1999} gives integer programming formulations for solving instances
of the maximum density still life problem for Conway's Game of Life. The integer programming formulation IP1
is a re-discovery of ideas used by Bosch.
Bosch uses constraints similar to \eqref{redlin1}--\eqref{redlin2} and
\eqref{bluelin2}--\eqref{lowlin} to model the cell rules in Conway's Game of Life.
Bosch does not use the optional constraint.
To obtain the Knights and Liars equivalent closest to Bosch's formulation,
all occurrences of the auxiliary variables $H_v$ and $L_v$ in IP1
are replaced by their negations $1-H_v$ and $1-L_v$ respectively.
This can be viewed as $x_v = 0$ forcing at least one of $L_v$ or $H_v$ to be zero,
$H_v = 0$ forcing $\sum_{w \in N(v)} x_w \geq \frac{\deg(v)}{2} + 1$, and
$L_v = 0$ forcing $\sum_{w \in N(v)} x_w \leq \frac{\deg(v)}{2} - 1$.
We give an alternative integer programming formulation IP2,
which uses only a single auxiliary variable for each vertex of even degree to model the
\emph{or} in \eqref{highlowimpl}.
\begin{flalign}
\text{(IP2) max. } \ & \sum_{v \in V(G)} x_v & & \nonumber \\
\text{subject to } \ & \eqref{oddzero}, \eqref{redlin1}, \eqref{redlin2} & & \nonumber \\
& \sum_{w \in N(v)} x_w \leq \ \left(\frac{\deg(v)}{2} -1\right) + \left(\frac{\deg(v)}{2} + 1 \right) (A_v + x_v) & & \text{for each } v \in V_{\text{even}}(G). \label{alt_or_1} \\
& \sum_{w \in N(v)} x_w \geq \left(\frac{\deg(v)}{2} + 1 \right) (A_v - x_v) & & \text{for each } v \in V_{\text{even}}(G). \label{alt_or_2} \\
& A_v\in \{0,1\} & & \text{for each } v \in V_{\text{even}}(G). \nonumber \\
& x_v \in \{0,1\} & & \text{for each } v \in V(G). \nonumber
\end{flalign}
The constraint \eqref{alt_or_1} models
$$(x_v = 0 \text{ and } A_v = 0) \text{ implies } \sum_{w \in N(v)} x_w \leq \ \left(\frac{\deg(v)}{2} -1\right) \ \text{ for each } v \in V_{\text{even}}(G),$$
and the constraint \eqref{alt_or_2} models
$$(x_v = 0 \text{ and } A_v = 1) \text{ implies } \sum_{w \in N(v)} x_w \geq \ \left(\frac{\deg(v)}{2} +1\right) \ \text{ for each } v \in V_{\text{even}}(G).$$
Bosch \cite{Bosch1999} gives another a way to model
(the Game of Life still life equivalent of) \eqref{highlowimpl}, which
uses no auxiliary variables, but has---depending on the degrees of the vertices
of $G$---a large number of constraints.
We call the Knights and Liars equivalent of this idea IP3.\\
{\footnotesize
\begin{flalign}
\text{(IP3) max. } \ & \sum_{v \in V(G)} x_v & & \nonumber \\
\text{subject to } & \ \eqref{oddzero}, \eqref{redlin1}, \eqref{redlin2} & & \nonumber \\
& -x_v + \sum_{w \in S} x_w - \sum_{w \in N(v) \setminus S} x_w \leq \frac{\deg(v)}{2} - 1 & & \text{for each } v \in V_{\text{even}}(G) \nonumber \\[-1.75em]
& & & \text{and each } S \subset N(v) \text{ with } \vert S \vert = \frac{\deg(v)}{2}. \label{bosch-subsets} \\
& x_v \in \{0,1\} & & \text{for each } v \in V(G). \nonumber
\end{flalign}
}
The constraint
\eqref{bosch-subsets} models that for each subset $S \subset N(v)$ with $\vert S \vert = \deg(v)/2$,
$x_v = 1$ implies that $S$ can not be exactly the set of all red neighbors of $v$.
Benchmarking the solving speed using the formulations IP1, IP2 and IP3
and the impact of negating the auxiliary variables and/or using the optional constraint in IP1
is difficult, because solvers are very sensitive to small structural changes, even such changes as
adding the constraints in different order.
However, IP3 seems to be not well suited for graphs with large degrees, for which IP1 and IP2 perform
significantly better.
Python programs for generating and solving the above integer programming formulations
are available at the first author's Github repository
\cite{TabatabaiGithub}.
We give implementations using both the official Python-API
\emph{gurobipy} of the commercial state-of-the art MIP solver \emph{Gurobi} \cite{Gurobi},
as well as COIN-OR's \cite{COINOR} library \emph{python-mip},
which allows to use the open source solver \emph{CBC}, which
is also maintained by COIN-OR.
The repository also contains integer programs that
use Gurobi's ability to natively model implications as indicator constraints.
The repository is a living collection of formulations and approaches to the Knights and Liars problem
and will be continuously updated.
Optionally, the concept of \emph{trivially blue vertices} discussed in Section \ref{upperboundsection} can
be used to adapt the above formulations.
The set of constraints \emph{$x_v = 0$ for each $v \in V_{\text{odd}}(G)$} can be replaced
by the set of constraints \emph{$x_v = 0$ for each trivially blue vertex $v$}, and all other
constraints need only be specified for vertices that are not trivially blue.
\subsection{Results}
\label{exactresults}
As mentioned in Section \ref{problemformulation},
we managed to calculate the new Knights and Liars numbers $\kl(G_{16,16}) = 98$,
$\kl(G_{17,17}) = 110$ and $\kl(G_{18,18}) = 126$.
These numbers were added to \seqnum{A289362} by the first author.
Using a desktop computer equipped with an AMD 3700X processor and 32 gigabytes of
memory, calculating $\kl(G_{17,17})$ using IP1 took approximately six hours, and finding $\kl(G_{18,18})$
took approximately six days.
For $16 \leq n \leq 18$, the Gurobi solver instance found red-balanced colorings with the maximum possible number of red vertices relatively quickly,
and spent most of the computation time proving optimality.
For this reason, we believe that the colorings we found for $n=19$ and $n=20$ are best possible.
The colorings---which are certificates for $\kl(G_{19,19}) \geq 144$ and $\kl(G_{20,20}) \geq 160$---are shown in Figure \ref{grids19and20}.
\begin{figure}[H]
\centering
\begin{subfigure}{.4\textwidth}
\centering
\includegraphics{figures/grid_19_lb.eps}
\subcaption{$\kl(G_{19,19}) \geq 144$}
\end{subfigure}%
\begin{subfigure}{.4\textwidth}
\centering
\includegraphics{figures/grid_20_lb.eps}
\subcaption{$\kl(G_{20,20}) \geq 160$}
\end{subfigure}%
\caption[short]{Red-balanced colorings of $G_{19,19}$ and $G_{20,20}$. We conjecture
that these colorings have the maximum possible number of red vertices.}
\label{grids19and20}
\end{figure}
We calculated Knights and Liars numbers and lower bounds
for the two-dimensional grid graph $G_{m,n}$ for $7 \leq m \leq n \leq 20$.
Our results are listed in Table \ref{twodim}.
The case $\min\{m,n\} \leq 6$ is discussed in Section \ref{leq6}.
We calculated Knights and Liars numbers for the grid graph $[n]^d$ for small values of $n$ and $d$.
The corresponding Knights and Liars numbers and lower bounds are listed in Table \ref{highdim}.
Note that the grid graphs $[2]^d$ are the $d$-dimensional hypercubes.
The hypercubes of odd dimension consist of vertices of odd degree only and thus
their Knights and Liars number is zero.
For the $8$-dimensional hypercube,
we obtained the bound $72 \leq \kl([2]^8) \leq 165$.
A red-balanced coloring of the $4$-dimensional hypercube is shown in Figure \ref{4cube}.
\begin{table}[H]
\center
\begin{tabular}{c|cccccccccccccc}
\toprule
$m/n$ & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
\midrule
7 & 10 & 12 & 14 & 20 & 20 & 20 & 22 & 24 & 30 & 30 & 30 & 32 & 34 & 40 \\
8 & - & 16 & 26 & 26 & 30 & 30 & 38 & 38 & 40 & 40 & 50 & 52 & 52 & 56 \\
9 & - & - & 28 & 30 & 32 & 34 & 40 & 40 & 44 & 52 & 54 & 56 & 60 & 64 \\
10 & - & - & - & 32 & 36 & 42 & 44 & 46 & 50 & 52 & 58 & 62 & 64 & 70 \\
11 & - & - & - & - & 40 & 42 & 50 & 52 & 54 & 60 & 64 & 68 & 70 & 80 \\
12 & - & - & - & - & - & 46 & 52 & 62 & 62 & 68 & 74 & 78 & 82 & 86 \\
13 & - & - & - & - & - & - & 58 & 64 & 68 & 76 & 80 & 86 & 92 & 98 \\
14 & - & - & - & - & - & - & - & 68 & 74 & 80 & 88 & 92 & 96 & $\geq 104$ \\
15 & - & - & - & - & - & - & - & - & 88 & 90 & 96 & 104 & 108 & $\geq 116$ \\
16 & - & - & - & - & - & - & - & - & - & 98 & 106 & 112 & $\geq 120$ & $\geq 124$ \\
17 & - & - & - & - & - & - & - & - & - & - & 110 & 120 & $\geq 126$ & $\geq 132$ \\
18 & - & - & - & - & - & - & - & - & - & - & - & 126 & $\geq 134$ & $\geq 140$ \\
19 & - & - & - & - & - & - & - & - & - & - & - & - & $\geq 144$ & $\geq 150$ \\
20 & - & - & - & - & - & - & - & - & - & - & - & - & - & $\geq 160$ \\
\bottomrule
\end{tabular}
\caption{Knights and Liars numbers and lower bounds for $G_{m,n}$ for $7 \leq m \leq n \leq 20$.}
\label{twodim}
\end{table}
\begin{table}[H]
\center
\begin{tabular}{c|cccccccccc}
\toprule
$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\midrule
$\kl([n]^3)$ & 1 & 0 & 0 & 8 & 16 & 24 & 64 & 112 & $\geq 160$ & $\geq 216$ \\
$\kl([n]^4)$ & 1 & 6 & 0 & 16 & 16 & 168 & $\geq 256$ & ? & ? & ? \\
$\kl([n]^5)$ & 1 & 0 & 0 & 32 & 128 & $\geq 256$ & ? & ? & ? & ? \\
$\kl([n]^6)$ & 1 & 40 & 0 & 64 & 512 & ? & ? & ? & ? & ? \\
\bottomrule
\end{tabular}
\caption{Knights and Liars numbers for higher-dimensional grids.}
\label{highdim}
\end{table}
\begin{figure}[H]
\centering
\includegraphics{figures/4cube.eps}
\caption{A red-balanced coloring of the 4-dimensional hypercube with six red vertices.}
\label{4cube}
\end{figure}
We give some Knights and Liars numbers for two-dimensional torus grid graphs in Table \ref{2dtorusnumbers}.
As discussed in Section \ref{problemformulation}, two-dimensional torus grid graphs whose interval-sizes
are both multiples of three admit a red-balanced coloring in which two thirds of all vertices are red.
The corresponding Knights and Liars numbers are marked in bold.
\begin{table}[H]
\footnotesize
\center
\begin{tabular}{c|cccccccccccccccccc}
\toprule
$m/n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\
\midrule
1 & 1 & 0 & 2 & 0 & 0 & 4 & 0 & 0 & 6 & 0 & 0 & 8 & 0 & 0 & 10 & 0 & 0 & 12 \\
2 & - & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
3 & - & - & \textbf{6} & 4 & 5 & \textbf{12} & 7 & 14 & \textbf{18} & 18 & 20 & \textbf{24} & 24 & 26 & \textbf{30} & 30 & 32 & \textbf{36} \\
4 & - & - & - & 6 & 6 & 12 & 10 & 20 & 12 & 18 & 16 & 24 & 18 & 32 & 22 & 40 & 24 & 38 \\
5 & - & - & - & - & 15 & 10 & 12 & 14 & 15 & 30 & 18 & 20 & 22 & 24 & 45 & 28 & 29 & 30 \\
6 & - & - & - & - & - & \textbf{24} & 14 & 28 & \textbf{36} & 36 & 40 & \textbf{48} & 48 & 52 & \textbf{60} & 60 & 64 & \textbf{72} \\
7 & - & - & - & - & - & - & 22 & 20 & 29 & 29 & 32 & 32 & 36 & 63 & 46 & 46 & 50 & 58 \\
8 & - & - & - & - & - & - & - & 40 & 42 & 36 & 46 & 60 & 48 & 64 & 70 & 80 & 74 & 84 \\
9 & - & - & - & - & - & - & - & - & \textbf{54} & 54 & 60 & \textbf{72} & 72 & 78 & \textbf{90} & 90 & 96 & \textbf{108} \\
10 & - & - & - & - & - & - & - & - & - & 60 & 46 & 72 & 64 & 68 & 90 & 82 & 82 & 108 \\
11 & - & - & - & - & - & - & - & - & - & - & 77 & 80 & 70 & 86 & 100 & 92 & 106 & 120 \\
12 & - & - & - & - & - & - & - & - & - & - & - & \textbf{96} & 96 & 104 & \textbf{120} & 120 & 128 & \textbf{144} \\
13 & - & - & - & - & - & - & - & - & - & - & - & - & 104 & 88 & 120 & $\geq 102$ & $\geq 110$ & 144 \\
14 & - & - & - & - & - & - & - & - & - & - & - & - & - & 126 & 130 & 128 & 138 & 156 \\
15 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & \textbf{150} & 150 & 160 & \textbf{180} \\
16 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & 160 & $\geq 152$ & 180 \\
17 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & 187 & 192 \\
18 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & \textbf{216} \\
\bottomrule
\end{tabular}
\caption{Knights and Liars numbers and lower bounds for $\Tor_{m,n}$ for $3 \leq m \leq n \leq 18$.}
\label{2dtorusnumbers}
\end{table}
We also calculated Knights and Liars numbers and lower bounds for the
three-dimensional torus grid graphs $\Tor_{n,n,n}$ for $1 \leq n \leq 5$.
The numbers are listed in Table \ref{3dtornusnumbers}.
\begin{table}[H]
\center
\begin{tabular}{cc}
\toprule
$n$ & $\kl(\Tor_{n,n,n})$ \\
\midrule
1 & 0 \\
2 & 0 \\
3 & 18 \\
4 & 40 \\
5 & $\geq 52$ \\
\bottomrule
\end{tabular}
\caption{Knights and Liars numbers for the three-dimensional torus grid graphs $\Tor_{n,n,n}$ for $n = 1, \ldots, 5$}
\label{3dtornusnumbers}
\end{table}
For $n \geq 1 $, let $T_n$ denote the triangular grid graph. The triangular grid graph $T_n$
is the graph whose vertices are the triples $(i,j,k)$ with $i,j,k \geq 0$ and $i+j+k = n$ and whose edges are the pairs of
vertices whose sum of absolute differences of coordinates is two \cite[Ex.\ 8.3.22, pp.\ 390--391]{West2000}.
We calculated the Knights and Liars numbers $\kl(T_n)$ for $1 \leq n \leq 100$
and observed that $\kl(T_n)$ is equal
to $\seqnum{A007980}(n)$ for these values of $n$.
Table \ref{triangularnumbers} lists the first 40 Knights and Liars numbers of the triangular grid graphs.
The sequence \seqnum{A007980} is defined as the
expansion of
$$\frac{1+x^2}{(1-x)^2(1-x^3)}$$
and has a multitude of other interpretations. For all $n \geq 1$, we have
$\seqnum{A007980}(n) = \left\lceil\frac{(n+1)(n+2)}{3}\right\rceil$,
as given by Paul Boddington on the OEIS page of the sequence.
For all $n \leq 100$, we found red-balanced colorings with the maximum possible number of red vertices,
in which every blue vertex has red neighbors only, leading to the aesthetically pleasing pattern
shown in the left coloring of Figure \ref{trianggrid}.
For some $n$, we searched for---and found---alternative red-balanced colorings with the maximum possible number of red vertices, for
which there are blue vertices with blue neighbors. The right coloring of Figure \ref{trianggrid}
is an example of such a coloring.
\begin{figure}[H]
\centering
\begin{subfigure}{.40\textwidth}
\centering
\includegraphics{figures/tri_16_1.eps}
\end{subfigure}%
\begin{subfigure}{.40\textwidth}
\centering
\includegraphics{figures/tri_16_2.eps}
\end{subfigure}%
\caption{Two different red-balanced colorings of the triangular grid graph $T_{16}$ with the maximum possible number
of red vertices.}
\label{trianggrid}
\end{figure}
\begin{table}[H]
\center
\begin{tabular}{cc|cc|cc|cc|cc}
\toprule
$n$ & $\kl(T_n)$ & $n$ & $\kl(T_n)$ & $n$ & $\kl(T_n)$ & $n$ & $\kl(T_n)$ & $n$ & $\kl(T_n)$ \\
\midrule
1 & 2 & 9 & 37 & 17 & 114 & 25 & 234 & 33 & 397 \\
2 & 4 & 10 & 44 & 18 & 127 & 26 & 252 & 34 & 420 \\
3 & 7 & 11 & 52 & 19 & 140 & 27 & 271 & 35 & 444 \\
4 & 10 & 12 & 61 & 20 & 154 & 28 & 290 & 36 & 469 \\
5 & 14 & 13 & 70 & 21 & 169 & 29 & 310 & 37 & 494 \\
6 & 19 & 14 & 80 & 22 & 184 & 30 & 331 & 38 & 520 \\
7 & 24 & 15 & 91 & 23 & 200 & 31 & 352 & 39 & 547 \\
8 & 30 & 16 & 102 & 24 & 217 & 32 & 374 & 40 & 574 \\
\bottomrule
\end{tabular}
\caption{Knights and Liars numbers for triangular grid graphs $T_n$ for $1 \leq n \leq 40$.}
\label{triangularnumbers}
\end{table}
For $n \geq 1$, let $\mathcal{B}_n$ denote the undirected graph corresponding to the
transitive closure of the boolean lattice. The set of vertices of
$\mathcal{B}_n$ is the powerset of $\{1,\ldots,n\}$ and two sets $A \neq B$ form an edge
if $A \subset B$ or $B \subset A$.
Table \ref{booleannumbers} lists the Knights and Liars numbers of $\mathcal{B}_n$ for $1 \leq n \leq 6$.
Figure \ref{subsetcolors6} shows the 34 red vertices in the red-balanced coloring of $\mathcal{B}_6$
we found. We omit curly brackets and commas to make the representation more compact.
We were not able to find a red-balanced coloring of $\mathcal{B}_7$ with at least one red vertex.
It remains open whether $\kl(\mathcal{B}_7) > 0$.
\begin{table}[H]
\center
\begin{tabular}{cc}
\toprule
$n$ & $\kl(\mathcal{B}_n)$ \\
\midrule
1 & 0 \\
2 & 0 \\
3 & 6 \\
4 & 0 \\
5 & 18 \\
6 & 34 \\
\bottomrule
\end{tabular}
\caption{Knights and Liars numbers $\kl(\mathcal{B}_n)$ for $n = 1, \ldots, 6$}
\label{booleannumbers}
\end{table}
\begin{figure}[H]
\centering
1 \ \
2 \ \
3 \ \
4 \ \
5 \ \ \\
13 \ \
16 \ \
24 \ \
25 \ \
34 \ \
56 \ \ \\
123 \ \
125 \ \
135 \ \
145 \ \
146 \ \
156 \ \
234 \ \
235 \ \
236 \ \
246 \ \
346 \ \
456 \ \ \\
1236 \ \
1245 \ \
1246 \ \
1345 \ \
2356 \ \
3456 \ \ \\
12346 \ \
12356 \ \
12456 \ \
13456 \ \
23456
\caption{The 34 red vertices in a best-possible red-balanced coloring of $\mathcal{B}_6$.}
\label{subsetcolors6}
\end{figure}
\section{The Knights and Liars problem is \NP-complete}
\label{npcomplete}
Let \textsc{KL} be the decision problem of deciding whether a given graph has a red-balanced coloring
in which at least $k$ vertices are red.
In order to make this section self-contained, we repeat the definition of red-balanced.
A \emph{red-balanced} coloring of a graph $G$ is a mapping $f: V(G) \rightarrow \{\text{red}, \text{blue}\}$,
such that for each red vertex, exactly half of its neighbors
are red, and for each blue vertex, \emph{not} exactly half of its neighbors
are red.
\begin{problem}
\problemtitle{\textsc{KL}}
\probleminstance{A graph $G$ and an integer $k$.}
\problemquestion{Does a red-balanced coloring of $G$ with at least $k$ red vertices exist?}
\end{problem}
In Theorem \ref{npctheorem}, we prove that \text{KL} is \NP-complete.
To show \NP-hardness we will give a polynomial-time reduction from
the \emph{exact cover by 3-sets} (\textsc{X3C})
problem---which Karp \cite{Karp1972} proved to be \NP-complete---to \textsc{KL}.
\begin{problem}
\problemtitle{\textsc{X3C}}
\probleminstance{A set $U$ whose cardinality is a multiple of three,
and a set $\mathcal{F}$ of 3-subsets of $U$.}
\problemquestion{Does a family $S \subseteq \mathcal{F}$
with $\dot{\bigcup}_{D \in S} D = U$ exist?}
\end{problem}
\begin{theorem}
\label{npctheorem}
The decision problem \textup{\textsc{KL}} is \NP-complete.
\begin{proof}
Clearly, whether a given coloring is red-balanced can be verified
in polynomial time, and it follows that \textsc{KL} is in $\text{NP}$.
To show that \textsc{KL} is \NP-hard, we give a polynomial-time reduction from \textsc{X3C} to \textsc{KL}.
Let $(U, \mathcal{F})$ be a problem instance of \textsc{X3C}.
We will define a problem instance $(G,k)$ of \textsc{KL},
such that $\textsc{X3C}(U, \mathcal{F})$ has
an affirmative answer if and only if $\textsc{KL}(G,k)$ does.
\vspace{0.25em}
\emph{Construction of the \textup{\textsc{KL}} instance.}
We construct an instance $(G,k)$ for \textsc{KL}, by starting from the empty graph $G$.
In this proof we will call vertices of degree one \emph{leaves} and all other vertices
\emph{inner} vertices. In figures sketching parts of the construction, we will depict
leaf vertices of $G$ as blue, because they must be blue in any red-balanced coloring of $G$.
Let $T$ be the graph consisting of a cycle of length three, in which each vertex
is connected to three leaf vertices.
For every $3$-set $X \in \mathcal{F}$, we add a copy $T_X$ of $T$ to $G$
and identify each element $a \in X$ with a unique inner vertex of $T_X$,
by giving the name $(a, X)$ to that vertex.
Figure \ref{cycles} depicts this construction.
\begin{figure}[H]
\centering
\includegraphics{figures/triangle.eps}
\caption{For each $X \in \mathcal{F}$, we add a copy $T_X$ of the graph $T$ to $G$.}
\label{cycles}
\end{figure}
Let $M = \max\{|U|, |\mathcal{F}|\}$.
We define $LC$ (short for ``large cycle'') to be the graph
consisting of a cycle of $M^2 + 3M$
vertices,
in which one of the vertices is connected to three leaf vertices,
and all other vertices are connected to two leaf vertices.
For each $u \in U$, we add a copy $LC_u$ of $LC$ to $G$.
Figure \ref{large_cycle} depicts this construction.
For each $u \in U$,
we add an auxiliary vertex $Z_u$
to $G$. This vertex acts as an intermediate connection point between $LC_u$
and each of the subgraphs $T_X$ for which $u \in X$.
We add an edge between the three-leaf-vertex of $LC_u$
and $Z_u$.
We add edges between $Z_u$ and each of the vertices $(u, X^{(1)}), \ldots, (u, X^{(m)})$,
where $X^{(1)}, \ldots, X^{(m)}$ are the $3$-sets containing $u$.
Note that $Z_u$ has exactly one neighbor in each of the subgraphs $T_{X^{(1)}}, \ldots, T_{X^{(m)}}$.
If $1 \leq m \leq 2$, we connect $3-m$ new leaf vertices to $Z_u$. If $m \geq 3$,
we add $m-3$ copies of the graph $K_2$ to $G$ and add edges between $Z_u$ and one of the vertices
of each copy of $K_2$.
Figure \ref{connections} sketches this construction for the case $m \geq 3$.
\begin{figure}[H]
\centering
\includegraphics{figures/lc.eps}
\caption{For each $u \in U$, we add a copy $LC_u$ of the graph $LC$ to $G$. The graph $LC$ consists of $M^2 + 3M$
inner vertices.}
\label{large_cycle}
\end{figure}
\begin{figure}[H]
\centering
\includegraphics{figures/connections.eps}
\caption{Sketch showing how the subgraph $LC_u$ is
connected to each of the subgraphs $T_{X^{(1)}}, \ldots, T_{X^{(m)}}$
for the case $m\geq3$.}
\label{connections}
\end{figure}
We count the number of inner vertices of $G$ that are not part of a copy of $LC$
and show that this number is strictly bounded from above by $M^2 + 3M$.
For each $X \in \mathcal{F}$,
there are three inner vertices in the subgraph $T_X$.
For each $u \in U$, the vertex $Z_u$ is an inner vertex, and is connected to
at most $|\mathcal{F}| - 3$ copies of $K_2$ (this upper bound is reached when $u$ is member of every set in $\mathcal{F}$),
each having an inner vertex in $G$.
The number of inner vertices not part of a copy of $LC$ is thus bounded by
\begin{equation}
\label{upperbound}
3 |\mathcal{F}| + |U| \cdot \left(|\mathcal{F}| - 2 \right) < M^2 + 3M.
\end{equation}
We set
$ k = \left\vert U \right\vert \cdot \left( M^2 +3 M \right)$.
The motivation behind this choice of $k$ is that a red-balanced coloring of $G$ can only
have at least $k$ red vertices if all inner vertices of all copies of $LC$ in $G$ are colored red. This
is explained in more detail in the second part of the proof.
\vspace{0.25em}
\emph{Equivalence of the problem instances.}
We claim that $G$ admits a red-balanced coloring with at least $k$ red vertices, \emph{if and only if}
$(U, \mathcal{F})$ has an exact $3$-cover.
In any red-balanced coloring of $G$, the inner vertices of a copy of $LC$ are
monochromatic (all blue or all red).
To see this, note that if an inner vertex of a copy of $LC$ is red,
then both its inner-vertex-neighbors must be red as well.
By the same argument, the inner vertices of a copy of $T$ are monochromatic in any red-balanced coloring.
First, consider the case where an exact $3$-cover $\mathcal{S}$ for the instance $(U, \mathcal{F})$ exists.
We construct a red-balanced coloring of $G$
with more than $k$ red vertices.
We color all leaves blue.
For every $u \in U$, we color $Z_u$ and all inner vertices of $LC_u$ red.
For every set $X \in \mathcal{S}$, we color all inner vertices of $T_X$ red
and for every set $X \in \mathcal{F} \setminus \mathcal{S}$, we color all inner vertices of $T_X$ blue.
If $u$ is member of at least three sets in $\mathcal{F}$, the vertex $Z_u$ is connected to
a number of copies of $K_2$. In each such copy of $K_2$, we color the vertex connected to $Z_u$ red.
The number of red vertices in this coloring exceeds $k$, because there are
$k = \left\vert U \right\vert \cdot \left( M^2 + 3M \right)$ red vertices
within the copies of $LC$ alone.
We show that this coloring is red-balanced, by checking
every inner vertex of $G$.
\begin{itemize}
\item For each $u \in U$, the two-leaf inner vertices of $LC_u$ are red and have
two red neighbors (adjacent inner vertices in $LC_u$) and two blue neighbors (leaves).
The three-leaf inner vertex of $LC_u$ is red and has three
red neighbors (the vertex $Z_u$ and two adjacent inner vertices in $LC_u$) and three blue neighbors (leaves).
\item For each $u \in U$, let $X^{(1)}, \ldots X^{(m)}$ be the $3$-sets containing $u$.
The vertex $Z_u$ is red. If $1 \leq m \leq 2$, $Z_u$ has two
red neighbors (the three-leaf-vertex of $LC_u$ and $(u,X)$,
where $X \in \mathcal{S}$ is the unique set in $\mathcal{S}$ containing $u$)
and two blue neighbors ($3-m$ leaves and the $m-1$ vertices $(u,X)$ for which $X \notin \mathcal{S}$).
If $m \geq 3$, $Z_u$ has $m-1$ red neighbors
($m-3$ vertices in the copies of $K_2$ connected to $Z_u$, the three-leaf-vertex of $LC_u$ and
$(u,X)$, where $X \in \mathcal{S}$ is the unique set in $\mathcal{S}$ containing $u$) and $m-1$
blue neighbors (the vertices $(u,X)$ for which $X \notin \mathcal{S}$).
\item Each inner vertex $(u, X)$ for which $u \in X \in \mathcal{S}$, is red and
has three red neighbors (the vertex $Z_u$ and two adjacent inner vertices in $T_X$)
and three blue neighbors (leaves).
Each inner vertex $(u, X)$ for which $u \in X \notin \mathcal{S}$,
is blue and has one red neighbor (the vertex $Z_u$) and five blue neighbors
(three leaves and two adjacent inner vertices in $T_X$).
\end{itemize}
Next, consider the case where $G$ has a red-balanced coloring with at least
$k$ red vertices.
We show that the sets $X \in \mathcal{F}$ for which the inner vertices of the subgraph $T_X$
are (all) red in this coloring form an exact $3$-cover of $\mathcal{F}$.
Because of the bound \eqref{upperbound}, and because each copy of $LC$ is monochromatic,
all inner vertices of each copy of $LC$ are red
(if a copy of $LC$ was blue,
there would not be enough inner vertices of $G$ left to exceed $k$ red vertices in $G$).
It follows that, in particular, for each $u \in U$, the
three-leaf vertex of $LC_u$ is red. This further implies that
$Z_u$ is red (because the three-leaf vertex of $LC_u$ has an equal number of red and blue neighbors).
Let again $X^{(1)}, \ldots, X^{(m)}$ denote the sets containing $u$.
If $m \geq 3$, the vertex $Z_u$ is connected to $3-m$ copies of $K_2$. The inner vertices of these
copies are red, because they have one blue neighbor (a leaf) and one red neighbor (the vertex $Z_u$).
We show that \emph{exactly one} of the vertices
$(u,X^{(1)}), \ldots, (u,X^{(m)})$ is red.
Since $Z_u$ is red, $Z_u$ has an equal number of red and blue neighbors.
We count the red and blue neighbors of $Z_u$, excluding the vertices $(u,X^{(1)}), \ldots, (u,X^{(m)})$:
\begin{itemize}
\item If $m=1$, the vertex $Z_u$ has two blue neighbors (two leaf vertices) and one red neighbor (the three-leaf vertex in $LC_u$).
\item If $m=2$, the vertex $Z_u$ has one blue neighbor (a leaf vertex) and one red neighbor (the three-leaf vertex in $LC_u$).
\item If $m \geq 3$, the vertex $Z_u$ has no blue neighbors and $m-2$ red neighbors
(the three-leaf vertex in $LC_u$ and $m-3$ in the the copies of $K_2$ connected to $Z_u$).
\end{itemize}
In all cases, for $Z_u$ to have an equal number of red and blue neighbors,
exactly one of the vertices $(u,X^{(1)}), \ldots, (u,X^{(m)})$ must be red.
It follows from the fact that for each $X \in \mathcal{F}$, the inner vertices of $T_X$ are monochromatic,
that exactly one of the subgraphs $T_{X^{(1)}}, \ldots, T_{X^{(m)}}$ has red inner vertices.
This means that for each $u\in U$, there exists exactly one set $X \in \mathcal{F}$ with $u \in X$, such
that the inner vertices of $T_X$ are red. It follows that the family of sets $X$ for which
the inner vertices of $T_X$ are red form an exact $3$-cover of $(U, \mathcal{F})$.
\end{proof}
\end{theorem}
Gonzales \cite{Gonzales1985} showed that the exact cover by $3$-sets problem remains \NP-complete
when restricted such that each element from the ground set appears in exactly three $3$-sets.
It follows from the construction in the proof of Theorem \ref{npctheorem},
that the decision problem \textsc{KL} remains \NP-complete when restricted to graphs
with maximum degree six.
Dyer and Frieze \cite{Dyer1983} showed that Planar \textsc{X3C} (i.e., \textsc{X3C} restricted such that
the bipartite incidence graph between universe set $U$ and set family $\mathcal{F}$ is planar) is \NP-complete.
It follows that \textsc{KL} remains \NP-complete when restricted to planar graphs.
This observation is due to Wulf \cite{WulfPersonal}.
\section{Open problems and questions}
\label{openproblems}
We give a number of open problems and questions we encountered,
which we hope will spark interest for future research on this topic.
\begin{enumerate}
\item Chu \cite{Chu2012} computed values of the maximum density still life problem for small $n$
by re-formulating the problem in terms of assigning wastage-scores to all possible
$3 \times 3$ sub-patterns in a still life. Is a similar formulation possible
for the Knights and Liars problem on square grids?
\item The decision problem discussed in Section \ref{npcomplete} remains \NP-complete when restricted
to planar graphs and graphs with maximum degree six. Investigate for which other graph classes the problem remains \NP-complete.
Is the case $k=1$---i.e., the problem of deciding whether a graph has a red-balanced coloring with at least one red vertex---\NP-complete (suggested by the anonymous referee)?
Is the problem restricted to sub-graphs of (two-dimensional) grid graphs \NP-complete (suggested by Stefan Lendl)?
Is the chromatic number or chromatic index related to the hardness of the problem?
\item In Section \ref{exactresults} we observed that the sequence of Knights and Liars numbers
of the triangular grid graphs equals the sequence \seqnum{A007980} for the initial 100 values.
Find a nice argument to show that this holds for all $n \geq 1$.
\item Study the generalization of the Knights and Liars problem to
directed graphs, in which the directed Knights and Liars number is
the maximum number of red vertices in a red-blue coloring such that for each red vertex, exactly
half of its out-neighbors are red, and for each blue vertex, not exactly half of its out-neighbors are red.
One can also ask for an edge-orientation of an undirected graph, such
that the directed Knights and Liars number is maximized.
\item For the $8$-dimensional hypercube $Q_8 = [2]^8$, we were not able to determine the value of
$\kl(Q_{8})$.
It would be of interest to see whether combinatorial arguments
can be used to improve the bound $72 \leq \kl(Q_{8}) \leq 165$, which we obtained using the integer programming
techniques described in Section \ref{ipsection}.
\item We were not able to find a non-trivial red-balanced coloring (i.e., a coloring with at least one red vertex)
of the graph $\mathcal{B}_7$ (defined in Section \ref{exactresults}).
Does such a coloring exist?
\item In Section \ref{problemformulation} we gave an example of a $4$-regular graph on eight
vertices with Knights and Liars number zero. Do arbitrarily large connected $k$-regular graphs with
Knights and Liars number zero exist for all $k \geq 2$?
\end{enumerate}
\section{Acknowledgments}
We would like to thank the anonymous referee for their helpful comments and suggestions and
for pointing us towards related literature in the field of still lifes. Without these
comments this paper would not be complete.
\begin{thebibliography}{9}
\bibitem{WinningWays}
E.\ R.\ Berlekamp, J.\ H.\ Conway, and R.\ K.\ Guy,
{\it Winning Ways for Your Mathematical Plays, Volume 2: Games in Particular},
Academic Press, 1982.
\bibitem{Bosch1999}
R.\ Bosch,
Integer programming and Conway's Game of Life,
{\it SIAM Rev.} {\bf 41} (1999),
594--604.
\bibitem{Bosch2000}
R.\ Bosch,
Maximum density stable patterns in variants of Conway's Game of Life,
{\it Oper.\ Res.\ Lett.} {\bf 27} (2000),
7--11.
\bibitem{Chu2012}
G.\ Chu and P.\ J.\ Stuckey,
A complete solution to the maximum density still life problem,
{\it Artificial Intelligence} {\bf 184-185} (2012),
1--16.
\bibitem{COINOR}
The COIN-OR Foundation,
Computational Infrastructure for Operations Research (COIN-OR), 2020,
\url{https://www.coin-or.org}.
\bibitem{Dyer1983}
M.\ E.\ Dyer and A.\ M.\ Frieze,
Planar 3DM is NP-complete,
{\it J.\ Algorithms} {\bf 7} (1986),
174--184.
\bibitem{Elkies1998}
N.\ D.\ Elkies,
The still-life density problem and its generalizations,
in P.\ Engel and H.\ Syta, eds., {\it Voronoi's Impact on Modern Science, Book I},
Institute of Math., Kyiv,
1998,
pp.\ 228--253.
\bibitem{Gonzales1985}
T.\ F.\ Gonzalez,
Clustering to minimize the maximum intercluster distance,
{\it Theoret.\ Comput.\ Sci.} {\bf 38} (1985),
293--306.
\bibitem{Gurobi}
Gurobi Optimization, LLC,
Gurobi Optimizer Reference Manual,
2021, \\
\url{https://www.gurobi.com}.
\bibitem{Karp1972}
R.\ M.\ Karp, Reducibility among combinatorial problems,
in R.\ E.\ Miller and J.\ W.\ Thatcher, eds., {\it Complexity of Computer Computations},
Plenum Press,
1972,
pp.\ 85--103.
\bibitem{LetskoMM140}
V.\ Letsko, Mathematical Marathon 140,
Volgograd State Pedagogical University,
2020, \\
\url{http://www-old.fizmat.vspu.ru/doku.php?id=marathon:problem_140}.
\bibitem{SloaneOEIS}
OEIS Foundation Inc.\ (2020),
The On-Line Encyclopedia of Integer Sequences, \\
\url{https://oeis.org}.
\bibitem{TabatabaiGithub}
P.\ Tabatabai, Knights and Liars, Github repository,
2021, \\
\url{https://github.com/tabatabai/knights-and-liars}.
\bibitem{West2000}
D.\ B.\ West,
{\it Introduction to Graph Theory},
Second edition,
Prentice Hall,
2000.
\bibitem{WulfPersonal}
L.\ Wulf,
\emph{Personal communication}, 2021.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 05C15; Secondary 00A08, 90C10, 68Q25, 68Q80.
\noindent \emph{Keywords: }
coloring, partition, grid, graph, maximization, integer programming, computational complexity, NP-completeness, cellular automata.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A007980} and \seqnum{A289362}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 19 2020;
revised versions received March 21 2021; April 26 2021.
Published in {\it Journal of Integer Sequences}, April 26 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}