\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.29}{25(3)}{2018}

\usepackage{url}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}


\newcommand{\rarr}{\rightarrow}
\newcommand{\sm}{\setminus}

\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}

\newcommand{\mP}{\mathcal{P}}

%\newtheorem{thm}{Theorem}
%\newtheorem{lemma}[thm]{Lemma}

%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Jan 21, 2017}{Jul 2, 2018}{Aug 24, 2018}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05C20,05C15} 

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the 
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.  
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{The authors. Released under the CC BY-ND license (International 4.0).}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% If needed, include a line break (\\) at an appropriate place in the title.
\title{Linear Bound for Majority Colourings of Digraphs}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

\author{Fiachra Knox\thanks{Research of the first author was supported by a PIMS postdoctoral fellowship.}\\
\small Department of Mathematics\\[-0.8ex]
\small Simon Fraser University\\[-0.8ex]
\small Burnaby, B.C., Canada\\
\small\tt fknox@sfu.ca\\
\and 
Robert \v{S}\'{a}mal\thanks{The second author was supported by grant GA \v{C}R 16-19910S.}\\
\small Computer Science Institute\\[-0.8ex] 
\small Charles University\\[-0.8ex] 
\small Prague, Czech Republic\\
\small\tt samal@iuuk.mff.cuni.cz}

\begin{document}

\maketitle

\begin{abstract} Given $\eta \in [0, 1]$, a colouring $C$ of $V(G)$ is an \emph{$\eta$-majority colouring} if at most $\eta d^+(v)$ out-neighbours of $v$ have colour $C(v)$, for any $v \in V(G)$.
We show that every digraph $G$ equipped with an assignment of lists $L$, each of size at least $k$, has a $2/k$-majority $L$-colouring.
For even $k$ this is best possible, while for odd $k$ the constant $2/k$ cannot be replaced by any number less than $2/(k+1)$.
This generalizes a result of Anholcer, Bosek and Grytczuk, who proved the cases $k=3$ and $k=4$ and claim a weaker result for general $k$.
\end{abstract}

\section{Introduction}

Given a digraph $G$, we write $V(G)$ and $E(G)$ for the vertex and edge set of a digraph $G$, respectively.
For $v \in V(G)$, we denote by $d^+(v)$ the out-degree of $v$.
Given $\eta \in [0, 1]$, a (not necessarily proper) colouring $C$ of $V(G)$ is an \emph{$\eta$-majority colouring} if at most $\eta d^+(v)$ out-neighbours of $v$ have colour $C(v)$, for any $v \in V(G)$.
A $1/2$-majority colouring is referred to simply as a \emph{majority colouring}.
This concept was introduced in connection to neural networks by van der Zypen~\cite{vdZmathOv}, who asked whether every digraph has a majority colouring with a bounded number of colours.
This question was answered by Kreutzer, Oum, Seymour, van der Zypen and Wood~\cite{ZypenWoodetal}, who showed that $4$ colours always suffice 
and ask, whether $3$ colours do. 

We consider the list-colouring version of this problem. 
For a set $S$, we denote by $\mP(S)$ the power set of $S$.
Given a digraph $G$ and an assignment $L: V(G) \rarr \mP(\N)$ of lists to vertices of $G$, an \emph{$L$-colouring} $C: V(G) \rarr \N$ of $G$ is a colouring of $V(G)$ such that $C(v) \in L(v)$ for every $v \in V(G)$.
If $G$ has an $\eta$-majority $L$-colouring for any such assignment $L$ whose lists are all of size at least $k$, we say that $G$ is \emph{$\eta$-majority $k$-choosable}.
Anholcer, Bosek and Grytczuk~\cite{ABG} showed that every digraph $G$ is $1/2$-majority $4$-choosable. 
As noted by David Wood (personal communication), their method can be extended to show that every digraph is $1/k$-majority $k^2$-choosable for every $k \geq 2$.
Our Theorem~\ref{thm:Main} improves on this result.

\begin{theorem} \label{thm:Main} For any integer $k \geq 2$, every digraph $G$ is $2/k$-majority $k$-choosable.
\end{theorem}

Theorem~\ref{thm:Main} was proved independently by Gir\~{a}o, Kittipassorn and Popielarz~\cite{GKP}.
The case $k=2$ is trivial.
Previously, Anholcer, Bosek and Grytczuk~\cite{ABG} showed that Theorem~\ref{thm:Main} holds 
in the cases $k=3$ and $k=4$ and conjectured that $2/k$ can be replaced by $1/2$ when $k = 3$.
Theorem~\ref{thm:Main} is best possible when $k$ is even, as shown by the example of a $k/2$-regular tournament on $k+1$ vertices (that is, all vertices 
have both in-degree and out-degree equal to $k/2$). If we make all lists equal, 
then some vertex must have an out-neighbour of the same colour, and this out-neighbour represents $2/k$ of its out-neighbourhood.
When $k$ is odd, a similar example shows that we cannot replace $2/k$ by any number less than $2/(k+1)$.

\section{Proof of Theorem~\ref{thm:Main}}

We denote by $vw$ an edge from a vertex $v$ of a digraph to another vertex~$w$.
The proof of Theorem~\ref{thm:Main} relies on the following lemma. 

\begin{lemma} \label{lem:Key} Let $k \geq 2$ be an integer and let $G$ be a digraph on a vertex set $V(G) = S \cup T$, such that $G[S]$ is strongly connected, $G[T]$ is
  edgeless and there are no edges from $T$ to $S$.
Let $C_T$ be any colouring of $T$ and let $L:S\rarr \mP(\N)$ be an assignment of lists, each of size at least $k$, to vertices in $S$.
  Then there exists an extension $C$ of $C_T$ to $V(G)$ with $C(v) \in L(v)$ for each $v \in S$, such that no vertex $v \in S$ has more than $2d^+(v)/k$ out-neighbours with the same colour as $v$.
\end{lemma}

\proof For any colouring $C$ of $V(G)$, we define the function $f_C: S \rarr \R$ by
$$f_C(v) = \frac{|\{w \in N^+(v) \mid C(w) = C(v)\}|}{d^+(v)}$$
for each vertex $v \in S$; 
i.e., $f_C(v)$ is the proportion of out-neighbours of $v$ which have the same colour as $v$ under $C$.
Given $v \in S$, we write $d^+_S(v) = |N^+(v) \cap S|$.

Let $A$ be the non-negative real $S \times S$ matrix with entries $A_{vw} = 1/d^+_S(v)$ if $vw$ is an edge of $G$ and $A_{vw} = 0$ otherwise.
We have $A{\bf j} = {\bf j}$ (where ${\bf j}$ is the vector of all $1$'s).
On the other hand if $A{\bf y} = c{\bf y}$ for any vector ${\bf y}$, then choose $v \in S$ such that $|y_v|$ is maximal;
now $|cy_v| = |\sum_{w \in S} A_{vw} y_w| \leq \sum_{w \in S} A_{vw} |y_v| = |y_v|$ and so $|c| \leq 1$.
Thus, the spectral radius of $A$ is $1$.

By applying the Perron--Frobenius Theorem (see, e.g., \cite[Theorem 8.8.1]{godsil2013algebraic}) to~$A^\top$, 
noting that $G[S]$ is strongly connected, we obtain an eigenvector ${\bf x}$ of~$A^\top$ with positive entries and eigenvalue $1$.
We remark that by normalizing~${\bf x}$ we could obtain a stationary distribution of the uniform random walk on $G[S]$.

Consider an extension $C$ of $C_T$ with $C(v)\hspace{-1pt}\in L(v)$ for each $v \in S$ such that $\sum_{v \in S} x_v f_C(v)$ is minimized.
We claim that $C$ satisfies the requirements of the lemma.
For brevity we write $f$ for $f_C$.
It suffices to show that $f(v) \leq 2/k$ for every $v \in S$.
Observe that 
\begin{equation} \label{eq:minimized sum}
\sum_{v \in S} x_v f(v) = \sum_{\stackrel{vw \in E(G)}{C(v) = C(w)}} \frac{x_v}{d^+(v)}.
\end{equation}

Fix a vertex $v \in S$.
We define $g: L(v) \rarr \R$ by
$$g(i) = \sum_{\stackrel{w \in N^+(v)}{C(w) = i}} \frac{x_v}{d^+(v)} + \sum_{\stackrel{u \in N^-(v)}{C(u) = i}} \frac{x_u}{d^+(u)}$$
for $i \in L(v)$.
Observe that if $v$ were recoloured with colour $i$, then (\ref{eq:minimized sum}) would change by $g(i) - g(C(V(G)))$.
By the minimality of $C$ and the definition of $g$ we have that $g(i) \geq g(C(v)) \geq x_v f(v)$.
Since $A^{\top} {\bf x} = {\bf x}$,
$$x_v = \sum_{u \in N^-(v)} \frac{x_u}{d^+_S(u)} \geq \sum_{u \in N^-(v)} \frac{x_u}{d^+(u)}$$
and hence
$$2x_v \geq \sum_{i \in L(v)} g(i) \geq kx_v f(v).$$ 
Since $x_v > 0$, we have $f(v) \leq 2/k$.
It follows immediately that $C$ satisfies the requirements of the lemma.
\endproof

\proof[Proof of Theorem~\ref{thm:Main}] 
Let $L:~V(G)\rarr \mP(\N)$ be an assignment of lists, each of size at least $k$, to vertices of $G$.
We partition $V(G)$ into strongly connected components $S_1, S_2, \ldots, S_r$, where there are no edges from $S_i$ to $S_j$ for any $i < j$.
We write $A_i$ for $\bigcup_{j \in [i]} S_j$ (taking $A_0 = \emptyset$); 
let $C_0$ be the unique colouring of $A_0$.
For each $i = 0, 1, 2, \ldots, r-1$ in turn, we apply Lemma~\ref{lem:Key} 
to the digraph obtained from~$G[A_{i+1}]$ by deleting the arcs in~$G[A_i]$, with $S = S_{i+1}$ and $T = A_i$. 
This gives us an extension of $C_i$ to an $L$-colouring $C_{i+1}$ of $A_{i+1}$ 
such that no $v \in S_{i+1}$ (and hence no $v \in A_{i+1}$) has more than $2d^+(v)/k$ out-neighbours of the same colour.
At the end of this process we obtain $C_r$, which is the desired $2/k$-majority $L$-colouring of~$V(G)$.
\endproof

\section{Future Work} 
The main related open problem is the question, whether every digraph has a majority 3-coloring. 
We refer the reader to~\cite{ZypenWoodetal} for further questions and related results. 
We note that Anholcer, Bosek and Grytczuk~\cite{ABG} prove their result for $k=4$ in a more general setting 
(with weights on the colors). As mentioned earlier, this approach can be extended to prove the existence of $1/k$-majority $k^2$-choosability of every digraph. 
We don't know whether $O(k)$-choosability is true in their more general setting. 

%\begin{itemize}
%  \item and compare it with it
%  \item future problems
%\end{itemize}

\section*{Acknowledgements} 

The authors would like to thank David Wood for presenting this problem at the workshop ``New Trends in Graph Colouring'' in Banff, October 2016, and for many 
helpful comments. 
We are also grateful to the organizers of this wonderful workshop and to our colleagues at the workshop for helpful discussions. 


%\bibliography{Majority}{}
%\bibliographystyle{plain}

\begin{thebibliography}{9}
\bibitem{ABG}
Marcin Anholcer, Bart{\l}omiej Bosek, and Jaros{\l}aw Grytczuk.
\newblock Majority choosability of digraphs.
\newblock {\em Electron. J. Combin.}, 24(3): \#P3.57, 2017.

\bibitem{GKP}
Ant\'onio Gir\~ao, Teeradej Kittipassorn, and Kamil Popielarz.
\newblock Generalized majority colourings of digraphs.
\newblock {\em Combin. Probab. Comput.}, 26(6):850--855, 2017.

\bibitem{godsil2013algebraic}
Chris Godsil and Gordon~F. Royle.
\newblock {\em Algebraic Graph Theory}.
\newblock Graduate Texts in Mathematics. Springer New York, 2013.

\bibitem{ZypenWoodetal}
Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van~der Zypen, and
  David~R. Wood.
\newblock Majority colourings of digraphs.
\newblock {\em Electron. J. Combin.}, 24(2): \#P2.25, 2017.

\bibitem{vdZmathOv}
Dominic van~der Zypen.
\newblock Majority colouring for directed graphs, 2016.
\newblock \url{https://mathoverflow.net/questions/233014}.

\end{thebibliography}


\end{document}