#  Ramsey Scheme Applied to String Theoretical Processes

Salman Sajad Wani  Department of Physics and Engineering, Istanbul, Technical
University, 34469, Istanbul, Turkey  Canadian Quantum Research Center
204-3002, 32 Ave Vernon, BC V1T 2L7 Canada  Arshid Shabir  Department of
Physics, NIT Srinagar, Kashmir 190006 India  Mir Faizal  Canadian Quantum
Research Center 204-3002, 32 Ave Vernon, BC V1T 2L7 Canada  Department of
Physics and Astronomy, University of Lethbridge, Lethbridge, AB T1K 3M4,
Canada  Seemin Rubab  Department of Physics, NIT Srinagar, Kashmir 190006
India

###### Abstract

In this letter, we analyze the evolution of physical quantities due to the
interaction of strings with background fields. We will obtain the
characteristic function for such a string theoretical process. This will be
done by generalizing the Ramsey scheme to world-sheet, and using it to obtain
the information about the evolution of quantity in a string theoretical
process, without making two-point measurements. We will also use the
characteristic function to obtain the average of the difference between the
initial and final values of such a quantity. Finally, using the characteristic
function, we calculate fisher information for the difference of such a
quantity.

##  I Introduction

It may be noted that ordinary particles are described by a number of
quantities, like mass and spin, and these quantities are not dynamically
obtained in quantum field theories. However, in string theory, these can be
obtained from the dynamics of world-sheet [1, 2]. This is because strings have
an extended structure, and have their own internal dynamics associated with
that internal structure. So, unlike particles in ordinary quantum field theory
(which have no internal dynamics and are just points in space-time), the
internal dynamics of a world-sheet of string theory are represented by a
conformal field theory. Thus, such quantities in ordinary quantum field theory
can be dynamically calculated using this conformal field theory describing the
world-sheet dynamics of string theory. In string theory, there are background
fields. These fields can interact with the strings, and change their
oscillatory modes [3, 4, 5, 6]. The change in the oscillatory modes would also
change the value of quantities, such as mass and spin, which can be obtained
dynamically from the world-sheet dynamics. It is important to analyze the
change in the value of such quantities due to the interaction of strings with
background fields.

It is known that the change in a quantity due to the interaction of a system
with some external potential can be obtained using two-point measurement
scheme [7, 8]. In the two-point measurement scheme, a system interacts with a
field, and this changes the initial eigenvalues of an operator to final
eigenvalues. The difference between these two projective measurements of a
quantity, made at the beginning and end of such a process, are then used to
obtain the distribution function for the quantity [7, 8]. This difference is
the difference between the initial and final eigenvalues of the operator,
after the system has interacted with an external field. Such two projective
measurements cannot be made on a system with an intrinsic Lorentz structure,
due to problems like violation of locality and superluminal signals [9, 10,
11]. However, these problems can be resolved by using the Ramsey scheme [12,
13]. The Ramsey scheme has been applied to quantum field theory [14].

In this scheme, first an auxiliary qubit is coupled to the system, and then
the information about the system is transferred to the qubit. The information
about the system is obtained by making measurements on the qubit. The effects
of the evolution of the system by its interaction with an external field can
also be probed using this qubit. This is done by preparing the qubit in a
superposition of ground and excited states, and then transferring the
information about the characteristic function of the distribution to the state
of the qubit. This procedure can be used to obtain the information about the
change in the eigenvalues of an operator, without making projective
measurements. The Ramsey scheme has been used to obtain such a difference in
quantum field theory [14]. As the dynamics of the world-sheet of string theory
is represented by a conformal field theory, in this letter, we will generalize
the Ramsey scheme to string theory.

We will also analyze the flow of information on the world-sheet of strings.
This will be done by using quantum fisher information. In fact, quantum fisher
information can be used to analyze the behavior of those quantities, which are
not represented by a quantum operator [15, 16, 17, 18]. As the difference of
the initial and final values of a quantity, in a string theoretical process,
cannot be represented by a quantum operator, we will use quantum fisher
information to analyze its behavior. This quantum fisher information would be
obtained from the distribution of the difference between the initial and final
values of a given quantity. Here we point out that even though the original
quantity can be represented by a quantum operator, the change in the quantity
in a quantum process cannot be represented by any quantum operator. This is
similar to the Hamiltonian being a quantum operator, but quantum work (which
represents the change in the eigenvalues of the Hamiltonian in a quantum
process) cannot be represented by any operator [19, 20, 21, 22].

##  II String Theoretical Process

In this section, we will analyze string theoretical process in which a string
interact with a background field. To analyze such a process, we will start
from the free Polyakov action, which describes the world-sheet of bosonic
string theory

$\displaystyle{S}=\frac{1}{4\pi\alpha^{\prime}}\int
d\sigma^{2}\eta^{\alpha\beta}\partial_{\alpha}X_{\mu}\partial_{\beta}X^{\mu}.$
(1)

Here $\alpha^{\prime}$ is related to the length of string $l_{s}^{2}$. We can
apply the Neumann boundary conditions for open strings, and write

$\displaystyle X^{\mu}\left(\tau,\sigma\right)=x^{\mu}+l_{s}\tau
p^{\mu}+il_{s}\sum_{m\neq
0}\frac{1}{m}{{\alpha}}^{\mu}_{m}e^{-im\tau}cos(m\sigma).$ (2)

As string theory has a gauge degrees of freedom, we need to fix a guage before
quantizing it. This can be done using the BRST quantization in the conformal
gauge [23]. This is done by adding a gauge fixing term (conformal gauge) and a
ghost term to the Polyakov action. This new effective action obtained by the
sum of the original Polyakov action with the gauge fixing and ghost term is
invariant under BRST transformation. The physical states of the system are
then constructed using the Noether charge corresponding to this symmetry of
the effective action. This Noether change is called the BRST charge, $Q$, and
physical states satisfy $Q|\rm{phy}>=0$. However, as the BRST quantization in
conformal guage is equivalent to light-cone quantization [24, 25], we can use
analyze string states in light-cone [26, 27]. Furthermore, the covariant
string theory, splits into the light-cone string theory and trivial
excitations [28]. The other excitations which represent the ghost sector
decouple from the theory, and can be neglected in light-cone quantization [29,
30]. This is similar to the situation in ordinary electrodynamics, where the
ghost sector decouples from the theory, and can be neglected for perturbative
calculations [31]. Thus, it is possible to analyze string theory in light-cone
gauge [26, 27]. This finite field BRST transformation is not the symmetry of
the path integral measure, and the Jacobian of transformation can be used to
transform the generating functional from light-cone gauge to covariant gauge
[32, 33, 34, 35, 36, 37, 38, 39]. In fact, it has also been demonstrated that
finite field dependent BRST transformation can be used to obtain the
generating functional in light-cone gauge from the generating functional
conformal gauge [40]. Here again we observe that in the light-cone gauge the
gauge degrees of freedom are removed, and so the string theory can be
consistently quantized in it. This is done by first expressing the target
space coordinates as $\\{X^{+},X^{-},X^{i}\\}_{i=1}^{24}$, with
$X^{+}=(X^{0}+X^{25}),$ and $X^{-}=(X^{0}-X^{25})$. Then the unphysical
degrees of freedom are removed by observing that there are no oscillations in
the $X^{+}$ direction in In the light-cone gauge. Furthermore, the oscillation
in $X^{-}$ direction can be expressed in terms of other string oscillations,
and need not be separately analyzed. Thus, in the light-cone gauge, only the
string oscillations in the $\\{X^{i}\\}_{i=1}^{24}$ direction have to be
considered. The string algebra in these directions can be written as

$[\hat{\alpha}_{m}^{i},\hat{\alpha}_{n}^{j}]=m\eta^{ij}\delta_{m+n,0}.$ (3)

This can be written as $[\hat{\alpha}_{m}^{i},\hat{\alpha}_{-m}^{i}]=m$ for
$n=-m$ and $(\hat{\alpha}_{m}^{i})^{\dagger}=\hat{\alpha}_{-m}^{i}$ with
$\\{i,j\\}$, taking values in $\\{1,2,3,..,24\\}$.

We define a vacuum as $|0,p\rangle$ such that
$\hat{p}^{\mu}|0,p\rangle=p^{\mu}|0,pk\rangle$. Using this vacuum, we can
construct a state $|k,0\rangle$ from $\alpha_{k}|0,p\rangle$. We start by
constructing a string density matrix $\hat{\rho}$ from these string states as

$\hat{\rho}=\mathcal{N}\sum_{l}\sum_{k}d_{k}{d_{l}}^{*}|k;p\rangle\langle
l;p|,$ (4)

$\mathcal{N}=1/\sum_{k}|d_{k}|^{2}$where $\mathcal{N}$ is the normalization
constant. This string density state evolves from $\hat{\rho}(0)$ at time
$\tau=0$ to $\rho(t)$ at time $\tau=t$, such that

$\hat{\rho}(t)=\hat{U}(t)\hat{\rho}(0)\hat{U}^{\dagger}(t).$ (5)

Here $U$ is a suitable unitary operator, which evolves the initial string
density state to the final string density state [41, 42]. Such a unitary
evolution occur due to the interaction of string states by a background field.
Thus, for example, with a background field [3, 4, 5, 6]. The the Polyakov
action with a background $B^{\mu\nu}(X)$ field, gravitational field with
metric $G^{\mu\nu}(X)$, and dilaton field $\Phi(X)$ (which couples to the two-
dimensional world-sheet Ricci scalar $R$), can be written as

$\displaystyle{S}=\frac{1}{4\pi\alpha^{\prime}}\int
d\sigma^{2}\Big{[}\eta^{\alpha\beta}\left(G^{\mu\nu}(X)+iB^{\mu\nu}(X)\right)\partial_{\alpha}X_{\mu}\partial_{\beta}X_{\nu}+\alpha^{\prime}\Phi(X)R\Big{]}.$
(6)

Here the background field will interact with the string for a time $T$, where
$T$ would be defined in the target space. So, we can perturb this string with
a background field, and write the resulting total world-sheet Hamiltonian as

$\hat{H}=\tilde{H}_{0}+\tilde{H}_{I},$ (7)

where $\tilde{H}_{0}$ is the original free string Hamiltonian, and
$\tilde{H}_{I}$ is the interaction of the string fields with the background
field. Here we have assumed that the is time dependent, and we can separated
the temporal dependence of $\tilde{H}_{I}(\tau)$ into $\lambda\chi(\tau)$. We
can also extract a constant $\lambda$ from $\tilde{H}_{I}$, from the
interaction Hamiltonian, which would act as an effective coupling constant,
and write

$\tilde{H}_{I}=\lambda\chi(\tau)\int d\sigma\mathcal{H}(\sigma).$ (8)

Here we have chosen the gauge $\tau=T$, with $T$ being the time in target
spacetime. With this choice of gauge, we can view $\chi(\tau)$ as a switching
function, which turns the background fields on at $\tau>0$ and off at $\tau<t$
on the world-sheet. Furthermore, and $\mathcal{H}(\sigma)$ will act as the
smearing function representing the interaction. Now the interaction is turned
on at time $\tau>0$ and turned off at time $\tau=t$ such that
$\tilde{H}(0)=\tilde{H}_{0}$ and $\tilde{H}(t)=\tilde{H}_{0}$ as
$\tilde{H}_{I}(0)=\tilde{H}_{I}(t)=0$. So, using this interaction Hamiltonian
$\hat{H}$, we can write the unitary transformation $U$ as

$\hat{U}(t)=\mathcal{T}\exp{\left(-i\lambda\chi(\tau)\int
d\sigma\mathcal{H}(\sigma)\right)},$ (9)

where $\mathcal{T}$ denotes time ordering between $0<\tau<t$. Using the Dyson
expansion, we can express this unitary operator in terms of the a series as

$\hat{U}(\tau)=1+\hat{U}^{1}(\tau)+\hat{U}^{2}(\tau)+O(\lambda^{3}),$ (10)

where $\hat{U}^{1}(\tau)$ and $\hat{U}^{2}(\tau)$ are the first and second
order terms in the Dyson expansion.

We want to analyze the effect of such interaction on a quantity defined in
string theory. This quantity can be a quantity like the square of the total
mass $M^{2}$ of the string or the angular momentum of the string $J$. Both
these quantities are calculated from world-sheet dynamics as eigenvalues of
operators defined on world-sheet, i.e. $\hat{M}^{2}$ and $\hat{J}$. However,
they also have important physical implications for particle physics, which can
be observed in target space. Thus, even though such quantities can be
calculated from world-sheet, they have important physical significance in
target space, which can be tested in particle physics experiments. We could
develop the argument specifically for $M^{2}$ or $J$, but here we will keep
our argument general, and define a general operator on world-sheet as
$\hat{A}$. The argument can be applied to any such operator, which can be
obtained from world-sheet dynamics, such as $\hat{M}^{2}$ or $\hat{J}$.

As the string interacts with the background field, we expect its oscillations
to change. This would in turn change the value of quantities defined on the
world-sheet, such as $\hat{M}^{2}$ or $\hat{J}$. It would be important to
measure the change in such values. Usually, such a change would be expected to
be measured, by first making an measurement at $\tau=0$, then making the
string interact with a field, and finally making another measurement at
$\tau=t$. Even though this seems straightforward, it would in principle
involve making two projective measurements on world-sheet. The problem here is
that two such projective measurements cannot be made on a system with an
Lorentz structure due to problems like superluminal signals [9, 10], and
world-sheet of string has an intrinsic Lorentz structure build into it.
However, such problems can be resolved for systems with a Lorentz structure by
a scheme called the Ramsey scheme [12, 13]. The Ramsey scheme has already been
applied to quantum field theories [14]. As the world-sheet of string theory is
modeled by a conformal field theory, we propose that the change in the world-
sheet operator $\hat{A}$ can be obtained by using a string theoretical
generalization of the Ramsey scheme.

##  III Characteristic Function

We can construct the characteristic function for this process. As world-sheet
has a Lorentz structure on it, we can use the Ramsey scheme to obtain
information related to two world-sheet projective measurements. So, if
$|A_{i}\rangle$ are the initial eigenvectors of the general world-sheet
operator $|\tilde{A}_{i}\rangle$ with eigenvalues $\tilde{A}_{i}$. To obtain
the information about change in the eigenvalues of $\hat{A}$ due to its
interaction with the background field, we will now generalize Ramsey scheme
[12, 13] to string theory. This will be done by first expressing the world-
sheet operators using their eigenvectors and eigenvalues as

$\displaystyle\hat{A}(0)=\sum_{i}A_{i}|{A}_{i}\rangle\langle{A}_{i}|,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\hat{A}(t)=\sum_{j}\tilde{A}_{j}|{\tilde{A}}_{j}\rangle\langle{\tilde{A}}_{j}|.$
(11)

We can write the probability for measuring eigenvalue $A_{i}$ at time $\tau=0$
as $p^{0}_{i}=|\langle{A}_{i}|\rho|{A}_{i}\rangle|^{2}$. The eigenvectors of
$\hat{A}$ evolves from $|A_{i}\rangle$ to $|\tilde{A}_{l}\rangle$ due to the
interaction with the interaction with background field. As this evolution is
captured by the unitary transformation $\hat{U}$, we can also write the
conditional probability for measuring eigenvalue $\tilde{A}_{l}$, at time
$\tau=t$, if the initial eigenvalue was $A_{i}$ at time $\tau=0$ as
$p^{\tau}_{l|i}=\langle\tilde{A}_{j}|U|{A}_{i}\rangle|^{2}$. We can write the
difference between these initial and the final eigenvalues of $\hat{A}$ as

$\displaystyle\bar{A}_{i,j}=\tilde{A}_{j}-A_{i}.$ (12)

Using $p^{0}_{i}$ and $p^{\tau}_{l|i}$, we obtain the probability associated
with the occurrence of this difference $\bar{A}^{i,l}$ as

$\displaystyle p_{i,j}$ $\displaystyle=$ $\displaystyle
p^{0}_{i}p^{\tau}_{j|i}$ (13) $\displaystyle=$
$\displaystyle|\langle{A}_{i}|\rho|{A}_{i}\rangle|\langle\tilde{A}_{j}|U|{A}_{i}\rangle|^{2}.$

As we have the probabilities associated with the difference $\bar{A}_{i,l}$,
we can write the full probability distribution corresponding corresponding to
it. This can be done by defining a distribution variable $\mathcal{A}$, which
would correspond to different values of $\bar{A}_{i,l}$, if there was no
degeneracies. However, to account for degeneracies in the eigenvalues of
$\hat{A}$, we define the probability distribution as

$P(\mathcal{A})=\sum_{ij}p_{i,j}\delta(\mathcal{A}-\bar{A}_{i,j}).$ (14)

As the probability distribution for the variable $\mathcal{A}$ can be written
as $P(\mathcal{A})$, we can write the average value for $\mathcal{A}$ using
$P(\mathcal{A})$ as

$\displaystyle\bar{\mathcal{A}}=\int\sum_{ij}p_{i,j}\delta(\mathcal{A}-\bar{A}_{i,j})\mathcal{A}d\mathcal{A}.$
(15)

Using the expression for $p_{i,j}$ and integrating this expression, we obtain

$\displaystyle\bar{\mathcal{A}}$ $\displaystyle=$
$\displaystyle\sum_{ij}|\langle{A}_{i}|\rho|{A}_{i}\rangle|\langle\tilde{A}_{j}|U|{A}_{i}\rangle|^{2}\left[\tilde{A}_{j}(\tau)-A_{i}(0)\right].$
(16)

Now using $[\hat{\rho},\hat{A}]=0,$ and
$[\hat{A},\hat{U}^{\dagger}\hat{A}\hat{U}]=0$, we observe that

$\bar{\mathcal{A}}=\sum_{l}p_{l}(\tau)A_{l}{(\tau)}-\sum_{i}p_{i}(0)A_{i}{(0)},$
(17)

where $p_{l}(\tau)=\sum_{i}p_{i,l}(\tau)$ and $p_{i}(0)=\sum_{l}p_{i,l}(0)$.
We observe that
$\sum_{l}p_{l}(\tau)A_{l}{(\tau)}=tr[\mathcal{A}{(\tau)}\rho{(\tau)}]$ and
$\sum_{i}p_{i}(0)A_{i}{(0)}=tr[\mathcal{A}{(0)}\rho{(0)}]$, and so we can
write

$\bar{\mathcal{A}}=tr[\mathcal{A}{(\tau)}\rho{(\tau)}]-tr[\mathcal{A}{(0)}\rho{(0)}].$
(18)

We can define the corresponding characteristic function of $\mathcal{A}$ as

$\tilde{P}(\mu)=\int P(\mathcal{A})e^{i\mu\mathcal{A}}d\mathcal{A}=\langle
e^{i\mu\mathcal{A}}\rangle.$ (19)

Here $\mu$ is the parameter used in the Ramsey scheme. We first define an
string auxiliary qubit, such that its ground state is $|0\rangle$, and its
excited state is $|0\rangle$. This string auxiliary qubit is defined in such a
way, that it is capable of transferring information from a string density
matrix. This can be done by first coupling it to the string density state
$\rho(0)$. Initially both the string and qubit are in the ground state. So, we
can write the product state of the system as

$\hat{\rho}_{\text{tot}}=\hat{\rho}\otimes\hat{\rho}_{\text{aux}}.$ (20)

After coupling the auxiliary qubit to the string density state, we apply a
Hadamard operator to the qubit. Now the string interacts with the background
field, and this evolves the total state of the system by a unitary operator
[14]

$\hat{C}(\mu)=\hat{U}e^{-i\mu\hat{H}(0)}\otimes|0\rangle\langle
0|+e^{-i\mu\hat{H}(t)}\hat{U}\otimes|1\rangle\langle 1|.$ (21)

Using this unitary operator, the string qubit state can be expressed as

$\hat{\rho}_{\text{aux}}=\text{Tr}_{X}[\hat{C}(\mu)\hat{\rho}_{\text{tot}}\hat{C}^{\dagger}(\mu)].$
(22)

Here we have defined a string trace operation $\text{Tr}_{X}$, which traces
over the string states. After evolving the system, we apply a final Hadamard
operation to the qubit state, and extract the information about the evolution
of the system by the background field. This is done as we now have an
expression for $\hat{\rho}_{\text{aux}}$, whose explicit form will depend on
the precise form of the operator $\hat{A}$. This final expression for the
string auxiliary qubit $\hat{\rho}_{\text{aux}}$, can then be compared to the
general expression for $\hat{\rho}_{\text{aux}}$ as [12, 13]

$\hat{\rho}_{\text{aux}}=\frac{1}{2}\Big{\\{}\mathbb{1}+\text{Re}[\tilde{P}(\mu)]\hat{\sigma}_{z}+\text{Im}[\tilde{P}(\mu)]\hat{\sigma}_{y}\Big{\\}}~{}.$
(23)

This expression is general, and will also hold for this string theoretical
process. Thus, we can obtain $\tilde{P}(\mu)$ using a specific form of the
string auxiliary qubit. So, this characteristic function is obtained from the
string Ramsey scheme.

##  IV Fisher Information

We can use this characteristic function to analyze the behavior of physical
quantities due to such an interaction with background field. It can be used to
explicitly obtain the value of this average difference $\bar{\mathcal{A}}$ as

$\displaystyle\bar{\mathcal{A}}=i\frac{d}{d\mu}\tilde{P}(\mu).$ (24)

So, basically we start from initial world-sheet string states. Then we perturb
this system, and so this perturbation changes the string states. Then we
obtain the difference between the initial and final eigenvalues of
$\mathcal{A}$ using Ramsey scheme [12, 13]. Now if $\mathcal{A}$ does not
contain any information about string states, then this average difference will
vanish for such a string theoretical process, $\bar{\mathcal{A}}=0$.

The fisher information is used for a quantity, which is not represented by a
quantum operator [15, 16, 17, 18]. As the difference of two quantities during
a string theoretical process cannot be represented by a quantum operator, we
will use fisher information to analyze it. We can associate a parameter, say
$\mu$ with the change in a physical quantity $\mathcal{A}$. Here $\mathcal{A}$
is a quantity defined on world-sheet such as the change in the mass square or
spin of strings during a string theoretical process. We can then use this
parameter to obtain the fisher information associated with the change in that
physical quantity, during a string theoretical process. If there is no fisher
information, then the change in the quantity cannot have a physical meaning.
However, if there is a change in the fisher information, then we can assume
that the change in the physical quantity will have a physical meaning. We can
write the fisher information associated with $\mathcal{A}$ as

$\displaystyle F=\int P(\mathcal{A})\left|\frac{\partial}{\partial\mu}\log
P(\mathcal{A})\right|^{2}d\mathcal{A}.$ (25)

To analyze string theoretical processes on world-sheet, we need to analyze the
change of string states on the world-sheet. This change of string states can
be measured by measuring the change in a quantity on the world-sheet, if that
quantity contains information about string states of the world-sheet. Thus, we
would start by defining a quantity on the world-sheet, represented by an
operator $\mathcal{A}$, such that it contains information about world-sheet
string states. However, if the quantum fisher information does not vanish (and
so operator $\mathcal{A}$ contains information about string states), then we
can analyze a string theoretical process by measuring the change in the value
of $\mathcal{A}$ during such a process.

##  V Conclusion

It is possible to obtain quantities, like mass and spin dynamically from the
world-sheet dynamics of strings. It is also possible for strings to interact
with background fields. In this letter, we have investigated how such an
interaction will change the a physical quantity. This has been done by
constructing the characteristic function for such a string theoretical
process. We have argued that such a characteristic function cannot be
constructed using the usual two point measurements, as the world-sheet has an
intrinsic Lorentz structure. We have also resolved this problem by
generalizing the Ramsey scheme to world-sheet. This has been done by coupling
an string auxiliary qubit to a string density state. After the first Hadamard
operation, this combined system is evolved due to the interaction of a
background field. Then a second Hadamard gate is applied, and the information
about the process is extracted from the qubit. This is done without making two
point measurements. It is used to obtain the characteristic function for such
a process. Finally, using the characteristic function, we also obtain fisher
information for the difference between the initial and final values of a
quantity, in a string theoretical process.

It would be interesting to apply this formalism to specific operators defined
on the world-sheet of string theory, such as $\hat{M}^{2}$ or $\hat{J}$. Then
using a specific perturbation by a background field, we can explicitly obtain
the characteristic function for such operators. This can then be used to
analyze a change in their value, after the string has interacted with a
background field. It would be interesting to analyze the consequence of such
string theoretical processes. It is also possible to generalize this analysis
to thermal states. This can be done by using KMS state instead of vacuum
state.

## References

  * [1] S. Hellerman and I. Swanson, Phys. Rev. Lett. 114 111601 (2015).
  * [2] F. Rojas and C. B. Thorn, Phys. Rev. D 84, 026006 (2011).
  * [3] A. E. Lawrence and E. J. Martinec, Class. Quant. Grav. 13, 63-96 (1996).
  * [4] I. Bars and K. Sfetsos, Phys. Rev. D 46, 4510-4519 (1992).
  * [5] J. T. Liu and R. Minasian, Nucl. Phys. B 874, 413-470 (2013).
  * [6] M. Schnabl, JHEP 11, 031 (2000).
  * [7] S. Suomela, P. Solinas, J. P. Pekola, J. Ankerhold and T. Ala-Nissila, Phys. Rev. B 90, 094304 (2014).
  * [8] F. W. J. Hekking and J. P. Pekola, Phys. Rev. Lett. 111, 093602 (2013).
  * [9] M. Redhead, Found. Phys. 25, 123 (1995).
  * [10] D. M. T. Benincasa, L. Borsten, M. Buck, and F. Dowker, Class. Quantum Grav. 31, 075007 (2014).
  * [11] R. D. Sorkin, gr-qc/9302018 (1993).
  * [12] R. Dorner, S. R. Clark, L. Heaney, R. Fazio, J. Goold and V. Vedral, Phys. Rev. Lett. 110, 230601 (2013).
  * [13] L. Mazzola, G. D. Chiara and M. Paternostro, Int. J. Quantum Inf. 12, 1461007 (2014).
  * [14] A. Ortega, E. McKay, Á. M. Alhambra and E. Martín-Martínez, Phys. Rev. Lett. 122, 24, 240604 (2019).
  * [15] J. Liu, H. Yuan, X-M. Lu and X. Wang, J. Phys. A. Math. Theor. 53, 023001 (2020).
  * [16] A. T. Rezakhani, M. Hassani and S. Alipour, Phys. Rev. Lett. 109, 190404 (2012).
  * [17] Y. Yang, Phys. Rev. Lett. 123, 110501 (2019).
  * [18] B. M. Escher, L. Davidovich, N. Zagury and R. L. de Matos Filho Phys. Rev. Lett. 109, 190404 (2012).
  * [19] A. del Campo, I. L. Egusquiza, M. B. Plenio and S. F. Huelga Phys. Rev. Lett. 110, 050403 (2013).
  * [20] Erik Lucero, M. Hofheinz, M. Ansmann, Radoslaw C. Bialczak, N. Katz, Matthew Neeley, A. D. O’Connell, H. Wang, A. N. Cleland and John M. Martinis Phys. Rev. Lett. 100, 247001 (2008).
  * [21] L. Rigovacca, A. Farace, L. A. M. Souza, A. De Pasquale, V. Giovannetti and G. Adesso, Phys. Rev. A 95, 052331 (2017).
  * [22] R. Nichols, P. Liuzzo-Scorpo, P. A. Knott and G. Adesso, Phys. Rev. A 98, 012114 (2018).
  * [23] J. Bischoff, S. V. Ketov and O. Lechtenfeld, Nucl. Phys. B 438, 373 (1995).
  * [24] N. Ishibashi and K. Murakami, JHEP 06, 087 (2016).
  * [25] N. Ishibashi and K. Murakami, JHEP 09, 053 (2013).
  * [26] E. Smith, Nucl. Phys. B 382, 229-241 (1992).
  * [27] D. Tong, [arXiv:0908.0333 [hep-th]].
  * [28] H. Matsunaga, JHEP 04, 143 (2019).
  * [29] P. P. Srivastava and S. J. Brodsky, Phys. Rev. D 64, 045006 (2001).
  * [30] R. Bentin, [arXiv:hep-th/0310094 [hep-th]] .
  * [31] R. P. Malik, Mod. Phys. Lett. A 16, 477 (2001).
  * [32] S. Upadhyay, Phys. Lett. B 740, 341 (2015).
  * [33] S. Upadhyay, Phys. Rev. D 92, 065027 (2015).
  * [34] S. Upadhyay and B. P. Mandal, Eur. Phys. J. C 81, 279 (2021).
  * [35] S. Upadhyay, Int. J. Mod. Phys. A 30, 1550150 (2015).
  * [36] S. Upadhyay and B. P. Mandal, Phys. Lett. B 744, 231 (2015).
  * [37] S. Upadhyay, Annals Phys. 340, 110 (2014).
  * [38] S. Upadhyay, EPL 105, 21001 (2014).
  * [39] S. Upadhyay, EPL 104, 61001 (2014).
  * [40] V. K. Pandey and B. P. Mandal, EPL 122, 21002 (2018).
  * [41] S. Vinjanampathy and J. Anders. Contemp. Phys. 57, 545 (2016).
  * [42] M. Esposito, U. Harbola, and S. Mukamel, Rev. Mod. Phys. 81, 1665 (2009).


# Domination by kings is oddly even

Cristopher Moorea Stephan Mertensa,b

###### Abstract

The $m\times n$ king graph consists of all locations on an $m\times n$
chessboard, where edges are legal moves of a chess king. Let $P_{m\times
n}(z)$ denote its domination polynomial, i.e., $\sum_{S\subseteq V}z^{|S|}$
where the sum is over all dominating sets $S$. We prove that $P_{m\times
n}(-1)=(-1)^{\lceil m/2\rceil\lceil n/2\rceil}$. In particular, the number of
dominating sets of even size and the number of odd size differs by $\pm 1$.
This property does not hold for king graphs on a cylinder or a torus, or for
the grid graph. But it holds for $d$-dimensional kings, where $P_{n_{1}\times
n_{2}\times\cdots\times n_{d}}(-1)=(-1)^{\lceil n_{1}/2\rceil\lceil
n_{2}/2\rceil\cdots\lceil n_{d}/2\rceil}$.

##  1 Introduction

A placement of chess pieces on a chessboard is called _dominating_ if each
free square of the chessboard is under attack by at least one piece. chess
domination problems have been studied at least since 1862, when Jaenisch [1]
posed the problem of finding the minimum number of queens needed to dominate
the $8\times 8$ board. For queens, the answer is 5 [2]. For kings, the answer
is 9 (Fig. 1).

[setfen=8/1k2k2k/8/8/1k2k2k/8/8/1k2k2k - - - 0 0, label=false, showmover=false] |
---|---
Figure 1: Nine kings are required to dominate the $8\times 8$ chessboard. More
mathematically: the smallest dominating set of the king graph $K_{8\times 8}$
(right) has size $9$.

In the 20th century, the idea of domination entered graph theory [3]. A
dominating set in a graph $G=(V,E)$ is a subset $S\subseteq V$ of vertices
such that every node in $V$ is either contained in $S$ or has a neighbor in
$S$.

The link from chess to graph theory is given by graphs like the king graph
(Fig. 1). In this graph, which we call $K_{m\times n}$, the vertices represent
the squares of an $m\times n$ chessboard, and each edge represents a legal
move of a king. That is, $K_{m\times n}=(V,E)$ where $V=[m]\times[n]$ and
$((x,y),(x^{\prime},y^{\prime}))\in E$ if and only if
$\max(|x-x^{\prime}|,|y-y^{\prime}|)=1$. Graphs for other chess pieces can be
defined accordingly. For instance, Rudrata showed in the 9th century C.E. that
the $8\times 8$ knight graph is Hamiltonian [4].

The _domination polynomial_ of a graph $G=(V,E)$ is the generating function of
its dominating sets with respect to their size, i.e.,

$P_{G}(z)=\sum_{\begin{subarray}{c}S\subseteq V\\\ \textrm{$S$
dominating}\end{subarray}}z^{|S|}\;=\;\sum_{k=0}^{|V|}N_{k}\,z^{k}\,,$ (1)

where $N_{k}$ is the number of dominating sets of size $k$. Like other graph
polynomials, the domination polynomial encodes many interesting properties of
a graph [5].

A closed form of the domination polynomial is known only for a few very simple
graphs like the complete graph, the wheel graph, and the star graph [6].
Recently, the $m\times n$ rook graph from chess was added to this list [7]. As
far as we know, the rook is the only chess piece for which this has been
achieved.

In this contribution we consider the domination polynomial $P_{m\times n}(z)$
of the $m\times n$ king graph. One of us has computed $N_{k}$ and thus
$P_{m\times n}(z)$ by exact enumeration for all $m,n\leqslant 22$ [8], and the
data shows an interesting pattern when $z=-1$: namely, $P_{m\times n}(-1)=\pm
1$. Since

$P_{m\times n}(-1)=\sum_{\textrm{$k$ even}}N_{k}-\sum_{\textrm{$k$
odd}}N_{k}\,,$

this means that the parity of dominating sets is almost perfectly balanced.
Indeed, it is as balanced as it can be, since the total number of dominating
sets in any finite graph is odd [9]. Specifically, we show that $P_{m\times
n}(-1)=(-1)^{\lceil m/2\rceil\lceil n/2\rceil}$ as in Table 1. Thus the number
of dominating sets of odd size is one greater than those of even size if $m$
and $n$ are both $1$ or $2$ mod $4$, and is one less otherwise.

| $m$
---|---
$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22
1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
2 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
5 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
6 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
8 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
9 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
10 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
11 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
12 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
13 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
14 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
15 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
16 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
17 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
18 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
19 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
20 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
21 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
22 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1
Table 1: Values of $P_{m\times n}(-1)$ from exact enumeration for the king
graph $K_{m\times n}$, showing the pattern $(-1)^{\lceil m/2\rceil\lceil
n/2\rceil}$.

##  2 Matching dominating sets of opposite parity

[setfen=k1k1k1k1/8/k1K1k2k/2k3k1/kk2k1k1/k4k2/1k2k1k1/3k2k1 - - - 0 0,
label=false, showmover=false, pgfstyle=bottomborder, linewidth=0.1ex,
markregion=a7-h8, markregion=a5-h6, markregion=a3-h4, pgfstyle=rightborder,
linewidth=0.1ex, markregion=a1-b8, markregion=c1-d8, markregion=e1-f8, ]

Figure 2: The matching between almost all dominating sets. We scan from left
to right and top to bottom until we find the first $2\times 2$ square where
the upper-right, lower-left, or lower-right corner is occupied. We then flip
that square’s upper-left corner (the white king), adding or removing it from
the set. This produces another dominating set of opposite parity.

[setfen=k1k1k1k1/8/k1k1k1k1/8/k1k1k1k1/8/k1k1k1k1/8 - - - 0 0, label=false,
showmover=false, pgfstyle=bottomborder, linewidth=0.1ex, markregion=a7-h8,
markregion=a5-h6, markregion=a3-h4, pgfstyle=rightborder, linewidth=0.1ex,
markregion=a1-b8, markregion=c1-d8, markregion=e1-f8, ]

Figure 3: The one dominating set that has no partner in our proof of Theorem
2. It has size 16, hence $P_{8\times 8}(-1)=(-1)^{16}=1$.

######  Theorem 1.

Let $P_{m\times n}(z)$ denote the dominating polynomial of the $m\times n$
king graph $K_{m\times n}$. Then

$P_{m\times n}(-1)=(-1)^{\lceil m/2\rceil\lceil n/2\rceil}\,.$ (2)

###### Proof.

We use a matching strategy illustrated in Fig. 2. We divide the graph into
$2\times 2$ squares starting at its top-left corner. If $m$ or $n$ is odd, the
squares on the right or bottom edge of the graph are truncated to $1\times 2$,
$2\times 1$, or $1\times 1$ squares. If $x\in[m]$ and $y\in[n]$ increase to
the right and downward so that the top-left vertex of $K_{m\times n}$ is
$(1,1)$, the top-left corners of the squares are the vertices $v=(x,y)$ where
$x$ and $y$ are both odd.

Now, given a dominating set $S$, we scan the graph from left to right and top
to bottom until we find the first $2\times 2$ square where some vertex other
than its top-left corner—that is, some vertex $(x,y)$ where $x$ or $y$ is
even—is occupied by a king, i.e., is in $S$. Note that all the squares before
that one have their top-left corners occupied, since otherwise their top-left
square would be uncovered—i.e., neither occupied nor a neighbor of an occupied
vertex—and $S$ would not be dominating.

Now consider that square’s top-left corner $v$, shown as a white king in Fig.
2. It is adjacent only to vertices in the previous squares, which are already
covered by their top-left corners, and to the other three vertices in its own
square, which are covered by one of the other vertices in that square. Thus we
can “flip” $v$, adding or removing it from $S$, and the resulting set
$S^{\prime}$ will also be dominating. Applying the same rule gives
$S^{\prime\prime}=S$, so this defines a partial matching of dominating sets.
Since $|S|$ and $|S^{\prime}|$ have opposite parity, the dominating sets with
partners in this matching cancel in $P_{m\times n}(-1)$.

The only dominating set for which this procedure does not define a partner in
this matching is the one shown in Fig. 3, consisting of the top-left corner of
each square. Call this set $T$. Since all other dominating sets cancel, we
have $P_{m\times n}(-1)=(-1)^{|T|}$. Noting that $|T|=(-1)^{\lceil
m/2\rceil\lceil n/2\rceil}$ completes the proof. ∎

##  3 King graphs on cylinders and tori

Our proof of Theorem 2 relies on free boundary conditions. If we consider the
king graph on a cylinder or torus by making $x$ and/or $y$ cyclic, our
matching strategy no longer works—there is no way to define the “first”
$2\times 2$ square. In fact, the statement of the theorem no longer holds.
When we compute $P_{m\times n}(-1)$ by exact enumeration on cylinders and
tori, we find it is no longer restricted to $\pm 1$ (see Table 2).

| $m$
---|---
$n$ | 3 | 4 | 5 | 6
3 | 5 | -3 | -1 | -1
4 | 3 | 39 | 11 | 43
5 | 9 | 33 | -1 | -1
6 | 15 | -13 | -1 | 11

| $m$
---|---
$n$ | 3 | 4 | 5 | 6
3 | -1 | 3 | -1 | -1
4 | 3 | 63 | 3 | 51
5 | -1 | 3 | -1 | -1
6 | -1 | 51 | -1 | 11

Table 2: Values of $P_{m\times n}(-1)$ for the king graph on the cylinder
where $x\in[m]$ is cyclic (left) and on the torus where both $x\in[m]$ and
$y\in[n]$ are cyclic (right).

##  4 Higher dimensions

The king graph can be generalized to other dimensions, including chess in
three and more dimensions [10]. Given $n_{1},\ldots,n_{d}\geqslant 0$, we
define $K_{n_{1}\times n_{2}\times\cdots\times n_{d}}$ as $G=(V,E)$ where
$V=[n_{1}]\times\cdots[n_{d}]$ and $(u,v)\in E$ if
$\max_{i\in[d]}|u_{i}-v_{i}|=1$. Equivalently, $K_{n_{1}\times
n_{2}\times\cdots\times n_{d}}$ is the strong graph product of $d$ path graphs
of size $n_{1},\ldots,n_{d}$. Then we have the following:

######  Theorem 2.

Let $d\geqslant 1$ and left $P_{n_{1}\times n_{2}\times\cdots\times n_{d}}(z)$
denote the dominating polynomial of the $d$-dimensional king graph
$K_{n_{1}\times n_{2}\times\cdots\times n_{d}}$. Then

$P_{n_{1}\times n_{2}\times\cdots\times n_{d}}(-1)=(-1)^{\lceil
n_{1}/2\rceil\lceil n_{2}/2\rceil\cdots\lceil n_{d}/2\rceil}\,.$ (3)

###### Proof.

The same matching strategy works, but now with $d$-dimensional
$2\times\cdots\times 2$ hypercubical blocks, truncated at the right, bottom,
rear, et cetera boundary if the corresponding $n_{i}$ is odd. Each block has
an upper-left-frontmost-et ceterest corner $v$ where $v_{1},\ldots,v_{d}$ are
all odd. Scan left to right, top to bottom, front to back, ana to kata [11]
and so on, finding the first block where some vertex other than this $v$ is
occupied. Then flipping $v$ gives another dominating set $S^{\prime}$ of
opposite parity. The only unmatched dominating set is the set $T$ consisting
of all these corners $v$, and $|T|=\prod_{i=1}^{d}\lceil n_{i}/2\rceil$. ∎

##  5 Conclusions

| $m$
---|---
$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16
1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1
2 | -1 | 3 | -3 | 5 | -5 | 7 | -7 | 9 | -9 | 11 | -11 | 13 | -13 | 15 | -15 | 17
3 | 1 | -3 | 1 | 5 | -3 | -3 | 5 | 1 | -3 | 1 | 1 | 1 | 1 | -3 | 1 | 5
4 | 1 | 5 | 5 | 5 | 1 | 1 | -3 | 1 | 1 | 9 | 5 | 9 | 1 | 1 | -7 | 1
5 | -1 | -5 | -3 | 1 | 3 | -1 | 9 | 13 | -1 | -5 | -3 | -3 | -13 | -9 | 5 | 5
6 | -1 | 7 | -3 | 1 | -1 | 15 | -7 | 9 | 3 | 3 | -23 | 25 | -5 | -5 | -11 | 29
7 | 1 | -7 | 5 | -3 | 9 | -7 | -3 | -3 | 1 | -11 | 17 | 1 | 1 | -15 | 21 | 13
8 | 1 | 9 | 1 | 1 | 13 | 9 | -3 | 9 | 5 | 5 | 1 | 21 | -7 | 1 | 29 | 9
9 | -1 | -9 | -3 | 1 | -1 | 3 | 1 | 5 | 23 | -13 | -3 | -7 | -9 | -9 | 29 | 21
10 | -1 | 11 | 1 | 9 | -5 | 3 | -11 | 5 | -13 | 27 | -19 | 41 | 19 | 31 | -15 | 25
11 | 1 | -11 | 1 | 5 | -3 | -23 | 17 | 1 | -3 | -19 | 1 | -15 | 17 | -11 | 9 | -35
12 | 1 | 13 | 1 | 9 | -3 | 25 | 1 | 21 | -7 | 41 | -15 | 29 | -23 | 41 | -19 | 45
13 | -1 | -13 | 1 | 1 | -13 | -5 | 1 | -7 | -9 | 19 | 17 | -23 | 19 | -37 | 21 | -35
14 | -1 | 15 | -3 | 1 | -9 | -5 | -15 | 1 | -9 | 31 | -11 | 41 | -37 | 103 | -39 | 77
15 | 1 | -15 | 1 | -7 | 5 | -11 | 21 | 29 | 29 | -15 | 9 | -19 | 21 | -39 | 53 | -107
16 | 1 | 17 | 5 | 1 | 5 | 29 | 13 | 9 | 21 | 25 | -35 | 45 | -35 | 77 | -107 | 169
Table 3: $P_{m\times n}(-1)$ from exact enumeration for the $m\times n$ grid
graph (or the wazir graph if you like Shatranj).

From a physics point of view, the domination polynomial $P(z)$ is the
partition function of a spin system at zero temperature where the energy is
the number of non-dominated vertices. For the king graph, this system can also
be thought of as sets of $3\times 3$ squares (the kings’ neighborhoods) which
can overlap but which must cover every vertex. The parameter $z$ is then the
fugacity of this system. We find it curious that this partition function can
be computed exactly for $z=-1$. It would be wonderful if we could compute
$P(z)$ at other values of real or complex $z$. For instance, a three-way
grouping between sets of size $0$, $1$, and $2$ mod $3$ could determine $P(z)$
where $z$ is a cube root of $1$.

For what other systems does this kind of argument exist? As part of a study of
percolation [12], we performed exact enumeration of spanning configurations on
grid graphs of various sizes, i.e., sets of vertices that contain a path from
one side of the grid to the other. These numerical results suggested that the
number of such sets of odd and even size differ by $\pm 1$. To prove this, we
defined a partial matching similar to the one in this paper by flipping a
vertex to produce another spanning configuration of opposite parity, leaving a
single configuration whose size determines $P(-1)$. As for kings, that
matching generalizes to higher-dimensional cubic lattices, and to some other
graphs as well.

Is this phenomenon sporadic or widespread? We have already seen that, for the
king graph, the matching strategy does not work on cylinders or tori. As a
counterexample with free boundary conditions, in Table 3 we show $P(-1)$ for
grid graphs of various sizes, and see that $P(z)$ is not restricted to $\pm
1$.

In chess terms these are wazir graphs, where the wazir can move only one step
north, south, east, or west [13]. The problem seems to be that the wazir does
not have a partial neighborhood that tiles the grid in the same way the
$2\times 2$ square does. But perhaps a matching strategy could work on some
region in the grid other than a rectangle—such as a region that can be tiled
with right trominoes.

## Acknowledgments

We are grateful to the solar eclipse of April 2024 for bringing us back
together. The title of this paper is inspired by a Sudoku designer known as
oddlyeven.

## References

  * [1] Carl Friedrich Jaenisch.  Traité des applications de l’analyse mathématique au jeu des échecs.  Dufour & Cie, Petrograd, 1862.
  * [2] John J. Watkins.  Across the Board: The Mathematics of Chessboard Problems.  Cambridge University Press, 2012.
  * [3] Teresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater.  Fundamentals of Domination in Graphs.  Marcel Dekker, Inc., New York, 1998.
  * [4] Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani.  Algorithms.  McGraw-Hill, New York, 2006.
  * [5] Saieed Akbari, Saeid Alikhani, and Yee-hock Peng.  Characterization of graphs using domination polynomials.  European Journal of Combinatorics, 31(7):1714–1724, 2010.
  * [6] Saeid Alikhani and Yee-Hock Peng.  Introduction to domination polynomial of a graph.  Ars Combinatoria, 114:257–266, 2014.
  * [7] Stephan Mertens.  Domination polynomial of the rook graph.  Journal of Integer Sequences, 27:24.3.7, 2024.
  * [8] Stephan Mertens.  Domination polynomials of the grid, the cylinder, the torus and the king graph.  In preparation.
  * [9] Andries E. Brouwer, Péter Csorba, and Lex Schrijver.  The number of dominating sets of a finite graph is odd.  Preprint https://www.win.tue.nl/~aeb/preprints/domin4a.pdf, 2009\.
  * [10] David Brine Pritchard.  The Classified Encyclopedia of Chess Variants.  John Beasley, 2007.
  * [11] Rudy Rucker.  Spaceland: A Novel of the Fourth Dimension.  Tom Doherty and Associates, 2003.
  * [12] Stephan Mertens and Cristopher Moore.  Percolation is odd.  Physical Review Letters, 123:230605, September 2019.
  * [13] Anthony Dickins.  A Guide to Fairy Chess.  Dover Publications, 1971.