% LaTeX file for a 16 page document
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{}{}{2014}

\title{\bf Some New Characterizations\\ 
of Graph Colorability and of\\ 
Blocking Sets of Projective Spaces}

\author{Uwe Schauz\\%\thanks{Thanks to the editors of this wonderful journal!}\\
\small Department of Mathematical Science\\[-0.8ex]
\small Xi'an Jiaotong-Liverpool University\\[-0.8ex]
\small Suzhou 215123, China\\[-0.8ex]
\small \texttt{uwe.schauz@xjtlu.edu.cn}\\
\small and\\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small King Fahd University of Petroleum and Minerals\\[-0.8ex]
\small Dhahran 31261, Saudi Arabia
}

\date{\dateline{Sep 30, 2013}{Mar 21, 2014}{Mar XX, 2014}\\
\small Mathematics Subject Classifications:
  05C15, 51E21, 91A46}


%------------------------------------------------------------------------------
\addtolength\marginparsep{-2pt}

%%%%%%%%%%%%%%%%%%
%%%   Pakete   %%%
%%%%%%%%%%%%%%%%%%

%%  Fehlersuche  %%
\usepackage{fixltx2e}
%verbesserte Fehlerkorrektur und -suche (Kompatibel mit 2e-Texten!).
%\usepackage{showkeys}%Verweis-Marken in der DVI-Ausgabe.
%\listfiles%Liste der eingelesenen Dateien am Ende des Log-Bereichs.
%\hfuzz1pc % Do not bother to report overfull boxes if overage is < 1pc
%\vfuzz2pt % Do not report over-full v-boxes if over-edge is small

%%  Eingabe  %%
%\usepackage[ansinew]{inputenc}
\usepackage{srcltx}%DVI inverse search. Last comilatin: \usepackage[inactive]{srcltx}

%%  Sprache,Darstellung  %%
\usepackage{datetime}%definiert \xxivtime, \ampmtime, (Muss vor ngerman kommen)
\usepackage{ngerman}%neue Trennregeln.
\selectlanguage{USenglish}
\nonfrenchspacing

%%  Text-Symbole  %%
\usepackage{eurosym}%DIN-Euro \euro \EUR1.20
\usepackage{textcomp}%TS1-Zeichencodierung z.B. \textdollar $.
\usepackage{url}

%%  Grafik  %%
\usepackage{epic}
\usepackage{eepic}
\usepackage[dvips,debugshow]{graphicx}
\usepackage{color}

%%  Mathematik  %%
\usepackage{amsmath}
\usepackage{amsthm}

%%  Mathematik-Symbole  %%
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{bm}%more general and robust implementation of \boldsymbol.

%%  Tabellen  %%
%\usepackage{booktabs}
\usepackage{enumerate}

%%  Sonstiges  %%
\usepackage{afterpage}
\usepackage{xspace}
%definiert \xspace =passendes Leerzeichen nach selbst definierten Makros.
%\usepackage{datetime}%definiert \xxivtime, \ampmtime, --> vor ngerman
%\usepackage{hyperref}


%%%%%%%%%%%%%%%%%%%%%%%%
%%%   Definitionen   %%%
%%%%%%%%%%%%%%%%%%%%%%%%

%\setlength\mathsurround{.2em}
%\emergencystretch.03\textwidth

%%  Umgebungen  %%
%\theoremstyle{plain}%This is the default
\newtheoremstyle{Theorem}{.7\baselineskip}{1\baselineskip}{\itshape}{}{\bfseries}{.}{ }{}
\theoremstyle{Theorem}
\newtheorem{Satz}{Theorem}[section]
\newtheorem{EquiDef}[Satz]{Equivalence and Definition}
\newtheorem{Korollar}[Satz]{Corollary}
\newtheorem{Verallgemeinerung}[Satz]{Generalisation}
\newtheorem{Proposition}[Satz]{Proposition}
\newtheorem{DefinitionProposition}[Satz]{Definition and Proposition}
\newtheorem{Lemma}[Satz]{Lemma}
\newtheorem{Vermut}[Satz]{Conjecture}
\newtheorem{Algorithmus}[Satz]{Algorithm}
\newtheorem{Spiel}[Satz]{Game}

\newtheoremstyle{Definition}{.6\baselineskip}{.8\baselineskip}{}{}{\bfseries}{.}{ }{}
\theoremstyle{Definition}
\newtheorem{Definition}[Satz]{Definition}
\theoremstyle{definition}
\newtheorem{Beispiel}[Satz]{Example}

\theoremstyle{remark}
\newtheorem{Bemerkung}[Satz]{Remark}
\newtheorem*{Notation}{Notation}

\newenvironment{sequation}{\begin{small}\begin{equation}}{\end{equation}\end{small}}
\newenvironment{sequation*}{\begin{small}\begin{equation*}}{\end{equation*}\end{small}}
\newenvironment{Beweis}[1][Proof]{\begin{proof}[#1]}{\end{proof}}
\newcommand\ps{\small}
\newenvironment{proofsize}[1]{\begin{small}#1}{\end{small}}

\newcommand\psize[1]{\begin{proofsize}#1\end{proofsize}}
\newcommand\spsize[1]{\footnotesize{#1}}
\newcommand\textps[1]{\text{\psize{#1}}}
\newcommand\textsps[1]{\text{\spsize{#1}}}

%%  nichtmathematische Befehle  %%
\definecolor{white}{rgb}{1,1,1}
\definecolor{cola}{rgb}{.9,.9,.9}%{1,0,0}
\definecolor{colb}{rgb}{.7,.7,.7}%{0,1,0}
\definecolor{colc}{rgb}{.5,.5,.5}%{0,0,1}
\definecolor{colab}{rgb}{.8,.8,1}%{1,0,0}
\definecolor{colbb}{rgb}{.6,.6,1}%{0,1,0}
\definecolor{colcb}{rgb}{.4,.4,1}
\definecolor{cold}{rgb}{1,1,0}
\definecolor{colf}{rgb}{0,1,1}
\definecolor{cole}{rgb}{0,0,1}
\definecolor{dred}{rgb}{0.9,0,0}
%\definecolor{ddred}{rgb}{0.8,0,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{black}{rgb}{0,0,0}
%\definecolor{dblue}{rgb}{0,0,0.8}
\definecolor{dblue}{rgb}{0.75,0,0.45}
%\definecolor{dgreen}{rgb}{0,0.7,0}
\definecolor{dgreen}{rgb}{0.85,0.35,0}
%\newcommand\red[1]{\textcolor{dred}{#1}}
\newcommand\white{\color{white}}
\newcommand\cola{\color{cola}}
\newcommand\colb{\color{colb}}
\newcommand\colc{\color{colc}}
\newcommand\cold{\color{cold}}
\newcommand\colbb{\color{colbb}}
\newcommand\colab{\color{colab}}
\newcommand\colcb{\color{colcb}}
\newcommand\cole{\color{cole}}
%\newcommand\colf{\color{colf}}
\newcommand\red{\color{dred}}
\newcommand\blue{\color{dblue}}
\newcommand\green{\color{dgreen}}
%\newcommand\gray{\color{gray}}
%\newcommand\black{\color{black}}
\newcommand\Index[1]{\index{#1}#1}
\newcommand\dashed[1]{\hbox{-- }#1\hbox{ --}\xspace}
\newcommand\ms{\hspace{\mathsurround}}
\newcommand\noms{\hspace{-\mathsurround}}
\newcommand\vsp{\vspace{1ex}}
\newcommand\vspp{\vspace{3ex}}
\newcommand\printday{\today\xspace}
\newcommand\Zeit{\xxivtime\xspace}%oder \ampmtime
\newcommand\Rand[1]{%\mbox{}
  \marginpar{\raggedleft\scriptsize\hspace{0pt}#1}}%
  %Randbemerkungen mit Trennung und korrekter Positionierung.
\newcommand\tRand[1]{\Rand{#1}#1}
\newcommand\Emph[1]{\Rand{\emph{#1}}\emph{#1}}

%%  Mathematik-Befehle  %%
\renewcommand{\(}{\noms$}
\renewcommand{\)}{\noms$}
\renewcommand\frac[2]{\genfrac{}{}{.4pt}{}{#1}{#2}}%EJC erzeugt zu breite Linien.
\renewcommand\tfrac[2]{\genfrac{}{}{.4pt}{1}{#1}{#2}}
\renewcommand\dfrac[2]{\genfrac{}{}{.4pt}{0}{#1}{#2}}
\renewcommand\atop[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand\Strut{\phantom{\rlap{\ensuremath{\displaystyle\sum}}}}
\newcommand\mathRand[1]{\hspace{\mathsurround}\Rand{#1}\nolinebreak\noms}
%Zeilenanfang-->\noms
\def\rand #1"#2"{\mathRand{\(#2\)}#1#2}
\def\randd #1"#2"#3\randd#4"#5"{\mathRand{\(#2\), \(#5\)}#1#2#3#4#5}

\newcommand\eqby[2][=]%
  {\ensuremath{\overset{\makebox[0pt]{\ensuremath{\smash[t]{\scriptstyle#2}}}}{#1}}}
  %equal by
\newcommand\Ceqby[2][=]{\quad\eqby[#1]{#2}\quad}
\newcommand\ceqby[2][=]{&\Ceqby[#1]{#2}}%bessere Posit. in split, align,
\newcommand\Ceq[1][=]{\quad#1\quad}
\newcommand\ceq[1][=]{&\Ceq[#1]}


\renewcommand\o{\emptyset}%\varnothing}
\newcommand\K{\mathbb{K}}
\newcommand\F[1][\ ]{\mathbb{F}_{\!#1}}
\newcommand\C{\mathbb{C}}
\newcommand\R{R}%{\mathcal{R}}
\newcommand\Rn[1][n]{\R\,\n[#1]}
\newcommand\Rl{\mathbb{R}}
\newcommand\Q{\mathbb{Q}}
\newcommand\Z{\mathbb{Z}}
\newcommand\N{\mathbb{N}}
\newcommand\M{\mathcal{M}}
\newcommand\AM{\mathcal{A\!M}}
\newcommand\PM{\mathcal{P\!M}}
\newcommand\B{\mathcal{B}}
\newcommand\V{\mathcal{V}}
\newcommand\Hy{\mathcal{H}}

\renewcommand\sb{\subseteq}%vorher: XX\sb{index}=XX_{index}
\renewcommand\sp{\supseteq}%vorher: XX\sb{ex}=XX^{ex}
\newcommand\nin{\notin}
\newcommand\nni{\not\ni}
\newcommand\sm{\setminus}
\newcommand\ssm{\textup{\texttt{\char92}}}
\newcommand\Ssm{\textup{\texttt{\char92\!\!\char92}}}
\newcommand\down{\downharpoonright}
\newcommand\up{{\upharpoonright}}
\newcommand\mto{\mapsto}
\newcommand\lmto{\longmapsto}
\newcommand\lto{\longrightarrow}
\newcommand\To{\Rightarrow}
\newcommand\lTo{\Longrightarrow}
\newcommand\Eqi{\Leftrightarrow}
\newcommand\lEqi{\Longleftrightarrow}
\newcommand\nach{\mathbin\circ}%\triangleleft}
\newcommand\vor{\mathbin\triangleright}
\newcommand\fa{\forall\,}
\newcommand\ex{\exists\,}
\newcommand\nex{\nexists\,}
\newcommand\DP{\colon\discretionary{\!\kern -.17em}{}{}}
% ":" als Interp.-zeichen mit Trennst.
\newcommand\mitsymbol{\textup{\textbrokenbar}}
\renewcommand\mit{\,\ \discretionary{\mitsymbol}{}{}\mitsymbol\ \,}
%\mit{} war altes \mathit{}
\newcommand\eqn[1][\neq]{\mathrel{\equiv\joinrel#1}}
\renewcommand\div{\mathrel{\bigm\lfloor\!\!\!\bigm\lfloor}}
\newcommand\vid{\mathrel{\bigm\rfloor\!\!\!\bigm\rfloor}}
\newcommand\ndiv{\mathrel{\;\!\div\hspace{-12pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\newcommand\ndivps{\mathrel{\;\!\div\hspace{-9pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\newcommand\nvid{\mathrel{\;\!\vid\hspace{-12pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\newcommand\nvidps{\mathrel{\;\!\vid\hspace{-9pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\newcommand\Div{\mathrel{\Bigm\lfloor\hspace{-6pt}\Bigm\lfloor}}
\newcommand\viD{\mathrel{\Bigm\rfloor\hspace{-6pt}\Bigm\rfloor}}
\newcommand\nDiv{\mathrel{\,\Div\hspace{-12.13pt}\diagup}}
\newcommand\nviD{\mathrel{\,\viD\hspace{-12.13pt}\diagup}}
\newcommand\n[1][n]{{\phantom{|}}^{\!\!\!\!#1}}
\newcommand\FZ{{\!_{\F[2]}\!\!}}
\newcommand\FZZ{{\!_{\Z}\!\!}}
\newcommand\Inv[2][.5ex]{\raisebox{#1}{\ensuremath
 {\scriptstyle\text{\!-\!-\hspace{-.08em}}\scriptscriptstyle#2\!\!\!}}}
\newcommand\Invs[2][.5ex]{\raisebox{#1}{\ensuremath
 {\scriptstyle\text{\!\!-\hspace{-.2em}-\hspace{-.08em}}\scriptscriptstyle#2\!\!\!}}}
\newcommand\inv[1][1]{\mathchoice{}{}{\Inv{\mathbf{#1}}}{\Invs[.1ex]{#1}}}
% besseres h^{-1}
\newcommand\invs[1][1]{\mathchoice{}{}{\Inv[.2ex]{\mathbf{#1}}}{\Invs[.1ex]{#1}}}
\providecommand\abs[1]{\lvert#1\rvert}
\providecommand\Abs[1]{\bigl\lvert#1\bigr\rvert}
\providecommand\norm[1]{\lVert#1\rVert}
\newcommand\spn[1]{\langle#1\rangle}
\newcommand\Spn[1]{\bigl\langle#1\bigr\rangle}
\newcommand\spnb[1]{\langle\hspace{-4pt}\langle#1\rangle\hspace{-4pt}\rangle}%_{\!_\Z}
\newcommand\Spnb[1]%
{\bigl\langle\hspace{-5pt}\bigl\langle#1\bigr\rangle\hspace{-5pt}\bigr\rangle}
\providecommand\basis[1]{\langle\!\langle#1\rangle\!\rangle}
%\newcommand\wert[1]{\llbracket#1\rrbracket}%Warheitswert einer Aussage
\newcommand\?[1]{{?}_{(#1)}}%Warheitswert einer Aussage
\newcommand\lo[2][\p]{{}^{#1}\!#2}%#1 links oben
\newcommand\blo[2][\p]{\abs{\lo[#1]{#2}}}%Betrag davon

\DeclareMathOperator\Id{Id}
\DeclareMathOperator\End{End}
\DeclareMathOperator\supp{supp}
\DeclareMathOperator\Bild{Im}
\DeclareMathOperator\Def{Def}
\DeclareMathOperator\Kern{Kern}
\DeclareMathOperator\Pot{\mathcal{P}}
\DeclareMathOperator\scm{scm}
\DeclareMathOperator\ch{ch}
\DeclareMathOperator\Ch{Ch}
\DeclareMathOperator\Char{char}
\DeclareMathOperator\per{per}
\DeclareMathOperator\codim{codim}
\DeclareMathOperator\Adj{Adj}
\DeclareMathOperator\Diag{Diag}
\DeclareMathOperator\Quot{Quot}
\DeclareMathOperator\GL{GL}
\DeclareMathOperator\PG{PG}
\DeclareMathOperator\PGC{PGC}
\DeclareMathOperator\A{A}
\DeclareMathOperator\Pro{P}
\DeclareMathOperator\AB{A\!B}
\DeclareMathOperator\PB{PB}
\DeclareMathOperator\PBC{PBC}
%\DeclareMathOperator\M{M}
%\DeclareMathOperator\AM{A\!M}
%\DeclareMathOperator\PM{PM}
\DeclareMathOperator\CS{CS}
\DeclareMathOperator\Ct{\mathcal{B}}
\DeclareMathOperator\Cy{\mathcal{C}}
\DeclareMathOperator\RS{RS}
\DeclareMathOperator\AV{A\!V}
\DeclareMathOperator\FV{FV}
\DeclareMathOperator\Mm{M}
\DeclareMathOperator\w{w}

%\AtEndDocument{\enlargethispage{\baselineskip}\footnotetext{%
%  Letzte Bearbeitung am \printday um \Zeit{}.}}

%------------------------------------------------------------------------------

\newcommand\cB{\mathcal{B}}
\newcommand\cC{\mathcal{C}}
\newcommand\cE{\mathcal{E}}
\newcommand\ce{\varepsilon}
\newcommand\cV{\mathcal{V}}
\newcommand\cH{\mathcal{H}}
\newcommand\cv{\nu}
\newcommand\X{\mathfrak{X}}
\newcommand\PX[1][\X]{P\!/\!#1}
\newcommand\cI{\mathcal{I}}
\newcommand\cF{\mathcal{F}}
\newcommand\cL{\mathcal{L}}
\newcommand\+{\boldsymbol{+}}
\newcommand\x{\chi}
\renewcommand\S{\mathcal{S}}
\newcommand\St{\S_{\textup{triv}}}
\newcommand\D{\mathcal{D}}
\newcommand\T{\mathcal{T}}
\newcommand\p{\varphi}
\newcommand\s{\sigma}
\renewcommand\l{\lambda}
\renewcommand\b{\beta}
\newcommand\hE{{\hat E}}
\newcommand\hS{{\hat S}}
\newcommand\tx{\skew{2}{\tilde}{x}}
\newcommand\hx{\skew{2}{\hat}{x}}
\renewcommand\d{\delta}
\newcommand\dpl[1][]{d^{^+}_{\!#1}}
\newcommand\td{\tilde\d}
\newcommand\e{\varepsilon}
\renewcommand\r{\varrho}
\newcommand\Chi{\kern0pt\lower-2.5pt\hbox{\ensuremath\chi\!}}
\newcommand\const{\textsf{const}}
%\newcommand\RefOr{{\varphi_\textsl{\textsf{\!ref}}}}%Referenz-Orientierung
\newcommand\bb{\mathbf{b}}
\newcommand\dd{\mathbf{d}}
\newcommand\xx{\mathbf{x}}
\newcommand\ee{\mathbf{e}}
\newcommand\kk{\mathrm{k}}
\newcommand\E{\mathsf{1}}
\newcommand\EE{\mathrm{I\!\!I}}
\newcommand\cop[1]{[#1]}%{\lfloor#1\rfloor}
\newcommand\sel[1]{\langle#1\rangle}%{\lceil#1\rceil}
%----------------------------------------------------------------
%Graphentheorie:
\newcommand\sTo{{{\shortrightarrow}\!\!\!\!\!\hspace{.75pt}%
  {\shortrightarrow}\!\!\!\!\!\hspace{.75pt}{\shortrightarrow}\!\!\!\!\!\hspace{.75pt}%
  {\shortrightarrow}\!\!\!\!\!\hspace{.75pt}{\shortrightarrow}}}
\newcommand\sFrom{{{\shortleftarrow}\!\!\!\!\!\hspace{.75pt}%
  {\shortleftarrow}\!\!\!\!\!\hspace{.75pt}{\shortleftarrow}\!\!\!\!\!\hspace{.75pt}%
  {\shortleftarrow}\!\!\!\!\!\hspace{.75pt}{\shortleftarrow}}}
\newcommand\lsTo{{\relbar\joinrel\joinrel\relbar\joinrel\joinrel\sTo}}
\newcommand\lsFrom{{\sFrom\joinrel\joinrel\relbar\joinrel\joinrel\relbar}}
\newcommand\msTo{{\relbar\joinrel\joinrel\relbar\joinrel\joinrel\joinrel\sTo}}
\newcommand\msFrom{{\sFrom\joinrel\joinrel\joinrel\relbar\joinrel\joinrel\relbar}}
\newcommand\sto{\scriptscriptstyle{\sTo}}
\newcommand\sfrom{\scriptscriptstyle{\sFrom}}
\newcommand\lsto{\scriptscriptstyle{\lsTo}}
\newcommand\lsfrom{\scriptscriptstyle{\lsFrom}}
\newcommand\msto{\scriptscriptstyle{\msTo}}
\newcommand\msfrom{\scriptscriptstyle{\msFrom}}
\newcommand\G[1][\sto]{{\overset{\makebox(0,-1.9){\ensuremath{#1\hspace{-.2em}}}}{G}}}
\newcommand\LG[1]{{\overset{\makebox(0,-1.9){\ensuremath{#1\hspace{-.2em}}}}{LG}}}
\newcommand\ed[1]{e^{\!#1}}
%\newcommand\V[1]{{}^{#1}\!v}
\DeclareMathOperator\sign{sign}
%%%%%%%%%%%%%%%%%%%%%%%%% from jfig
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\makeatother\endgroup


\begin{document}
\maketitle

\begin{abstract}
Let $G=(V,E)$ be a graph and $q$ be an odd prime power. We prove that $G$ possess a
proper vertex coloring with $q$ colors if and only if there exists an odd vertex labeling
$x\in\F[q]^V$ of $G$. Here $x$ is called odd if there is an odd number of partitions
$\pi=\{V_1,V_2,\dotsc,V_t\}$ of $V$ whose blocks $V_i$ are \(G\)-bipartite and
\(x\)-balanced, i.e., such that $G|_{V_i}$ is connected and bipartite, and $\sum_{v\in
V_i}x_v=0$. Other new characterizations concern edge colorability of graphs and, on a more
general level, blocking sets of projective spaces. Some of these characterizations are
formulated in terms of a new switching game.
\end{abstract}


\section{Introduction}\label{sec.int}

The results in this paper are based on the study of a new \emph{switching game}
(Section\,\ref{sec.sg}). We view this game as an auxiliary tool only. Many of our results are
formulated without mentioning it and provide new equivalents for the colorability of graphs,
for example. Our auxiliary switching game is a single player game with complete information.
The player's objective is to modify a certain \emph{initial pattern} step by step and to reach a
certain \emph{zero pattern} eventually. The number of moves needed does not matter here.
The question is whether it is possible to reach the zero pattern at all. We already studied
some similar generalizations of Berlekamp's Switching Game in \cite{schBer,schBer2}.
These games were closely related to anti-codes (codes with restricted maximal weight) and
to flows of graphs. We did also obtain some graph colorability results, some Alon-Tarsi-like
results, but only by using the duality of flows and colorings. The switching game that we are
going to study here is more directly related to colorings. Actually, there is only one natural
step between our switching games and graph colorability, which are \emph{blocking sets}
(Section\,\ref{sec.ab}) of finite vectors spaces \rand$"\V"=\F[q]\n$. As blocking sets over
$\F[q]$ are a generalization of non"~\(q\)"~colorable graphs, as we will see, it is natural to
study them first. We will show that a subset \rand$"B"\sb\V$ is a blocking set if and only if
there exist a winning strategy in our switching game. Here the set of available moves is
defined with respect to $B$, so that the \emph{switchability} of the initial pattern actually
depends on $B$. We will also present some best possible strategies, i.e., general
strategies that turn out to be winning strategies whenever the game actually can be won. All
these strategies and the whole concept of switchability can be expressed as mere linear
combinations and linear dependencies of certain vectors in $\Z^\V$ (or in
$\Z_r^\V$).\smallskip

We then turn to graphs (Section\,\ref{sec.gc}). Graphs \rand$"G=(V,E)"$ correspond to
blocking sets with special properties. Hence, our results about blocking sets hold for graphs
as well, and we can even simplify or improve them based on the additional properties of
graphs. It turns out that some quantitative statements about certain classes of partitions of
$V$ are equivalent to the \(q\)"~colorability of $G$. The general form of these equivalents
might be technical, but in some special cases we obtain cleaner results. For example, if $q$
is an odd prime power, we can prove that the graph $G$ possesses a proper vertex coloring
using at most $q$ many colors if and only if there exists an odd vertex labeling $x\in\F[q]^V$
of $G$. Here $x$ is called odd if there is an odd number of partitions
$\pi=\{V_1,V_2,\dotsc,V_t\}$ of $V$ whose blocks $V_i$ are \(G\)"~bipartite and
\(x\)"~balanced, i.e., such that $G|_{V_i}$ is connected and bipartite, and $\sum_{v\in
V_i}x_v=0$. Other new characterizations concern edge colorability of graphs.\smallskip

We also obtain some results with respect to the number of colorings in modular arithmetic,
when we count modulo some \rand$"r"\geq2$. Many algebraic tools work or can be applied
in modular arithmetic. In some of the applications of such tools, it can be important to know
that the number of colorings of a graph is nonzero modulo $r$. This can be a problem. For
example, one can sometimes use the Combinatorial Nullstellensatz to prove the colorability
of some graphs or to generalize colorability results to list coloring results, as e.g.\ in
\cite[Sec.\,5]{schAlg}. In such approaches, one usually has to show that a certain coefficient
in a certain polynomial is nonzero. Sometimes, this coefficient equals the number of
colorings of the examined graph $G$. Hence, it seems that, in that case, one should already
be satisfied with the existence of colorings. However, in modular arithmetic, having a
coloring and having a nonvanishing number of colorings is not the same. The number might
be zero modulo $r$, even though colorings exist. Therefore, it might be good to know that,
with just one additional linear restriction on the colorings, one can actually force that number
to be nonzero modulo $r$. More precisely, if \rand$"\cC_q(G)"\sb\F[q]\n$ denotes the set
of colorings with colors taken from $\F[q]$, we show that to any divisor $r$ of $q-1$ there
exists an $x\in\V=\F[q]\n$ such that $\frac{\abs{\cC_q(G)\sm x^\perp}}{q-1}$ is nonzero
modulo $r$, provided $\cC_q(G)\neq\o$. It is conceivable that one can find ways to employ
this, for example in connection with the Combinatorial Nullstellensatz.\medskip

% -----------------------------------------------------------------------------
\section{Switching Games}\label{sec.sg}

Our single player switching game is played on the \emph{board} \rand$"\V":=\F[q]\n$. A
\emph{pattern} is a function $f\DP\V\lto\Z$. Typically, we start with the fixed \emph{initial
pattern} \rand$"f_0":=q^{n-1}\{0\}$, defined by
\begin{equation}
q^{n-1}\{0\}(x):=
\begin{cases}
 q^{n-1}&\text{if $\,x=0$,}\\
 0&\text{if $\,x\in\V\ssm0$.}
\end{cases}
\end{equation}
This initial pattern will then be modified by adding integral multiples $mf$ of certain
\emph{available} patterns $f$,
\begin{equation}
f_0\ \lmto\ f_0+mf.
\end{equation}
This is called making a \emph{move}. We also say that we \emph{switch} $f$ exactly $m$
many times, where negative multiplicities $m$ are allowed. The class of available patterns
$f$ will be defined later and will vary from case to case; hence, actually we will examine
several different games. We say that we can \emph{switch off} $f_0$, or that $f_0$ is
\emph{switchable}, if there is a finite sequence of moves that results in the zero function
denoted \rand$"\o"$. For an integer \rand$"r"\geq2$, we say that we can switch off $f_0$
\emph{modulo $r$\!}, or that $f_0$ is switchable modulo $r$, if we can switch it off, but with
all function values of all patterns taken modulo $r$. One could also say that a
\emph{winning strategy} exists, or that it exists modulo $r$, in that case.
\smallskip

Before we play the game, here are some more conventions:

We identify subsets $U\sb\V$ with their characteristic functions $\V\lto\{0,1\}$ as
\(0\)"~\(1\) patterns:
 \rand\begin{equation}
"U(x)":=\begin{cases}
 1&\text{if $\,x\in U$,}\\
 0&\text{if $\,x\in\V\sm U$.}
\end{cases}
\end{equation}
This is used extensively. It simplifies notation but can lead to unusual expressions. For
example, the singletons \rand$"\{u\}"\sb\V$ are also viewed as \(0\)"~\(1\) patterns
\begin{equation}
\{u\}\DP\ \V\lto\{0,1\},\,\ x\lmto\{u\}(x).
\end{equation}
These one"=point sets form the standard basis of the \(\Z\)"~module \rand$"\Z^\V"$ of all
patterns. They are usually not available as moves, only the initial pattern, as a multiple of
$\{0\}$, could be considered as an unavoidable initial move.

Note that both the board $\V:=\F[q]\n$, as well as the set of patterns $\Z^\V$, carry the
structure of a module. Our board $\V$ is a module over $\F[q]$, while $\Z^\V$ is a module
over $\Z$. They both provide an addition. Therefore, we have to be careful with the notation.
Subsets of $\V$ are usually viewed as \(0\)"~\(1\) patterns in $\Z^\V$ and added in
$(\Z^\V,+)$, while elements of $\V$, or combinations of one element and one subset of
$\V$, are always added in $(\V,+)$. For example, if $n=2$ and we consider $(0,1)$ and
$(1,0)$ as two points of the board $\V=\F[q]\n[2]$, we have
\begin{equation}
(0,1)+(1,0)\,=\,(1,1)\,\in\,\V,
\end{equation}
as we would view the $+$ as addition in $\V$ here, and
\begin{equation}
(0,1)+\{(1,0)\}\,=\,\{(1,1)\}\,\in\,\{0,1\}^\V\,\sb\,\Z^\V,
\end{equation}
again with the addition in $\V$ (with $x+U=\{x+u\mit u\in U\}$), but
\begin{equation}
\{(0,1)\}+\{(1,0)\}\,=\,\{(0,1),(1,0)\}\,\in\,\Z^\V,
\end{equation}
where the $+$ is meant as addition in $\Z^\V$. Similar rules are used for the two scalar
multiplications; hence, for example,
\begin{equation}
2\{(1,0)\}\ \neq\ \{2(1,0)\},
\end{equation}
where the left scalar multiplication is meant in $\Z^\V$ and produces the pattern that has the
value $2$ in $(1,0)$ and $0$ elsewhere, while the right scalar multiplication is in
$\V=\F[q]\n[2]$ and produces the pattern $\{(2,0)\}$, which has the value $1$ in $(2,0)$ and
$0$ elsewhere. The reader may try to read the left side of the first equation in
Theorem\,\ref{sz.ss} with these conventions. There, we view a linear combination inside
$\Z^\V$ of certain patterns $\spn{S}\in\Z^\V$, and evaluate it in a point $x$. However, the
patterns $\spn{S}$ appear as linear spans inside the vector space $\V$ first. One has to
recognize that they, as subsets of $\V$, also are patterns in $\Z^\V$.


% -----------------------------------------------------------------------------
\section{Blocking Sets}\label{sec.ab}


A \emph{blocking set} in the \(\F[q]\)"~vector space \randd$"\V":=\F[q]\n$ is a subset
\randd$"B"$ such that each hyperplane \rand$H"\lessdot"\V$ contains at least one element
of $B$, $B\cap H\neq\o$. Usually, this is formulated in the language of projective spaces,
but we do not do it here. To characterize blocking sets $B\sb\V$ in terms of switchability, we
have to recall some basic facts about the subspaces of our \(\F[q]\)"~vector space $\V$.
Such enumerative facts are most elegantly denoted with \(q\)"~analogs, in particular, the
\emph{\(q\)"~numbers}
 \rand\begin{equation}\label{eq.qn}
"[m]_q"\,:=\,\frac{q^m-1}{q-1}\,=\,q^{m-1}+\dotsb+q^1+q^0.
\end{equation}
Our first lemma counts hyperplanes, i.e., maximal proper subspaces $H$ of $\V$,
$H\lessdot\V$. We frequently will use them, and define, for $A,B\sb\V$ and $a\in\V$,
 \rand\begin{equation}
"\Hy_A^B"\,:=\,\{H\lessdot\V\mit A\sb H,\,B\cap
H=\o\},\quad\Hy_a^B\,:=\,\Hy_{\{a\}}^B,\quad\Hy^B\,:=\,\Hy_\o^B,\quad\text{etc.}
\end{equation}
We recall some basic enumerative facts about $\Hy_A$ and translate them into our
switching game notation:

\begin{Lemma}\label{lem.H}
Let $U$ be an \(m\)"~dimensional proper subspace of the \(n\)"~dimensional vector space
$\V:=\F[q]\n$ over $\F[q]$, and let $x\in\V\!\sm\!U$. Then
$$
\abs{\Hy_U}=[n{-}m]_q\ \ \quad\text{and}\ \ \quad\abs{\Hy_{U\cup\{x\}}}=[n{-}m{-}1]_q.
$$
In particular,
$$
\sum_{H\in\Hy_U}H\,\,=\,\,[n{-}m]_qU\,+\,[n{-}m{-}1]_q(\V\!\sm\!U)\,\,=\,\,q^{n-m-1}U\,+\,[n{-}m{-}1]_q\V,
$$
and this equation also holds for the full space $U=\V$ if we set $[-1]_q:=-q^{-1}$.
\end{Lemma}

We also will need enumerative facts about $\Hy^B$:

\begin{Lemma}\label{lem.tu}
Let $\o\neq B\sb\V$. Then
$$
\abs{\Hy^B}=\sum_{S\sb B}(-1)^{\abs{S}}\,[n{-}\dim\spn{S}]_q
=\frac{1}{q-1}\sum_{S\sb B}(-1)^{\abs{S}}\,q^{n{-}\dim\spn{S}},
$$
where the first equation also holds for $B=\o$.
\end{Lemma}

\begin{Beweis}
There are $[n{-}\dim\spn{S}]_q$ many hyperplanes containing a given subset $S\sb B$.
Therefore, the first equation follows from the principle of inclusion exclusion. The second
equation easily follows from our Definition\,\eqref{eq.qn} of \(q\)"~numbers, using that, for
$B\neq\o$,
\begin{sequation}
\sum_{S\sb B}(-1)^{\abs{S}}\,=\,0.
\vspace{-.7\baselineskip}
\end{sequation}%
\end{Beweis}

At this point, one may observe that the last formula for $\abs{\Hy^B}$ contains a not obvious
insight about the spanning subsets of blocking sets. If we read our formula only modulo $q$,
we may omit all summands with $\dim\spn{S}<n$, so that the sum only runs over spanning
subsets $S\sb B$, $\spn{S}=\V$. Hence, if $B$ is a blocking set, $\abs{\Hy^B}=0$, we see
that
\begin{equation}\label{eq.ss}
q\ \ \text{divides}\ \sum_{\atop{S\sb B}{\spn{S}=\V}}(-1)^{\abs{S}}.
\end{equation}
This might be of some interest on its own, but we also need it at some point. More
important, however, is the following application of the lemmas above:

\begin{Satz}\label{sz.ss}
Let $\o\neq B\sb\V$ and $x\in\V$. Then
$$
\biggl(\sum_{S\sb B}(-1)^{\abs{S}}q^{n-\dim\spn{S}}\spn{S}\biggr)(x)
\,=\,q\abs{\Hy_x^B}-\abs{\Hy^B}.
$$
Or, put another way,
$$
\sum_{\atop{S\sb B}{\spn{S}\ni x}}(-1)^{\abs{S}}q^{n-\dim\spn{S}}
\,=\,q\abs{\Hy_x^B}-\abs{\Hy^B}.
$$
\end{Satz}

\begin{Beweis}
Using $q[m-1]_q=[m]_q-1$, which also holds for $m=0$, we calculate:
\begin{sequation}
\begin{split}
\sum_{S\sb B}(-1)^{\abs{S}}&q^{n-\dim\spn{S}}\spn{S}\\
\ceqby{\ref{lem.H}}\sum_{S\sb B}(-1)^{\abs{S}}\,q\Bigl(\sum_{H\in\Hy_S}\!\!H\,\,-[n{-}\dim\spn{S}{-}1]_q\V\Bigr)\\
\ceq q\sum_{H\lessdot\V}\Bigl(\sum_{S\sb B\cap H\!\!\!\!}(-1)^{\abs{S}}\Bigr)H
    \,\,-\sum_{S\sb B}(-1)^{\abs{S}}\,[n{-}\dim\spn{S}]_q\V
    \,\,+\sum_{S\sb B}(-1)^{\abs{S}}\V\\
\ceqby{\ref{lem.tu}}q\!\!\sum_{\atop{H\lessdot\V}{H\cap B=\o\!\!}}\!\!H\,\,-\abs{\Hy^B}\,\V\,+\,\o\\
\ceq\sum_{x\in\V}\,\bigl(q\abs{\Hy_x^B}-\abs{\Hy^B}\bigr)\{x\}.
\end{split}
\end{sequation}%
\end{Beweis}

If $B$ is a blocking set, $\Hy^B=\o$, this theorem simplifies to the following equation:

\begin{Korollar}\label{kor.ss}
If $B$ is a blocking subset of $\V$, then
$$
\sum_{S\sb B}(-1)^{\abs{S}}q^{n-\dim\spn{S}}\spn{S}
\,=\,\o.
$$
\end{Korollar}

With this, we are able to prove the following theorem:

\begin{Satz}\label{sz.eq}
Let $q$ be a prime power and assume $r\in\N$ does not divide $q^{n-1}$. For any subset
$B\sb\V:=\F[q]\n$, the following are equivalent over the board $\V$:
\begin{enumerate}[(i)]
\item $B$ is a blocking set.
\item The pattern $q^{n-1}\{0\}$ can be switched off by switching each hyperplane that
    contains at least one $b\in B$ exactly $-1$ times and by switching the full space $\V$
    exactly $[n{-}1]_q$ many times.
\item The pattern $q^{n-1}\{0\}$ can be switched off by switching for each nonempty
    $S\sb B$ the span $\spn{S}$ exactly $(-1)^{\abs{S}}q^{n-\dim\spn{S}-1}$ many times
    (which then automatically adds up to an integral number of switches for any possible
    span $\spn{S}$).
\item The pattern $q^{n-1}\{0\}$ can be switched off modulo \(r\) by switching affine lines
    $u+\spn{b}$ with directions $b$ taken from $B$.
\item Some modulo \(r\) nonvanishing multiple $\ell\{0\}$ of $\{0\}$ can be switched off
    modulo \(r\) by switching affine subspaces $u+U$ whose corresponding direction
    subspaces $U$ contain at least one $b\in B$.
\end{enumerate}
\end{Satz}

\begin{Beweis}
To prove $(i)\To(ii)$, assume that $B$ is a blocking set. Then any hyperplane $H$ contains
at least one element $b\in B$ and shall be switched in Statement\,\((ii)\). If we actually switch
each hyperplane $H$ exactly $-1$ time, then the point $0$ is switched $-[n]_q$ many times,
while any other point $x\neq0$ is switched $-[n{-}1]_q$ many times. Thus, if we also switch
the full space $\V$ exactly $[n{-}1]_q$ many times, the points $x\neq0$ remain unswitched,
while $0$ is switched $-[n]_q+[n{-}1]_q=-q^{n-1}$ many times, canceling the initial pattern
$q^{n-1}\{0\}$.\smallskip

To gain insight in the implication $(i)\To(iii)$, we divide the equation in Corollary\,\ref{kor.ss}
by $q$ and move the summand corresponding to $S=\o$ to the other side. The equation
obtained can then be viewed as a switching procedure. As mentioned, this procedure
necessarily involves an integral number of switches of any $\spn{S}$, which easily follows
from Statement\,\eqref{eq.ss}.\smallskip

The implications $(ii)\To(iv)$ and $(iii)\To(iv)$ follow from the fact that any subspace that
contains a $b\in B$ can be decomposed into parallels of the line $\spn{b}$.\smallskip

The implication $(iv)\To(v)$ is trivial.\smallskip

In order to prove $\neg(i)\To\neg(v)$, assume that a hyperplane $H$ is not blocked by $B$.
Then any legitimate move $u+U$ in Part\,\((v)\) is not parallel to $H$, as there is a $b\in B$
with
\begin{sequation}
U\,\ni\,b\,\nin\,H.
\end{sequation}%
It intersects $H$, as well as any fixed parallel $h+H\neq H$ of $H$, in exactly
$q^{\dim(U)-1}$ many points,
\begin{sequation}
\abs{(u+U)\cap(h+H)}\,=\,q^{\dim(U)-1}\,=\,\abs{(u+U)\cap H}.
\end{sequation}%
Applied to any pattern $f\in\Z^{\V}$, the move $u+U$ will not change the difference
\begin{sequation}
 \Delta(f)\,:=\,\sum_{x\in H}f(x)\ -\!\sum_{x\in h+H}\!\!\!\!f(x).
\end{sequation}%
This difference is an invariant,
\begin{sequation}
\Delta(f+(u+U))\,=\,\Delta(f),
\end{sequation}%
where, in this expression, one should recognize the different additions in $\V$ and
$\Z^\V$. If the invariant is nonzero at the beginning, then it will stay nonzero forever. In
particular, the pattern $f=\ell\{0\}$, with $\ell\not\equiv0\pmod{r}$, cannot be transformed into
$\o$ modulo $r$, as this would require a change of the invariant modulo $r$.\smallskip
\end{Beweis}

An equivalence like this is usually more powerful if it connects weak and strong statements;
thus, we tried to make the weak ones weaker and the strong ones stronger. In our theorem,
Statement\,\((iv)\) is relatively weak and most similar to the switching rules in the Berlekamp
games described in \cite{schBer} and \cite{schBer2}. The weakest switchability statement in
our equivalence is Statement\,\((v)\), but it could be weakened even more. If $q=p^\b$ and
$\F[p]$ is the prime field of $\F[q]$, we may even allow switching of all affine
\(\F[p]\)"~subspaces $u+U$ with $U\sp\spn{b}_{\F[q]}$ for some $b\in B$. Our strong
switchability statements \((ii)\) and \((iii)\) are already very narrow and precise. They describe
the best possible winning strategies mentioned in the introduction. In all these different
games, the reader may just wonder about the unexpected multiplier $q^{n-1}$ in our initial
pattern $q^{n-1}\{0\}$. This actually can be altered in some cases. If we play modulo $r$,
with $r\in\N\ssm0$ coprime to $q$ (so that $1$ is a multiple of $q^{n-1}$ modulo $r$), then
we may replace $q^{n-1}\{0\}$ by the neater $\{0\}$ as initial pattern.

The next equivalent is formulated without mentioning any games. Its equations might also
be viewed as linear dependencies of some patterns in $\Z^\V$:

\begin{Satz}\label{sz.eq2}
Let $q$ be a prime power and $\o\neq B\sb\V:=\F[q]\n$. If $r>1$ divides $q-1$, then the
following are equivalent:
\begin{enumerate}[(i)]
\item $\,\,B$ is a blocking set.
\item $\,\displaystyle\sum_{S\sb B}(-1)^{\abs{S}}q^{n-\dim\spn{S}} \,=\,0$.
\item $\displaystyle\sum_{\atop{S\sb B}{\spn{S}\ni x}}(-1)^{\abs{S}}q^{n-\dim\spn{S}}
    \,=\,0\,\ $ for all $x\in\V\!$.
\item $\displaystyle\sum_{\atop{S\sb B}{\spn{S}\ni x}}(-1)^{\abs{S}}\,\equiv\,0\pmod{r}\,\ $
    for all $x\in\V$.
\end{enumerate}
Moreover, if Condition\,\((iii)\) or Condition\,\((iv)\) is not fulfilled in $x=0$, then these
conditions are not fulfilled in a further point $x\in\V$.
\end{Satz}

\begin{Beweis}
The equivalence $(i)\Eqi(ii)$ is the content of Lemma\,\ref{lem.tu}.

The implication $(i)\To(iii)$ is the content of Corollary\,\ref{kor.ss}, and $(iii)\To(iv)$ is trivial.

That $(iv)\To(i)$, follows from the implication $(v)\To(i)$ in Theorem\,\ref{sz.eq}. Indeed,
assuming Condition\,\((iv)\), we know that the switchable pattern
\begin{sequation}
U:=\sum_{\atop{S\sb B}{S\neq\o}}(-1)^{\abs{S}}q^{n-\dim\spn{S}}\spn{S}
\equiv\sum_{\atop{S\sb B}{S\neq\o}}(-1)^{\abs{S}}\pmod{r}
\end{sequation}%
is zero modulo $r$ in any $x\neq0$. However, in $0$ it is nonzero modulo $r$, as by
Theorem\,\ref{sz.ss},
\begin{sequation}
U(0)
\,\,=\,\,q\abs{\Hy_0^B}-\abs{\Hy^B}-q^n
\,\,=\,\,(q-1)\abs{\Hy^B}-q^n
\,\,\equiv\,\,-q^n
\,\,\equiv\,\,-1
\,\,\not\equiv\,\,0\pmod{r}.
\end{sequation}%
Hence, by Theorem\,\ref{sz.eq}, $B$ is a blocking set.

To verify the additional statement, assume that Condition\,\((iii)\) or Condition\,\((iv)\) is not
fulfilled for $x=0$. Then, as we have shown already, $B$ is not a blocking set, so that no
switchable pattern is a (modulo $r$ nonvanishing) multiple of $\{0\}$. In particular, this holds
for the pattern $U$ above. Therefore, as already $U(0)\not\equiv0\pmod{r}$, $U$ must differ
from the pattern $U(0)\{0\}$, and be nonzero modulo $r$ in another point $x$. However, for
$x\neq0$, $U(x)$ is, modulo $r$, exactly the value of the sums in Condition\,\((iii)\) and
Condition\,\((iv)\); hence, both conditions are not met in that point, too.
\end{Beweis}

We also provide the following more quantitative version:

\begin{Satz}\label{sz.mr}
Let $q$ be a prime power, $\o\neq B\sb\V:=\F[q]\n$ and assume $r>1$ is a divisor of $q-1$.
Then
$$
\sum_{\atop{S\sb B}{\spn{S}\ni x}}(-1)^{\abs{S}}\ \equiv\
-\abs{\Hy^{B\cup\{x\}}}\pmod{r}\quad\text{ for all $x\in\V$,}
$$
and
$$
\abs{\Hy^{B\cup\{x\}}}\ \not\equiv\ 0\pmod{r}\quad\text{ for at least one $x\in\V\ssm0$}
$$
if and only if $B$ is not a blocking set.
\end{Satz}

\begin{Beweis}
The first part can be deduced from Theorem\,\ref{sz.ss} as follows:
\begin{sequation}
\sum_{\atop{S\sb B}{\spn{S}\ni x}}(-1)^{\abs{S}}
\ \equiv\ \sum_{\atop{S\sb B}{\spn{S}\ni x}}(-1)^{\abs{S}}q^{n-\dim\spn{S}}
\ \equiv\ 1\abs{\Hy_x^B}-\abs{\Hy^B}
=-\abs{\Hy^B\sm\Hy_x^B}
=-\abs{\Hy^{B\cup\{x\}}}\pmod{r}.
\end{sequation}%
The second part ensues from this equality and Equivalence\,\ref{sz.eq2}.
\end{Beweis}

We close this section with an example. This example shows that, in Equivalent\,\((v)\) of
Theorem\,\ref{sz.eq}, we cannot ignore the point of origin $0\in\V$. If this were possible, it
would lead to a characterization of blocking sets trough the linear independence of the
corresponding available moves (as patterns over $\V\ssm0$). Actually, during our research,
we had the idea that this could be possible. In the similar switching game in our paper
\cite{schBer2} it was possible to ignore the point of origin (and we then played the game
over the projective space $\PG_{n-1}(\F[q])$). The example is the following:


\begin{Beispiel}
Let $\V:=\F[2]^3$ and $B:=\{e_1,e_2,e_3+e_2,e_3+e_1\}$, where $e_1$, $e_2$ and $e_3$
denote the vectors of the standard base of $\V$. Then $\spn{e_1+e_2}^\perp$ is not
blocked by $B$, so that we cannot switch patterns of the form $\ell\{0\}\neq\o$ in any of our
games. However,
\begin{equation}
e_1^\perp-e_2^\perp-\spn{e_2}-\spn{e_3+e_2}+\spn{e_1}+\spn{e_3+e_1}\,=\,\o.
\end{equation}
This linear dependence would be a proper switchability condition over the board $\V\ssm0$,
where $\ell\{0\}=\o$. Indeed, it is easy to check that all summands here are legal moves in
the game of Equivalent\,\((v)\) of Theorem\,\ref{sz.eq}.
\end{Beispiel}

In the next section, we will connect graphs to blocking sets. Actually, with this connection,
one can show that another counterexample arises from the complete tripartite graph
$K_{7,7,7}$, for instance. Hence, even in the more special graph theoretical situation, the
point of origin is indispensable.


%--------------------------------------------------------------------------------------------------------------
\section{Graph Colorings}\label{sec.gc}

In this section, let $G=(V,E)$ be a graph on $n$ vertices with at least one edge. For vertices
$v\in V$, let
 \rand\rand\begin{equation}
"\hat v"\,:=\,(\?{u=v})_{u\in V}\,\in\,"\V"\,:=\,\F[q]^V
\end{equation}
be the tuple with a $1$ in position $v$ and zeros elsewhere. For edges
\rand$e="uv":=\{u,v\}\in E$, we define
 \rand\begin{equation}
"\hat e"\,:=\,\hat u-\hat v\,\in\,\V.
\end{equation}
Obviously, this is not well defined, since the edge $e$ can be written in two ways, as $uv$
and as $vu$. However, $\hat e$ is well defined up to the sign only, but the sign will not
matter in our investigations. Therefore, we just stick to one of the two possible choices for
each edge $e$. With that, we define to every set $S\sb E$ of edges a corresponding set
$\hS$ of vectors,
 \rand\begin{equation}
"\hS"\,:=\,\{\hat e\!\mit\!e\in S\}\,\sb\,\V,
\end{equation}
and a corresponding partition $\pi(S)\,=\,\pi(V,S)$ of the set of vertices $V$,
 \rand\begin{equation}
"\pi(S)"\,:=\,\{U\sb V\mit\text{$U$ \psize{is vertex set of a connected component of the
graph} $(V,S)$}\}.
\end{equation}
Hence, if \rand$"\Pi(V)"$ denotes the set of all partitions $\pi$ of $V$, and $\Pi_c(G)$
denotes the set of those $\pi$ whose blocks $U\in\pi$ are connected in $G$,
 \rand\begin{equation}
"\Pi_c(G)"\,:=\,\{\pi\in\Pi(V)\mit \text{$\fa\,U\in\pi\DP G|_U$ \psize{is connected}}\},
\end{equation}
then
\begin{equation}
\{\pi(S)\mit S\sb E\}=\Pi_c(G).
\end{equation}
Indeed, one can easily find to any $\pi\in\Pi_c(G)$ an edge set $S_\pi\sb E$ with
$\pi(S_\pi)=\pi$, and use this fact to prove this equation. Moreover, for $x\in\V=\F[q]\n[V]$,
we say that a subset $U\sb V$ of vertices is \emph{\(x\)"~balanced} if the restriction
$x|_U\DP U\!\lto\F[q]$, $u\lmto x_u$ has vanishing value sum,
\begin{equation}
\sum_{u\in U}x_u\,=\,0.
\end{equation}
A partition $\pi$ of $V$ is \(x\)"~balanced if each of its blocks is \(x\)"~balanced. We denote
with $\spn{\pi}_q$, or just \rand$"\spn{\pi}"$, the subspace of all vectors $x$ for which $\pi$
is \(x\)"~balanced,
\begin{equation}
\spn{\pi}\,=\,\spn{\pi}_q\,:=\,\bigl\{x\in\V\mit\text{$\textstyle\sum\limits_{u\in U}x_u=0$\ \ \psize{for all} $U\in\pi$}\bigr\}\,\leq\,\V.
\end{equation}
We can use our definitions to calculate the linear spans $\spn{\hS}$ that correspond to edge
sets $S\sb E$. In the simplest case, if $(V,S)$ is connected,
\begin{equation}
\spn{\hS}\,=\,\{x\in\V\mit\text{$\textstyle\sum\limits_{v\in V}x_v=0$}\}\,=\,\spn{\{V\}}.
\end{equation}
Here, $\{V\}$ is the trivial partition of $V$, and our definition of $\spn{\pi}$ simplifies for
$\pi=\{V\}$ to the set in the middle. That this set contains $\hS$ and its linear span
$\spn{\hS}$ is obvious. Conversely, that the set in the middle is contained in $\spn{\hS}$
follows easily from the fact that, due to the connectedness of $(V,S)$, all vectors $x\in\V$
with just one $1$ and one $-1$ entry (apart from zeros) already belong to $\spn{\hS}$. The
general case can be reduced to this case. Obviously, for any $S\sb E$,
\begin{equation}
\spn{\hS}\,=\,\spn{\pi(S)}.
\end{equation}
In particular,
\begin{equation}
\dim\spn{\hS}\,\,=\,\,\dim\spn{\pi(S)}\,\,=\,\,n-\abs{\pi(S)}.
\end{equation}
We will also need that
\begin{equation}\label{eq.dis}
\begin{split}
\sum_{\atop{S\sb E}{\spn{\pi(S)}\ni x}}(-1)^{\abs{S}}
&=\sum_{\atop{\pi\in\Pi_c(G)}{\spn{\pi}\ni x}}\,
    \sum_{\atop{S\sb E}{\pi(S)=\pi}}(-1)^{\abs{S}}\\
&=\sum_{\atop{\pi\in\Pi_c(G)}{\spn{\pi}\ni x}}\,
    \sum_{\atop{S\sb E}{\pi(S)=\pi}}\,\prod_{U\in\pi}\,(-1)^{\abs{S|_U}}\\
&=\sum_{\atop{\pi\in\Pi_c(G)}{\spn{\pi}\ni x}}\,
    \prod_{U\in\pi}\sum_{\atop{S\sb E(G|_U)}{\pi(U,S)=\{U\}}}\!\!\!(-1)^{\abs{S}},
\end{split}
\end{equation}
where, in the first equation, we replaced the condition $\spn{\pi(S)}\ni x$, which means that
$\pi(S)\in\Pi_c(G)$ is \(x\)"~balanced, by the condition that $\pi(S)$ is equal to a partition
$\pi\in\Pi_c(G)$ that is \(x\)"~balanced. In the second equation, we just decomposed the
edge sets $S$ into their connected components $S|_U$. Finally, in the third equation, we
have to find (and then sum over) all edge sets $S\sb E$ with the blocks $U$ of $\pi$ as
connected components. This is the same as, first, to find to every block $U$ of $\pi$ all
edge sets $S_U$ that connect $U$, and, second, to combine them in all possible ways
(which the distributive law accomplishes for us automatically).

With these definitions, it should be clear that $G$ has a proper vertex coloring with $q$
colors if and only if $\hE$ is not a blocking set,
 \rand\begin{equation}\label{eq.cc}
"\cC_q(G)":=\{c\in\V\!\mit\!\text{$c$ \psize{is coloring of} $G$}\}\,\neq\,\o\ \ \,\lEqi\,\ \
\Hy^\hE\,\neq\,\o.
\end{equation}
Indeed, if $c\in\V$ ($c\DP V\lto\F[q]$) is a vertex labeling then, for any edge $e=uv\in E$,
\begin{equation}
c(u)\neq c(v)\ \ \lEqi\ \ c(u)-c(v)\neq0\ \ \lEqi\ \ c\cdot\hat e\neq0\ \ \lEqi\ \ c^\perp\nni\hat e,
\end{equation}
with the standard scalar product $\pm\,c\cdot\hat e=c(u)-c(v)$ in $\V$. Hence,
\begin{equation}
c\,\in\,\cC_q(G)\ \ \lEqi\ \ c^\perp\,\in\,\Hy^\hE.
\end{equation}
The correspondence between hyperplanes and colorings is $1$ to $q-1$ here, as there are
$q-1$ elements in the multiplicative group of $\F[q]$ (and $0\nin\cC_q(G)$, as $G$ contains
an edge). Hence,
\begin{equation}
\abs{\cC_q(G)}=(q{-}1)\abs{\Hy^\hE}.
\end{equation}
Our correspondence also can be restricted to $\cC_q(G)\sm x^\perp$ and
$\Hy^{\hE\cap\{x\}}$ (for any $x\in\V$), so that
\begin{equation}
\abs{\cC_q(G)\sm x^\perp}=(q{-}1)\abs{\Hy^{\hE\cup\{x\}}}.
\end{equation}
In particular,
\begin{equation}
q-1\quad\text{divides}\quad\abs{\cC_q(G)\sm x^\perp},
\end{equation}
which we will not mention further when we use the quotient of these two numbers. Another
well known fact, is the following formula:
\begin{equation}\label{eq.cq}
\abs{\cC_q(G)}=\sum_{S\sb E}(-1)^{\abs{S}}q^{\abs{\pi(S)}}.
\end{equation}
We know this already from Lemma\,\ref{lem.tu}. However, a main difference here, and the
main reason for the additional results about graphs in this section, is that this does not just
hold for one initially given prime power $q$. In contrast to the blocking set candidates
$B\sb\V:=\F[q]^V$ of the last section, the graph $G$ is defined independently from $q$ and
$\F[q]$. Accordingly, the set $\hE$ can be interpreted as a subset of $\F[q]^V$ for any
prime power $q$. Hence, $\cC_q(G)$ is defined, and the formula holds, for every prime
power $q$. Actually, not even the restriction to prime powers is required here. We just have
to extend our definition of $\cC_q(G)\sb\V:=\F[q]^V$ slightly. In fact, our definition inside
Statement\,\eqref{eq.cc} makes sense for any set $\F[q]$ of $q$ fixed colors, if we set
$\V:=\F[q]^V$ as before. We only need $\F[q]$ to be a field when we apply the results of the
previous sections, and then $q$ necessarily has to be a prime power.

We start the transfer of results with the following specialization of Theorem\,\ref{sz.eq2},
which contains one additional equivalent based on Equation\,\eqref{eq.dis}:

\begin{Satz}\label{sz.eqc}
Let $q$ be a prime power. If $r>1$ is a divisor of $q-1$, then the following are equivalent:
\begin{enumerate}[(i)]
\item $G$ has a \(q\)"~coloring.
\item $\,\displaystyle\sum_{S\sb E}\,(-1)^{\abs{S}}q^{\abs{\pi(S)}}\,\neq\,0.$
\item $\displaystyle\sum_{\atop{S\sb E}{\spn{\pi(S)}\ni x}}
    (-1)^{\abs{S}}q^{\abs{\pi(S)}}\,\neq\,0\,\ $ for an $x\in\V$.
\item $\displaystyle\sum_{\atop{S\sb E}{\spn{\pi(S)}\ni x}}(-1)^{\abs{S}}
    \,\not\equiv\,0\pmod{r}\,\ $ for an $x\in\V$.
\item $\displaystyle\sum_{\atop{\pi\in\Pi_c(G)}{\spn{\pi}\ni x}}\,
    \prod_{U\in\pi}\sum_{\atop{S\sb E(G|_U)}{\pi(U,S)=\{U\}}}\!\!\!(-1)^{\abs{S}}
    \,\not\equiv\,0\pmod{r}\,\ $ for an $x\in\V$.
\end{enumerate}
Moreover, if Condition \((iii)\) or \((iv)\) or \((v)\) is satisfied in $x=0$, then these conditions
hold true in a further point $x\in\V$.
\end{Satz}

From Theorem\,\ref{sz.mr}, we obtain the following:

\begin{Satz}\label{sz.con}
Let $q$ be a prime power, and assume $r>1$ is a divisor of $q-1$. Then
$$
\sum_{\atop{\pi\in\Pi_c(G)}{\spn{\pi}\ni x}}
    \prod_{U\in\pi}\sum_{\atop{S\sb E(G|_U)}{\pi(U,S)=\{U\}}}\!\!\!(-1)^{\abs{S}}
=\sum_{\atop{S\sb E}{\spn{\pi(S)}\ni x}}(-1)^{\abs{S}}\ \equiv\
-\frac{\abs{\cC_q(G)\sm x^\perp}}{q-1}\pmod{r}\quad\text{ for all $x\in\V$,}
$$
and
$$
\frac{\abs{\cC_q(G)\sm x^\perp}}{q-1}\ \not\equiv\ 0\pmod{r}\quad\text{ for at least one $x\in\V\ssm0$,}
$$
if and only if $G$ is \(q\)"~colorable.
\end{Satz}

We also mention that the expression $\abs{\cC_q(G)\sm x^\perp}$ in this theorem can be
replaced by $-\abs{\cC_q(G)\cap x^\perp}$ frequently. For example, we know that
\begin{equation}
q!\quad\text{divides}\quad\abs{\cC_q(G)},
\end{equation}
if $G$ is not colorable with just $q-2$ colors, as there are $q!$ many permutations of $q$
colors. Hence, in this case, if $r\neq q-1$, indeed,
\begin{equation}\label{eq.smi}
\frac{\abs{\cC_q(G)\sm x^\perp}}{q-1}
=\frac{\abs{\cC_q(G)}}{q-1}-\frac{\abs{\cC_q(G)\cap x^\perp}}{q-1}
\equiv-\frac{\abs{\cC_q(G)\cap x^\perp}}{q-1}\pmod{r}.
\end{equation}

For $r=2$, we also obtain the following corollary:

\begin{Korollar}
Let $q$ be an odd prime power. Then
$$
\Abs{\{S\sb E\mit\spn{\pi(S)}\ni x\}}\ \equiv\ \frac{\abs{\cC_q(G)\sm x^\perp}}{q-1}\pmod{2}\quad\text{ for any $x\in\V$,}
$$
and
$$
\Abs{\{S\sb E\mit\spn{\pi(S)}\ni
x\}}\ \not\equiv\ 0\pmod{2}\quad\text{ for one $x\in\V\ssm0$}
$$
if and only if $G$ is \(q\)"~colorable.
\end{Korollar}

To achieve further simplifications in our colorability criteria, we have to examine the most
inner sum in Condition\,\((v)\) of Theorem\,\ref{sz.eqc}. Formulated for $V$ and $G$,
instead of $U$ and $G|_U$, this is
\begin{equation}
\sum_{\atop{S\sb E}{\pi(S)=\{V\}}}\!\!\!(-1)^{\abs{S}}.
\end{equation}
For this sum, one can find some interesting interpretations in the literature. At first, one may
try to pair off and cancel as many as possible oppositely signed summands. In this way,
Whitney showed in \cite{wh} that one can restrict the summation range to subsets $S$ that
do not contain a broken circuit. Here, a broken circuit is a circuit with its biggest edge
removed, i.e., biggest with respect to a given total ordering on $E$. Another interesting
interpretation was given by Greene and Zaslavsky in \cite[Theorem\,7.3]{grza}, with a
combinatorial proof in \cite[Theorem\,1.2\,\&\,1.3]{gesa}. It states that our sum counts the
acyclic orientations of $G$ with one fixed given sink $v_0\in V$. In our investigations, we
have the additional advantage that we have to count only modulo $r$. This allows the
following reinterpretation in terms of colorings based on Equation\,\eqref{eq.cq}:
\begin{equation}
\sum_{\atop{S\sb E}{\pi(S)=\{V\}}}\!\!\!(-1)^{\abs{S}}
=\sum_{\atop{S\sb E}{\abs{\pi(S)}=1}}\!\!\!(-1)^{\abs{S}}
\equiv\sum_{S\sb E}(-1)^{\abs{S}}r^{\abs{\pi(S)}-1}=\tfrac{1}{r}\abs{\cC_r(G)}\pmod{r}.
\end{equation}
With this, the last condition in Theorem\,\ref{sz.eqc} can be rewritten:
\begin{Satz}
Let $q$ be a prime power. If $r>0$ is a divisor of $q-1$, then $G$ is vertex colorable with
$q$ many colors if and only if there exists an $x\in\V$ with
$$
\sum_{\atop{\pi\in\Pi_c(G)}{\spn{\pi}\ni x}}
    \prod_{U\in\pi}\,\frac{1}{r}\Abs{\cC_r(G|_U)}
    \not\equiv0\pmod{r}.
$$
\end{Satz}

The sum in this theorem simplifies even more if $r=2$, because
$\tfrac{1}{2}\abs{\cC_2(G|_U)}$ is nonzero modulo $2$ only if $G|_U$ is bipartite and
connected. Based on this observation, we say that a set $U\sb V$ of vertices is
\emph{\(G\)"~bipartite} if the induced subgraph $G|_U$ is connected and bipartite. A
partition $\pi$ of $V$ is \(G\)"~bipartite if each of its blocks is \(G\)"~bipartite. Finally, we say
that $x$ is \emph{odd} if the number of \(x\)"~balanced and \(G\)"~bipartite partitions of $V$
is odd. With these definitions, we see that $x$ is odd if and only if the sum in the last
theorem is nonzero modulo $r=2$. Therefore, we obtain the following main result:

\begin{Satz}
Let $q$ be an odd prime power. Then a graph $G$ admits a vertex coloring with $q$ colors
if and only if it admits an odd vertex labeling $x\DP V\!\lto\F[q]$.
\end{Satz}

Moreover, the additional statement of Theorem\,\ref{sz.eqc} holds accordingly. If the
all"=zero labeling $0\in\V$ is odd, then there are also other odd labelings $x\neq0$. Our
more precise congruency in Theorem\,\ref{sz.con} can also be specialized:

\begin{Satz}\label{sz.odd}
Let $q$ be an odd prime power. Then, for any vertex labeling $x\in\V:=\F[q]^V$,
$$
\text{$\dfrac{\abs{\cC_q(G)\sm x^\perp}}{q-1}$ is odd}\ \ \lEqi\,\ \text{$x$ is odd}.
$$
\end{Satz}

If $q>3$ and $G$ is not colorable with just $3$ colors, then $q(q-1)(q-2)(q-3)$ divides
$\abs{\cC_q(G)}$. Hence, $\tfrac{\abs{\cC_q(G)}}{q-1}$ is then even, and, similarly as in
Equation\,\eqref{eq.smi},
\begin{equation}
\dfrac{\abs{\cC_q(G)\cap x^\perp}}{q-1}\ \equiv\ \dfrac{\abs{\cC_q(G)\sm x^\perp}}{q-1}\pmod{2}.
\end{equation}
In particular, (by Theorem\,\ref{sz.odd}) in this case any odd labeling $x\in\V$ guarantees
not just a coloring $c$ that is not orthogonal to it, but it guarantees also at least one coloring
that is orthogonal to it.

Since the edge colorings of a graph are the vertex colorings of its line graph, we may
translate our theorems into the language of edge colorings. This is straightforward. We just
define the corresponding terms and formulate the theorem: We say that a set $F\sb E$ of
edges is \emph{junction"=free} if the induced subgraph $G|_F$ is a path or an even cycle. If
the restriction to $F$ of an edge labeling \rand$"y"\DP E\lto\F[q]$ has zero sum, $\sum_{e\in
F}y_e=0$, we say that a set $F\sb E$ of edges is \emph{\(y\)"~balanced}. We also say that
a partition $\pi$ of $E$ is \(y\)"~balanced, respectively junction"=free, if each of its blocks is
\(y\)"~balanced, respectively junction"=free. Finally, we say that $y$ is \emph{odd} if the
number of \(y\)"~balanced and junction"=free partitions of $E$ is odd. With these definitions,
we obtain the following result:

\begin{Satz}
If $q$ is an odd prime power, then a graph $G$ admits an edge coloring with $q$ colors if
and only if it admits an odd edge labeling $y\DP E\lto\F[q]$.
\end{Satz}

If \rand$"\cC'_q(G)"$ denotes the set of proper edge colorings $E\lto\F[q]$, we also have
the following:

\begin{Satz}
Let $q$ be an odd prime power. Then, for any edge labeling $y\in\F[q]^E$,
$$
\text{$\dfrac{\abs{\cC'_q(G)\sm y^\perp}}{q-1}$ is odd}\ \ \lEqi\,\ \text{$y$ is odd}.
$$
\end{Satz}

We finish with some remarks about the number and the lengths of paths in junction"=free
edge partitions: If the number of vertices of odd degree is $2t$, then the number of
unclosed paths in any junction"=free partition $\pi$ of $E$ must be at least $t$. That is
because, any vertex $v$ of odd degree must be the end of at least one path in $\pi$, as all
other paths through $v$ cover an even number of its edges. It follows that the average
length of the paths in $\pi$ is at most $\abs{E}/t$. Hence, for \(q\)"~regular graphs, this
upper bound for the average length would be $q$.


%% ------------------------------------------------------------------------------
\vspace{.9cm}

\noindent\textbf{Acknowledgement:}\\
We gratefully acknowledge the support provided by the King Fahd University of Petroleum
and Minerals under the project number IN100028. We thank Ahmet Tatar for his help, and
also Ellen Touchstone of the Continuing Support Team of the Language Centre at Xi'an
Jiaotong-Liverpool University.

%-------------------------------------------------------------------------------
%-------------------------------------------------------------------------------

\begin{thebibliography}{}
\bibitem[GeSa]{gesa}
  D.\,D.\,Gebhard, B.\,E.\,Sagan:
    Sinks in Acyclic Orientations of Graphs.\\
    \textit{Journal of Combinatorial Theory, Series B 80 (2000), 130-146.}
\bibitem[GrZa]{grza}
  C.\,Greene, T.\,Zaslavsky:\\
    On the Interpretation of Whitney Number through Arrangements of Hyperplanes,
    Zonotopes, Non-Radon Partitions, and Orientations of Graphs.\\
    \textit{Trans.\ Amer.\ Math.\ Soc.\ 280 (1983), 97-126.}
\bibitem[Sch1]{schBer}
  U.\,Schauz: Colorings and Nowhere Zero Flows of Graphs in Terms of Berlekamp's
  Switching Game\\
  \textit{The Electronic Journal of Combinatorics 18/1 (2011), \#P65.}
\bibitem[Sch2]{schBer2}
  U.\,Schauz: Anti-Codes in Terms of Berlekamp's Switching Game\\
  \textit{The Electronic Journal of Combinatorics 19/1 (2012), \#P10.}
\bibitem[Sch3]{schAlg}
  U.\,Schauz: Algebraically Solvable Problems:\\
  Describing Polynomials as Equivalent to Explicit Solutions\\
  \textit{The Electronic Journal of Combinatorics 15 (2008), \#R10.}
\bibitem[Wh]{wh} H.\,Whitney: A Logical Expansion in Mathematics.\\
    \textit{Bull.\ Amer.\ Math.\ Soc.\ 38 (1932), 572-579.}
\end{thebibliography}
\end{document}