% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.41}{24(3)}{2017}


% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

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

\theoremstyle{remark}



\def\ds{\displaystyle}
\def\red{\color{red}}


\def\T{\mathsf{T}}
\def\K{\mathsf{K}}
\def\L{\mathsf{L}}
\def\P{\mathbb{P}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\vecr{\mathbf{r}}
\def\S{\mathcal{S}}
\def\V{\mathcal{V}}
\def\C{\mathsf{C}}
\def\H{\mathcal{H}}
\def\F{F}
\def\O{\mathcal{O}}
\def\vecv{\mathbf{v}}
\def\Sph{\mathbb{S}}
\def\zero{{\bf 0}}
\def\sd{\operatorname{sd}}
\def\a{\boldsymbol{a}}
\def\p{\boldsymbol{p}}
\def\q{\boldsymbol{q}}
\def\u{\boldsymbol{u}}

\def\x{\boldsymbol{x}}
\def\y{\boldsymbol{y}}
\def\z{\boldsymbol{z}}
\def\diam{\operatorname{diam}}
\def\alt{\operatorname{alt}}
\def\ind{\operatorname{ind}}
\def\KG{\operatorname{KG}}





% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Fair splitting of colored paths}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Meysam Alishahi\\
\small School of Mathematical Sciences\\[-0.8ex]
\small Shahrood University of Technology\\[-0.8ex] 
\small Shahrood, Iran\\
\small\tt meysam\_alishahi@shahroodut.ac.ir\\
\and
Fr\'ed\'eric Meunier \\
\small Universit\'e Paris Est\\[-0.8ex]
\small CERMICS\\[-0.8ex]
\small 77455 Marne-la-Vall\'ee CEDEX, France\\
\small\tt frederic.meunier@enpc.fr
}



% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jun 6, 2016}{Aug 15, 2017}{Aug 25, 2017}\\
\small Mathematics Subject Classifications: 05C69}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
This paper deals with two problems about  splitting fairly a path with colored vertices, where ``fairly'' means that each part contains almost the same amount of vertices in each color. 

Our first result states that it is possible to remove one vertex per color from a path with colored vertices so that the remaining vertices can be fairly split into two independent sets of the path. 
It implies in particular a conjecture of Ron Aharoni and coauthors. The proof uses the octahedral Tucker lemma.

Our second result is the proof of a particular case of a conjecture of D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi about fair splittings of necklaces for which one can decide which thieves are advantaged. The proof is based on a rounding technique introduced by Noga Alon and coauthors to prove the discrete splitting necklace theorem from the continuous one.

\bigskip\noindent \textbf{Keywords:} Tucker's lemma; splitting necklace; independent sets
\end{abstract}
\section{Introduction}

This paper is about fair splittings of paths with colored vertices. ``Fair'' means throughout the paper that for each color $j$, the numbers of vertices of color $j$ in each part differ by at most one.

Given a path $P$ whose vertex set is partitioned into $m$ subsets $V_1,\ldots,V_m$, Aharoni et al.~\cite[Conjecture 1.6]{aharoni2016fair} conjectured that there always exists an independent set $S$ of $P$ such that $|S\cap V_j|\geq |V_j|/2-1$, with strict inequality holding for at least $m/2$ subsets $V_j$. 
 We prove that we can actually remove one vertex from each $V_j$ so that the remaining vertices can be fairly split into two independent sets of $P$ of almost same size. 

 \begin{theorem}\label{main}
Given a path $P$ whose vertex set is partitioned into $m$ subsets $V_1,\ldots,V_m$, there always exist two disjoint independent sets $S_1$ and $S_2$ covering all vertices but one in each $V_j$, with sizes differing by at most one, and satisfying for each $i\in\{1,2\}$
$$ |S_i\cap V_j| \geq  \frac{|V_j|} 2 -1\qquad\mbox{for all $j\in[m]$.}$$
\end{theorem}

 Theorem~\ref{main} implies in particular that the conjecture by Aharoni et al. is true: the equality $|S_1\cap V_j|+|S_2\cap V_j|= |V_j|-1$ holds for every $j$ and thus one of $S_1$ or $S_2$ satisfies the inequality strictly for at least $m/2$ indices $j$.

The Borsuk-Ulam theorem was originally used for proving a special case of their conjecture (Theorem 1.7 of their paper). Here, we use the octahedral Tucker lemma, which is a combinatorial version of the Borsuk-Ulam theorem. 

\bigskip

Another result in combinatorics deals with the fair splitting of a path whose vertices are colored and is a consequence of the Borsuk-Ulam theorem: the splitting necklace theorem. Consider an open necklace of $n$ beads, each having a color $j\in[m]$. We denote by $a_j$ the number of beads of color $j$. A {\em fair $q$-splitting} is the partition of the beads into $q$ parts, each containing $\lfloor a_j/q\rfloor$ or $\lceil a_j/q\rceil$ beads of color $j$. The picturesque motivation is the division of the necklace among $q$ thieves after its robbery. A theorem of Alon~\cite{alon1987splitting} states that such a partition is always achievable with no more than $(q-1)m$ cuts when $a_j$ is divisible by $q$. Using a flow-based rounding argument, Alon, Moshkovitz, and Safra~\cite{alon2006algorithmic} were able to show that such a partition is achievable without this assumption. 
In a paper in which he proved the splitting necklace theorem when $q=2$ via the octahedral Tucker lemma, P{\'a}lv{\"o}lgyi~\cite{palvolgyi2009combinatorial} conjectured that for each $j$ such that $a_j$ is not divisible by $q$, it is possible to decide which thieves get $\lfloor a_j/q\rfloor$ and which get $\lceil a_j/q\rceil$ and to still have a fair $q$-splitting not requiring more than $(q-1)m$ cuts. The conjecture is known to be true when $q=2$ (see~\cite{palvolgyi2009combinatorial}), when $a_j\leq q$ for all $j$ (by a greedy assignment), and when $m=2$ (see~\cite{meunier2014simplotopal}).
With a simple trick inspired by the argument of Alon, Moshkovitz, and Safra, we show that the conjecture is true when the remainder in the euclidian division of $a_j$ by $q$ is $0$, $1$, or $q-1$ for all $j$. This result implies in particular the conjecture for $q=3$.

\section{Fair splitting by independent sets of a path}

%\subsection{Main tool}  

%The Borsuk-Ulam theorem has many applications in combinatorics, see . A generalization of this theorem, Ky Fan's theorem, is useful for strengthening these applications, see ST. Similarly as for the BU theorem with Tucker's lemma, Ky Fan's theorem has a combinatorial counterpart -- Ky Fan's lemma -- which is about the existence of fully-labeled simplices in labelings of triangulation of the sphere. 

\subsection{Proof}

The combinatorial counterpart of the Borsuk-Ulam theorem is Tucker's lemma. Our main tool is a special case of this counterpart when the triangulation is the first barycentric subdivision of the cross-polytope. It turns out that in this case, Tucker's lemma can be directly expressed in combinatorial terms. This kind of formulation goes back to Matou\v{s}ek~\cite{matouvsek2004combinatorial} and Ziegler~\cite{ziegler2002generalized}.


As in oriented matroid theory, we define $\preceq$ to be the following partial order on $\{+,-,0\}$: $$0\preceq +,\quad 0\preceq -,\quad+\mbox{ and }-\mbox{ are not comparable.}$$ We extend it for sign vectors by simply taking the product order: for $\x,\y\in\{+,-,0\}^n$, we have $\x\preceq\y$ if the following implication holds for every $i\in[n]$
$$x_i\neq 0\Longrightarrow x_i=y_i.$$ 

%Ky Fan's lemma restricted to the first barycentric subdivision of the cross-polytope takes the following form.

\begin{lemma}[Octahedral Tucker lemma]\label{lem:oct_tucker}
Let $s$ and $n$ be positive integers. If there exists a map $\lambda:\{+,-,0\}^n\setminus \{\zero\} \rightarrow\{\pm 1,\ldots,\pm s\}$
 satisfying $\lambda(-\x)=-\lambda(\x)$ for all $\x$ and $\lambda(\x)+\lambda(\y)\neq 0$ when $\x\preceq\y$, then $s\geq n$.
\end{lemma}

In the proof, we use the following notations for $\x\in\{+,-,0\}^n$:
$$\x^+=\{i\in[n]\colon x_i=+\}\qquad\mbox{and}\qquad\x^-=\{i\in[n]\colon x_i=-\}.$$  Note that $\x\preceq\y$ if and only if simultaneously $\x^+\subseteq\y^+$ and $\x^-\subseteq\y^-$. We also use the notion of alternating sequences. A sequence of elements in $\{+,-,0\}^n$ is {\em alternating} if all terms are nonzero and any two consecutive terms are different. Given an $\x=(x_1,\ldots,x_n)\in\{+,-,0\}^n$, we denote by $\alt(\x)$ the maximum length of an alternating subsequence of $x_1,\ldots,x_n$.
%\subsection{The proof}

\begin{proof}[Proof of Theorem~\ref{main}]
The proof consists in applying Lemma~\ref{lem:oct_tucker} on a map $\lambda$ we define now. Let $n$ be the number of vertices of $P$. Without loss of generality, we assume that the vertices of $P$ are $1,2,\ldots,n$ in this order when one goes from one endpoint to the other. In the definition of $\lambda$, we use the quantity $t=\max\big\{\alt(\x)\colon \x\in\{+,-,0\}^n\;\,\mbox{s.t.}\;J(\x)=\varnothing\big\}$, where $$J(\x)=\Big\{j\in[m]\colon |\x^+\cap V_j|=|\x^-\cap V_j|=|V_j|/2\quad\mbox{or}\quad\max(|\x^+\cap V_j|,|\x^-\cap V_j|)>|V_j|/2\Big\}.$$ Note that $t\geq 0$.

Consider a vector $\x\in\{+,-,0\}^n\setminus\{\zero\}$. We distinguish two cases.
In the case where $J(\x)\neq\varnothing$, we set  $\lambda(\x)=\pm (t+j')$, where $j'$ is the maximum element in $J(\x)$ and where the sign is defined as follows. When $|\x^+\cap V_{j'}|=|\x^-\cap V_{j'}|=|V_{j'}|/2$, the sign is $+$ if $\min(\x^+\cap V_{j'})<\min(\x^-\cap V_{j'})$ and $-$ otherwise. When $\max\big(|\x^+\cap V_{j'}|,|\x^-\cap V_{j'}|\big)>|V_{j'}|/2$, the sign is $+$ if $|\x^+\cap V_{j'}|>|V_{j'}|/2$, and $-$ otherwise.
In the case where $J(\x)=\varnothing$, we set $\lambda(\x)=\pm\alt(\x)$, where the sign is the first nonzero element of $\x$.

Let us check that the map $\lambda$ satisfies the condition of Lemma~\ref{lem:oct_tucker}. Consider $\x\in\{+,-,0\}^n\setminus\{\zero\}$. The relation $J(-\x)=J(\x)$ immediately implies $\lambda(-\x)=-\lambda(\x)$. Now, consider $\x,\y\in\{+,-,0\}^n\setminus\{\zero\}$ such that $\x\preceq\y$ and $|\lambda(\x)|=|\lambda(\y)|$. We cannot have simultaneously $J(\x)=\varnothing$ and $J(\y)\neq\varnothing$ since then $|\lambda(\x)|\leq t$ and $|\lambda(\y)|>t$. Suppose first that $J(\x)\neq\varnothing$. Since $\x^+\subseteq\y^+$ and $\x^-\subseteq\y^-$, the signs of $\lambda(\x)$ and $\lambda(\y)$ are the same. Suppose now $J(\y)=\varnothing$. Then $J(\x)=\varnothing$. In this case we have $\alt(\x)=\alt(\y)$, and it is simple to check (and well-known) that the first nonzero coordinates of $\x$ and $\y$ have the same value.
%elements of $\x$ and $\y$ are the same.

We can thus apply Lemma~\ref{lem:oct_tucker} with $s=t+m$. It gives $t+m\geq n$, which implies that there exists $\z'\in\{+,-,0\}^n$ such that $J(\z')=\varnothing$ and $\alt(\z')\geq n-m$, which in turn implies that there exists $\z\in\{+,-,0\}^n$ such that $J(\z)=\varnothing$ and $\alt(\z)=|\z^+|+|\z^-|=n-m$. 
%{\color{blue} Without loss of generality, we can assume that the first nonzero element in $\z$ is negative.} 
Let $S_1=\z^+$ and $S_2=\z^-$. They are both independent sets of $P$ and their sizes differ by at most one. 
Because $J(\z)=\varnothing$, we have $|S_1\cap V_j|+|S_2\cap V_j|\leq |V_j|-1$ for all $j$. The fact that $|S_1|+|S_2|=n-m$ leads then to $|S_1\cap V_j|+|S_2\cap V_j|=|V_j|-1$ for all $j$. Now, using again $J(\z)=\varnothing$, we have each of $|S_1\cap V_j|$ and $|S_2\cap V_j|$ non-larger than $|V_j|/2$, which leads directly to the inequality of the statement.
\end{proof}

The proof shows that $S_1$ and $S_2$ alternate along the path $P$. Theorem~\ref{main} combined with this remark leads to the following corollary, 
which improves Theorem~1.8 in the aforementioned paper by Aharoni et al. 
In particular, if $m$ and the number of vertices of $P$ have the same parity, replacing ``path'' by ``cycle'' in the statement of Theorem~\ref{main} does not change the conclusion.

\begin{corollary}\label{cor}
Given an $n$-cycle $C$ whose vertex set is partitioned into $m$ subsets $V_1,\dots,V_m$, there always exist two disjoint sets $S_1$ and $S_2$ covering all
 vertices but one in each $V_j$, with sizes differing by at most one, and satisfying for each $i\in\{1,2\}$
$$|S_i\cap V_j| \geq  \frac{|V_j|} 2 -1\qquad\mbox{for all $j\in[m]$,}$$
where one of the $S_i$'s is an independent set of size $\left\lfloor \frac{n-m} 2\right\rfloor$ and the other induces at most $\left\lceil \frac{n-m} 2\right\rceil- \left\lfloor \frac{n-m} 2\right\rfloor$ edge. 
\end{corollary}


\begin{proof}
Remove an arbitrary edge of the cycle $C$ and apply Theorem~\ref{main} to the path $P$ we obtain this way. When $n-m$ is even, the fact that $S_1$ and $S_2$ alternate implies that they are independent sets of $C$ as well, with the same property as for the case of a path. When $n-m$ is odd, one of $S_1$ and $S_2$ is independent and of size $\left\lfloor\frac{n-m} 2\right\rfloor$ and the other is of size $\left\lceil \frac{n-m} 2\right\rceil$ and may contain the two endpoints of $P$, but the other properties are kept.
\end{proof}


%{\red Moreover, one can see that for the case that $n-m$ is odd, the set $S_i$ with the cardinality $\left\lfloor \frac{n-m} 2\right\rfloor$ always is independent. }

%{\color{blue} (I think that it is nice to be emphasized since it concludes that under the same condition as in the corollary, there are two disjoint independent sets of size  $\left\lfloor \frac{n-m} 2\right\rfloor$ intersecting each $V_i$ in at least $\left\lfloor \frac{|V_j|-1} 2 \right\rfloor$ points.}



\subsection{Extension to arbitrary numbers of independent sets}

%We conjecture that Theorem~\ref{main} can be extended for any number of independent sets. In a graph, a subset of vertices is {\em $q$-stable} if no two of them are at distance less than $q$, where the distance is counted in terms of edges. In particular, the $2$-stable sets of a graph are precisely its independent sets

There is a generalization of the octahedral Tucker lemma -- the $\Z_p$-Tucker lemma~\cite{ziegler2002generalized} -- which deals with an arbitrary prime number $p$ of signs, instead of simply two signs `$+$' and `$-$'. Using this generalization in place of the octahedral Tucker lemma in the proof of Theorem~\ref{main} leads quite easily to a generalization of Theorem~\ref{main} involving a number $p$ of $2$-stable sets. However, it seems that there is no simple way to controle their sizes. We conjecture actually that something stronger holds. In a graph, a subset of vertices is {\em $q$-stable} if no two of them are at distance less than $q$, where the distance is counted in terms of edges. In particular, the $2$-stable sets of a graph are precisely its independent sets.

\begin{conjecture}\label{conj}
Given a positive integer $q$ and a path $P$ whose vertex set is partitioned into $m$ subsets $V_1,\ldots,V_m$ of sizes at least $q-1$,
there always exist pairwise disjoint $q$-stable sets $S_1,\ldots,S_q$ covering all vertices but $q-1$ in each $V_j$, with sizes differing by at most one, and satisfying
$$ |S_i\cap V_j|\geq \left\lfloor \frac{|V_j|+1} q\right\rfloor-1$$ for all $i\in[q]$ and all $j\in[m]$.
\end{conjecture}

%{\red Note that an equivalent statement consists in omitting the lower bounds on the sizes of the $V_j$'s and requiring that the $S_i$'s cover all but $\min(|V_j|,q-1)$ vertices in each $|V_j|$. A statement without if some of $V_j$'s have less than $q-1$ vertices, then we can delete the vertices in these $V_j$'s and consider the path on the remaining vertices whose vertices are in the relative positions they have on $P$. Therefore, omitting the size assumption on $V_j$'s from the statement of Conjecture~\ref{conj}, we reach to an equivalent statement to this conjecture.} 


%{\red Furthermore, we believe in something even stronger: the intersection of each $S_i$ and each $V_j$ has the cardinality at most $|V_j|/q$.} 
 
This conjecture is obviously true for $q=1$ and Theorem~\ref{main} is the special case where $q=2$. The way Theorem~\ref{main} is written might suggest a lower bound of the form $|V_j|/q-1$, but there are simple counterexamples. Consider for instance a case with $q=3$ and $|V_1|=7$. If there were pairwise disjoint 3-stable sets $S_1,S_2,S_3$ covering all vertices of $V_1$ but two, with each $|S_i\cap V_1|$ of size at least $7/3-1=1.33$, we would have $|V_1|-2= |S_1\cap V_1|+|S_2\cap V_1|+|S_3\cap V_1|\geq 6$, a contradiction.

The independent sets $S_i$ of Theorem~\ref{main}  satisfy automatically the additional inequality $|S_i\cap V_j|\leq |V_j|/2$ for all $j$, and it is actually used in the proof itself of that theorem. 
%{\red As it is seen in the proof of Theorem~\ref{main},} the independent sets $S_i$ of Theorem~\ref{main} satisfy in addition the inequality $|S_i\cap V_j|\leq |V_j|/2$ for all $j$. 
We believe that the stronger version of Conjecture~\ref{conj} with an upper bound of $|V_j|/q$ on $|S_i\cap V_j|$ for all $i$ and $j$ is true. 



Since Conjecture~\ref{conj} is true for $q\in\{1,2\}$, the following proposition implies that it is true for any power of two. The other cases remain open.

\begin{proposition}\label{prop}
If Conjecture~\ref{conj} holds for both $q'$ and $q''$, then it holds also for $q=q'q''$.
\end{proposition}

The proof uses extensively the relations 
\begin{equation}\label{eq}
\left\lfloor\frac 1 c\left\lfloor \frac a b\right\rfloor\right\rfloor=\left\lfloor\frac{a}{bc}\right\rfloor\qquad\mbox{and}\qquad\left\lceil\frac 1 c{\left\lceil \frac a b\right\rceil}\right\rceil=\left\lceil\frac{a}{bc}\right\rceil
\end{equation} that hold for any $a,b,c\in\Z$ (actually, only $c\in\Z$ is required for these relations to hold).

Let us prove them. 
We have $\left\lfloor\frac 1 c\left\lfloor \frac a b\right\rfloor\right\rfloor\leq \frac 1 c\left\lfloor\frac a b\right\rfloor \leq\frac a {bc}$, and thus $\left\lfloor\frac 1 c\left\lfloor \frac a b\right\rfloor\right\rfloor\leq\left\lfloor\frac{a}{bc}\right\rfloor$. We also have $\frac a {bc}\geq \left\lfloor\frac{a}{bc}\right\rfloor$ and thus $\frac a {b}\geq c\left\lfloor\frac{a}{bc}\right\rfloor$, which implies since $c\in\Z$ that $\left\lfloor\frac a {b}\right\rfloor\geq c\left\lfloor\frac{a}{bc}\right\rfloor$. Therefore $\left\lfloor\frac 1 c\left\lfloor \frac a b\right\rfloor\right\rfloor\geq\left\lfloor\frac{a}{bc}\right\rfloor$, which implies the left equality. The right one is then immediate since $-\lfloor -x\rfloor=\lceil x\rceil$ for all $x\in\mathbb{R}$.
%The right equality is proved similarly.

\begin{proof}[Proof of Proposition~\ref{prop}]
%{\red Considering the conclusion of the conjecture, without loss of generality, we can assume that $|V_j|\geq q-1$ for each $j$. To see this, let $J=\{j\in[m]\colon |V_j|\geq q-1\}$. Since we all vertices in each  $V_j$ with $j\in J$ must be removed, we can consider the path $P'$ whose vertices are $\bigcup\limits_{j\in J}V_j$ such that these vertices are located in $P'$ according to their relative positions on $P$. Now, to prove the proposition, it is enough to show that the conclusion of the proposition is true for the path $P'$ whose vertices are partitioned into $V_j$'s for $j\in J$. }  
%Consider a path $P$ whose vertices are partitioned into $m$ subsets $V_1,\ldots,V_m$. We assume that the conjecture is true for $q'$ and $q''$. We aim at proving that there exist $q$-stable sets $S_1,\ldots,S_q$ satisfying the conclusion of Conjecture~\ref{conj}. If $S_i\cap V_j=\varnothing$ for an index $j$ such that $|V_j|\leq q-1$, then $S_i$ satisfies the inequalities for this index $j$. Since all vertices in a $V_j$ whose cardinality is at most $q-1$ have to be removed, we assume without loss of generality that $|V_j|\geq q-1$ for all $j$. 

Consider a path $P$ whose vertices are partitioned into $m$ subsets $V_1,\ldots,V_m$ of sizes at least $q-1$. We assume that the conjecture is true for $q'$ and $q''$. We aim at proving that there exist pairwise disjoint $q$-stable sets $S_1,\ldots,S_q$ satisfying the conclusion of Conjecture~\ref{conj}. 

 Since the conjecture is assumed to be true for $q'$, there exist pairwise disjoint $q'$-stable sets $T_1,\ldots,T_{q'}$ of $P$, covering all vertices but $q'-1$ of each $V_j$ and such that for each $i\in[q']$
$$\begin{array}{l}
\ds{|T_i\cap V_j| \geq \left\lfloor  \frac{|V_j|+1} {q'} \right\rfloor-1}\quad\mbox{for all $j\in[m]$,}\quad\mbox{ and}\\ \\
\ds{\left\lceil \frac{n-(q'-1)m} {q'}\right\rceil \geq |T_i| \geq  \left\lfloor \frac{n-(q'-1)m} {q'}\right\rfloor,}
\end{array}$$ where $n$ is the number of vertices of $P$.
The conjecture being also assumed to be true for $q''$, we apply it on the path $Q_i$ whose vertices are the elements of $T_i$ (in the relative positions they have on $P$), for each $i\in[q']$. Note that $|T_i\cap V_j|\geq q''-1$ for every $j$. Therefore, for each $i$, there are pairwise disjoint $q''$-stable sets $S_{i1},\ldots,S_{iq''}$ of $Q_i$ covering all vertices but $q''-1$ of each $T_i\cap V_j$ and such that for each $k\in[q'']$ 
$$\begin{array}{l}
\ds{|S_{ik}\cap V_j| \geq \left\lfloor \frac{|T_i\cap V_j|+1} {q''} \right\rfloor-1}\quad\mbox{for all $j\in[m]$,}\quad\mbox{ and}\\ \\
\ds{\left\lceil \frac{|T_i|-(q''-1)m} {q''}\right\rceil \geq |S_{ik}| \geq  \left\lfloor \frac{|T_i|-(q''-1)m} {q''}\right\rfloor.}
\end{array}$$
Using the relation~\eqref{eq}, we get directly that each of the $q=q'q''$ subsets $S_{ik}$ satisfies
$$\begin{array}{l}
\ds{ |S_{ik}\cap V_j| \geq\left\lfloor \frac{|V_j|+1} q \right\rfloor-1}\quad\mbox{for all $j\in[m]$,}\quad\mbox{and}\\ \\
\ds{\left\lceil \frac{n-(q-1)m} q\right\rceil \geq |S_{ik}| \geq  \left\lfloor \frac{n-(q-1)m} q\right\rfloor.}
\end{array}$$
For each $V_j$, the number of uncovered vertices is exactly $q'-1+q'(q''-1)=q-1$. Moreover, each $T_i$ is $q'$-stable for $P$ and each $S_{ik}$ is $q''$-stable for $Q_i$. Thus each $S_{ik}$ is $q$-stable for $P$ and this finishes the proof.
\end{proof}

The proof of Proposition~\ref{prop} can be adapted in a straightforward way to get that it is also true for the aforementioned version of Conjecture~\ref{conj} with the upper bounds on the $|S_i\cap V_j|$'s. We get thus that this stronger conjecture is also true for any power of two. 

\section{Fair splitting of the necklace with advantages}

The result we prove in this section is the following one. We denote by $r_j$ the remainder of the euclidian division of $a_j$ by $q$.

\begin{theorem}\label{thm:neck}
When $r_j\in\{0,1,q-1\}$ for all $j$, then it is possible to choose for each $j$ such that $r_j\neq 0$, the thieves who get an additional bead of color $j$ and still have a fair $q$-splitting not requiring more than $(q-1)m$ cuts.
\end{theorem}

The following corollary is an immediate consequence of the previous theorem (and answered positively what was identified as a first interesting question by P{\'a}lv{\"o}lgyi).
\begin{corollary}
When there are three thieves, it is possible to choose for each $j$ such that $r_j\neq 0$, the thief (if $r_j=1$) or the two thieves (if $r_j=2$) who get an additional bead and still have a fair $3$-splitting not requiring more than $2m$ cuts.
\end{corollary}

It is proved by rounding in an appropriate way a fair splitting obtained by a continuous version of the splitting necklace theorem.

While in the splitting necklace theorem the cuts have to take place between the beads, this condition is relaxed in the ``continuous version'' of the splitting necklace theorem, also proved by Alon~\cite{alon1987splitting}. In this latter version, cuts are allowed to be located on beads, and  thieves may then receive fractions of beads. In this case, there always exists a {\em continuous fair $q$-splitting} for which each thief receives an amount of exactly $a_j/q$ beads of color $j$, with no more than $(q-1)m$ cuts.

Consider a continuous fair $q$-splitting and denote by $B_j$ the beads of color $j$ that are split between two or more thieves. Our result is obtained by showing that we can move the cuts located on beads in the $B_j$'s so that we reach a ``discrete'' fair $q$-splitting with the desired allocation. If $B_j=\varnothing$, then we already have a discrete fair splitting for the beads of color $j$. For each $j$ with $B_j\neq\varnothing$, we build a bipartite graph $G_j=(U_j,E_j)$ with the thieves on one side and the beads in $B_j$ on the other side. We put an edge between a thief $t$ and a bead $k$ if $t$ receives a part of $k$. For an edge $e=tk\in E_j$, let $u_e\in(0,1)$ be the amount of bead $k$ received by thief $t$. We have for all $k\in B_j$ and all $t\in[q]$ (we identify the thieves with the integers in $[q]$)
\begin{equation}\label{flow}
\sum_{e\in E_j}u_e=|B_j|,\quad\sum_{e\in\delta(k)}u_e=1,\quad\mbox{and}\quad\sum_{e\in\delta(t)}u_e=\alpha_{tj}+\frac {r_j} q\quad\mbox{for some integer $\alpha_{tj}\geq 0$,}
\end{equation} where $\delta(v)$ is the set of edges incident to a vertex $v$. Note that the degree of each thief-vertex $t$ in $G_j$ is at least $\alpha_{tj}+1$ and the degree of each bead-vertex is at least $2$.

Changing the values of the $u_e$'s, while keeping them nonnegative and while satisfying the equalities~\eqref{flow}, leads to another continuous fair $q$-splitting with at most $(q-1)m$ cuts. The $u_e$'s form a flow. It is thus always possible to choose the continuous fair $q$-splitting in such a way that $G_j$ has no cycle for every $j$ (basic properties of flows). In the proofs below, $G_j$ will therefore always be assumed to be without cycle.
To get our result, we are going to select a subset $F$ of $E_j$ such that each bead-vertex is incident to exactly one edge in $F$. This subset of edges will encode an assignment of the beads in $B_j$ compatible with the already assigned beads (which does not increase the number of cuts), and leading to the desired allocation. 

For the proof of the case $r_j=1$, such a subset of edges is obtained as a special object of graph theory that we describe now.
Let $H=(V,E)$ be a bipartite graph and let $b:V\rightarrow\Z_+$. A {\em $b$-factor} is a subset $F\subseteq E$ such that each vertex $v\in V$ is incident to exactly $b(v)$ edges of $F$. There exists a $b$-factor if and only if each subset $X$ of $V$ spans at least $\sum_{v\in X}b(v)-\frac 1 2 \sum_{v\in V}b(v)$ edges, see~\cite[Corollary 21.4a]{schrijver2002combinatorial}.


\begin{lemma}\label{lem:r1}
When $r_j=1$, it is possible to move the cuts located on the beads of color $j$ and to get a discrete fair $q$-splitting for which we choose the thief getting the additional bead of color $j$. 
\end{lemma}

\begin{proof}
We have in this case $|B_j|=\sum_{t\in [q]}\alpha_{tj}+1$ (using~\eqref{flow}). For a thief $t$, define $b(t)=\alpha_{tj}$, except when $t$ is the thief chosen for the additional bead, in which case define $b(t)=\alpha_{tj}+1$. For each bead $k$, define $b(k)=1$. Consider a subset $X$ of vertices of $G_j$. Denote by $T$ the thief-vertices in $X$ and by $K$ the bead-vertices in $X$. The edges spanned by $X$ is $\delta(T)\setminus E[T:B_j\setminus K]$. We have $|\delta(T)|\geq\sum_{t\in T}(\alpha_{tj}+1)$ and $|E[T:B_j\setminus K]|\leq |T|+|B_j|-|K|-1$. To get this latter inequality, we use the fact that $G_j$ has no cycle. The number of edges spanned by $X$ is thus at least $|K|-|B_j|+1+\sum_{t\in T}\alpha_{tj}$. 

The quantity $\sum_{v\in X}b(v)-\frac 1 2 \sum_{v\in U_j}b(v)$ is at most $1+\sum_{t\in T}\alpha_{tj}+|K|-|B_j|$. According to the above mentioned result, there exists a $b$-factor in $G_j$.
\end{proof}

\begin{lemma}\label{lem:rq-1}
When $r_j=q-1$, it is possible to move the cuts located on the beads of color $j$ and to get a discrete fair $q$-splitting for which we choose the thief getting one bead of color $j$ less than the other thieves. 
\end{lemma}

\begin{proof}
Since $G_j$ is without cycle, its number of edges is at most $q-1+|B_j|$. The degree of each vertex in $B_j$ being at least $2$, it implies that $q-1+|B_j|\geq 2|B_j|$, and thus $|B_j|\leq q-1$. The fact that $r_j=q-1$ leads finally to $|B_j|=q-1$ (using~\eqref{flow}), which implies that $\alpha_{tj}=0$ for all $t\in[q]$. For any proper subset $T\subset [q]$ of distinct thieves, we have thus $\sum_{t\in T}\sum_{e\in\delta(t)}u_{e}=|T|-\frac {|T|}{q}$, which means that the size of the neighborhood of $T$ in $G_j$ is at least $\left\lceil|T|-\frac {|T|}{q}\right\rceil=|T|$. This latter equality holds because $|T|\leq q-1$. Hall's theorem ensures then that we can assign the $q-1$ beads in $B_j$ to any choice of $q-1$ thieves.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:neck}]
For the colors $j$ such that $r_j=0$, the original rounding procedure introduced by Alon, Moshkovitz, and Safra makes the job. For the colors $j$ such that $r_j\in\{1,q-1\}$, Lemmas~\ref{lem:r1} and~\ref{lem:rq-1} allow to conclude.
\end{proof}


Note that this approach may fail already when $q=4$ and $r_j=2$: if thieves $a$ and $b$ receive each half of a bead and thieves $c$ and $d$ receive each half of another bead, it is impossible to move the cuts so that both $a$ and $b$ are advantaged.

\subsection*{Acknowledgments} This work was done when the first author was visiting the Universit\'e Paris Est. He would like to acknowledge professor Fr\'ed\'eric Meunier for his generous support and hospitality. 

%\bibliographystyle{plain}
%\bibliography{ColoredPath}
\vspace{-0.5cm}
\SquashBibFurther
\begin{thebibliography}{99}

\bibitem{aharoni2016fair}
Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin
  Loebl, and Ran Ziv.
\newblock Fair representation by independent sets.
\newblock In {\em Mathematics of Jirka Matou\v sek}. Springer, 2017.

\bibitem{alon1987splitting}
Noga Alon.
\newblock Splitting necklaces.
\newblock {\em Advances in Mathematics}, 63(3):247--253, 1987.

\bibitem{alon2006algorithmic}
Noga Alon, Dana Moshkovitz, and Shmuel Safra.
\newblock Algorithmic construction of sets for $k$-restrictions.
\newblock {\em ACM Transactions on Algorithms (TALG)}, 2(2):153--177, 2006.

\bibitem{matouvsek2004combinatorial}
Ji{\v{r}}{\'\i} Matou{\v{s}}ek.
\newblock A combinatorial proof of {K}neser's conjecture.
\newblock {\em Combinatorica}, 24(1):163--170, 2004.

\bibitem{meunier2014simplotopal}
Fr{\'e}d{\'e}ric Meunier.
\newblock Simplotopal maps and necklace splitting.
\newblock {\em Discrete Mathematics}, 323:14--26, 2014.

\bibitem{palvolgyi2009combinatorial}
D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi.
\newblock Combinatorial necklace splitting.
\newblock {\em The Electronic Journal of Combinatorics}, 16(1):\#R79, 2009.

\bibitem{schrijver2002combinatorial}
Alexander Schrijver.
\newblock {\em Combinatorial optimization: polyhedra and efficiency}.
\newblock Springer, 2003.

\bibitem{ziegler2002generalized}
G{\"u}nter~M. Ziegler.
\newblock Generalized {K}neser coloring theorems with combinatorial proofs.
\newblock {\em Inventiones mathematicae}, 147(3):671--691, 2002.

\end{thebibliography}


\end{document}

