# The Chromatic Number of Kneser Hypergraphs via Consensus Division

Ishay Haviv School of Computer Science, The Academic College of Tel Aviv-
Yaffo, Tel Aviv 61083, Israel. Research supported in part by the Israel
Science Foundation (grant No. 1218/20).

###### Abstract

We show that the Consensus Division theorem implies lower bounds on the
chromatic number of Kneser hypergraphs, offering a novel proof for a result of
Alon, Frankl, and Lovász (Trans. Amer. Math. Soc., 1986) and for its
generalization by Kriz (Trans. Amer. Math. Soc., 1992). Our approach is
applied to study the computational complexity of the total search problem
$\textsc{Kneser}^{p}$, which given a succinct representation of a coloring of
a $p$-uniform Kneser hypergraph with fewer colors than its chromatic number,
asks to find a monochromatic hyperedge. We prove that for every prime $p$, the
$\textsc{Kneser}^{p}$ problem with an extended access to the input coloring is
efficiently reducible to a quite weak approximation of the Consensus Division
problem with $p$ shares. In particular, for $p=2$, the problem is efficiently
reducible to any non-trivial approximation of the Consensus Halving problem on
normalized monotone functions. We further show that for every prime $p$, the
$\textsc{Kneser}^{p}$ problem lies in the complexity class
$\mathsf{PPA}\textsc{-}p$. As an application, we establish limitations on the
complexity of the $\textsc{Kneser}^{p}$ problem, restricted to colorings with
a bounded number of colors.

##  1 Introduction

This paper is concerned with two classic problems: the graph-theoretic problem
of determining the chromatic number of Kneser hypergraphs and the consensus
division problem from the area of fair division, which lies at the
intersection of economics, mathematics, and computer science. We present a
novel direct connection between the two problems, offering a new proof for a
result of Alon, Frankl, and Lovász [3] on the chromatic number of Kneser
hypergraphs as well as for its generalization by Kriz [28]. We use this
connection to study the computational complexity of the total search problems
associated with Kneser hypergraphs and with approximate consensus division. In
what follows, we provide some background on the two problems and on their
computational aspects, and then describe our contribution.

#### Kneser hypergraphs.

For an integer $r\geq 2$ and a set family ${\cal F}$, the $r$-uniform Kneser
hypergraph $K^{r}({\cal F})$ is the hypergraph on the vertex set ${\cal F}$,
whose hyperedges are all the $r$-subsets of ${\cal F}$ whose members are
pairwise disjoint. For integers $n$ and $k$ with $n\geq r\cdot k$, let
$K^{r}(n,k)$ denote the hypergraph $K^{r}({\cal F})$, where ${\cal
F}=\binom{[n]}{k}$ is the family of all $k$-subsets of
$[n]=\\{1,2,\ldots,n\\}$. When $r=2$, the superscript $r$ may be omitted. The
chromatic number of a hypergraph $H$, denoted by $\chi(H)$, is the minimum
number of colors that allow a proper coloring of its vertices, that is, a
coloring with no monochromatic hyperedge.

The study of the chromatic number of Kneser graphs was initiated in 1955 by
Kneser [27], who observed that the graph $K(n,k)$ admits a proper coloring
with $n-2k+2$ colors and conjectured that fewer colors do not suffice, that
is, $\chi(K(n,k))=n-2k+2$. Lovász [29] confirmed Kneser’s conjecture in 1978,
and his result was extended in multiple ways over the years. One extension,
due to Schrijver [34], showed that the subgraph $S(n,k)$ of $K(n,k)$, induced
by the $k$-subsets of $[n]$ that are stable (i.e., include no two consecutive
elements modulo $n$) has the same chromatic number. Another extension, due to
Alon, Frankl, and Lovász [3], confirmed a conjecture of Erdös [13] by showing
that $\chi(K^{r}(n,k))=\lceil\frac{n-r(k-1)}{r-1}\rceil$ for all integers
$r\geq 2$. Their lower bound on $\chi(K^{r}(n,k))$ was further generalized by
Kriz [28], as stated below, using a quantity of set families, called the
$r$-colorability defect and denoted by ${\mathop{\mathrm{cd}}}_{r}$ (see
Definition 2.2; see also [12]).

######  Theorem 1.1 ([28]).

For every integer $r\geq 2$ and for every family ${\cal F}$ of non-empty sets,

$\chi(K^{r}({\cal F}))\geq\Big{\lceil}\frac{\mathop{\mathrm{cd}}_{r}({\cal
F})}{r-1}\Big{\rceil}.$

While Theorem 1.1 implies the tight lower bound of Alon et al. [3] on the
chromatic number of $K^{r}(n,k)$ (see Lemma 2.3), it does not cover the
aforementioned result of Schrijver [34]. In an attempt to simultaneously
generalize both the results, additional extensions were established by several
authors, e.g., Meunier [32], Alishahi and Hajiabolhassan [1], Aslam et al.
[5], and Frick [18].

It is interesting to mention that although the statements of the above results
are all purely combinatorial, their proofs rely on topological tools. Lovász’s
lower bound [29] on the chromatic number of $K(n,k)$ was based on the
Borsuk–Ulam theorem [7], a fundamental result in algebraic topology, and his
approach pioneered the area of topological combinatorics. The extension to
hypergraphs by Alon et al. [3] was based on a theorem of Bárány, Shlosman, and
Szücs [6] that generalizes the Borsuk–Ulam theorem. It was shown by Matoušek
[30] that the chromatic number of $K(n,k)$ can also be determined as an
application of Tucker’s lemma, a combinatorial analogue of the Borsuk–Ulam
theorem. His machinery was further developed by Ziegler [36] and later by
Meunier [32] to provide alternative proofs for the results of [3, 28, 34].

#### Consensus division.

Another area that extensively applies topological tools is fair division,
where the goal is to find fair allocations of resources among several parties.
In the consensus division scenario, given $m$ continuous valuation functions
$v_{1},\ldots,v_{m}$ defined on subsets of the unit interval $[0,1]$, we aim
to divide the interval into $r$ (not necessarily connected) pieces
$A_{1},\ldots,A_{r}$ using as few cuts as possible, such that each function
assigns the same value to the $r$ pieces, namely,
$v_{i}(A_{t})=v_{i}(A_{t^{\prime}})$ for all $i\in[m]$ and
$t,t^{\prime}\in[r]$. For the case $r=2$, referred to as consensus halving,
the Hobby–Rice theorem [25] asserts that there always exists such a division
with at most $m$ cuts. For a general $r\geq 2$, Alon [2] used the
generalization of [6] of the Borsuk–Ulam theorem to show that if the valuation
functions are probability measures on $[0,1]$, then there exists a consensus
division with at most $(r-1)\cdot m$ cuts. Note that this result played a
central role in his proof of the Splitting Necklaces theorem [2]. In fact, it
turns out that if the number of desired pieces is a prime $p$, then the
existence of a consensus division with at most $(p-1)\cdot m$ cuts is
guaranteed for any given continuous valuation functions, which unlike
probability measures, are not required to be additive nor non-negative. This
extension was provided for $p=2$ by Simmons and Su [35] and for any prime $p$
by Filos-Ratsikas, Hollender, Sotiraki, and Zampetakis [16] (see Theorem 2.4).

#### Computational aspects.

The complexity class $\mathsf{TFNP}$, introduced in [31], consists of the
total search problems in $\mathsf{NP}$, i.e., the search problems for which
every instance is guaranteed to have a solution, where the solutions can be
verified in polynomial time. In 1994, Papadimitriou [33] introduced several
sub-classes of $\mathsf{TFNP}$ that express the mathematical arguments which
yield the existence of the solutions for their problems. In particular, he
defined for every prime $p$, the complexity class $\mathsf{PPA}\textsc{-}p$,
associated with the principle that every bipartite graph that has a vertex
whose degree is not a multiple of $p$, has another such vertex. Consequently,
$\mathsf{PPA}\textsc{-}p$ is the class of problems in $\mathsf{TFNP}$ that are
efficiently reducible to the corresponding canonical problem: Given a Boolean
circuit that represents a bipartite graph and given a vertex whose degree is
not a multiple of $p$, find another such vertex. This family of classes was
further studied and developed by Hollender [26] and by Göös, Kamath, Sotiraki,
and Zampetakis [21], who independently introduced the classes
$\mathsf{PPA}\textsc{-}r$ for composites $r$. Note that the class
$\mathsf{PPA}\textsc{-}2$ is denoted by $\mathsf{PPA}$, and that its analogue
for directed graphs, called $\mathsf{PPAD}$, is known to be contained in
$\mathsf{PPA}\textsc{-}r$ for all integers $r\geq 2$ [26, 21].

For any integer $r\geq 2$, let Con-$r$-Division denote the computational
problem, which given an access to $m$ continuous valuation functions
$v_{1},\ldots,v_{m}$ over $[0,1]$, asks to find a consensus division into $r$
pieces $A_{1},\ldots,A_{r}$ with at most $(r-1)\cdot m$ cuts. In its
approximate version with precision parameter $\varepsilon$, the pieces should
satisfy $|v_{i}(A_{t})-v_{i}(A_{t^{\prime}})|\leq\varepsilon$ for all
$i\in[m]$ and $t,t^{\prime}\in[r]$. The problem may be considered for various
families of input functions, ranging from piecewise-constant functions and
probability measures to monotone functions and general functions. While
piecewise-constant functions can be explicitly represented by the endpoints
and values of the intervals on which they are nonzero, in the more general
settings the functions are given by some succinct representation, e.g.,
arithmetic circuits or efficient Turing machines that compute them. It follows
from [16] that for all primes $p$, every instance of the Con-$p$-Division
problem has a solution even for $\varepsilon=0$, hence the problem is total.

A considerable attention has been devoted in recent years to the
Con-$r$-Division problem with $r=2$, referred to as Con-Halving. Filos-
Ratsikas and Goldberg [14, 15] proved that the problem is
$\mathsf{PPA}$-complete, even for piecewise-constant functions and inverse-
polynomial precision parameter $\varepsilon$, and derived the
$\mathsf{PPA}$-completeness of the Splitting Necklaces with two thieves and
Discrete Sandwich problems. Their result was strengthened and extended in
several ways. Deligkas, Filos-Ratsikas, and Hollender [9] proved that the
problem remains $\mathsf{PPA}$-hard when the number of valuation functions is
a fixed constant: for two or more general functions, and for three or more
monotone functions. Filos-Ratsikas, Hollender, Sotiraki, and Zampetakis [17]
proved that the problem remains $\mathsf{PPA}$-hard when the valuation
functions are piecewise-uniform with only two blocks. More recently, Deligkas,
Fearnley, Hollender, and Melissourgos [8] proved that the problem is
$\mathsf{PPA}$-hard for any precision parameter $\varepsilon<1/5$, even when
the valuation functions are piecewise-uniform with three blocks. An additional
version of the Con-Halving problem, where the goal is not to partition an
interval but an unordered collection of items, was studied by Goldberg,
Hollender, Igarashi, Manurangsi, and Suksompong [20].

The complexity of the Con-$r$-Division problem for a general $r$ is much less
understood. It was proved by Filos-Ratsikas, Hollender, Sotiraki, and
Zampetakis [16] that for every prime $p$, Con-$p$-Division lies in the
complexity class $\mathsf{PPA}\textsc{-}p$, and the question of whether it is
$\mathsf{PPA}\textsc{-}p$-hard was left open. Yet, for $p=3$, it was shown in
[17] that Con-$3$-Division is $\mathsf{PPAD}$-hard for an inverse-exponential
precision parameter $\varepsilon$. On the algorithmic side, Alon and Graur [4]
proved that given an access to $m$ probability measures over $[0,1]$, it is
possible to find in polynomial time a partition of the unit interval into $r$
pieces with at most $(r-1)\cdot m$ cuts, such that every piece receives at
least $\frac{1}{m\cdot r}$ of each measure. They also considered the case
where a larger number of cuts is allowed, and showed that for a given
precision parameter $\varepsilon$, it is possible to efficiently find a
solution with $O(\varepsilon^{-2}\cdot m\log m)$ cuts. Goldberg and Li [19]
proved that the Con-$r$-Division problem on $m$ probability measures, where
the number of allowed cuts is $2(r-1)(p-1)\cdot\frac{\lceil p/2\rceil}{\lfloor
p/2\rfloor}\cdot m$ for a prime $p$, lies in the complexity class
$\mathsf{PPA}\textsc{-}p$. For example, the Con-Halving problem on $m$
probability measures with $8m$ allowed cuts lies in $\mathsf{PPA}\textsc{-}3$.

Before turning to our results, let us introduce, for any integer $r\geq 2$,
the computational search problem $\textsc{Kneser}^{r}$ associated with the
family of $r$-uniform Kneser hypergraphs $K^{r}(n,k)$. The input consists of
integers $n$ and $k$ with $n\geq r\cdot k$ along with a Boolean circuit that
represents a coloring of the vertices of the hypergraph $K^{r}(n,k)$ with
$\lfloor\frac{n-r(k-1)-1}{r-1}\rfloor$ colors, which is smaller by one than
its chromatic number [3]. The goal is to find a monochromatic hyperedge, that
is, $r$ pairwise disjoint vertices that are assigned the same color by the
input coloring. Omitting the superscript $r$ when $r=2$, the Kneser problem is
known to lie in $\mathsf{PPA}$, and it is an open question whether it is
$\mathsf{PPA}$-hard, as suggested by Deng, Feng, and Kulkarni [10]. More
generally, it was asked in [16] whether for every prime $p$, the
$\textsc{Kneser}^{p}$ problem lies in $\mathsf{PPA}\textsc{-}p$ and if it is
$\mathsf{PPA}\textsc{-}p$-hard. While no hardness result is known for these
problems, it was shown in [22] that the Schrijver problem, which asks to find
a monochromatic edge in a graph $S(n,k)$ given a coloring of its vertices with
$n-2k+1$ colors, is $\mathsf{PPA}$-complete. It was recently shown in [24]
that the problem of finding a monochromatic edge in a graph $S(n,k)$, given a
coloring of its vertices with only $\lfloor n/2\rfloor-2k+1$ colors, is
efficiently reducible to the Kneser problem.

###  1.1 Our Contribution

This paper presents a novel direct connection between the chromatic number of
Kneser hypergraphs and the consensus division problem. As our first
contribution, we offer a new proof of Kriz’s lower bound on the chromatic
number of Kneser hypergraphs [28], stated earlier as Theorem 1.1. The proof
relies on the Consensus Division theorem of Filos-Ratsikas et al. [16]. Our
technique borrows and extends ideas that were applied in [20] and in [23].

We then adopt a computational perspective and explore our approach to Theorem
1.1 as a reduction from the $\textsc{Kneser}^{p}$ problem to the
Con-$p$-Division problem for any prime $p$. Our main contribution is an
efficient reduction from the $\textsc{Kneser}^{p}$ problem with an extended
access to the input coloring to a quite weak approximation of the
Con-$p$-Division problem. Before the precise statements, let us introduce the
following variants of the studied computational problems. Their formal
definitions are given in Sections 4.1 and 4.2.

  * •

The $\textsc{Kneser}^{p}$ problem with subset queries: As in the standard
$\textsc{Kneser}^{p}$ problem, the input is a coloring of the vertices of a
hypergraph $K^{p}(n,k)$ with fewer colors than its chromatic number, and the
goal is to find a monochromatic hyperedge. Here, however, the access to the
coloring allows, in addition to queries for the colors of the vertices,
another type of queries called subset queries. Such a query involves a subset
$D$ of $[n]$ and a color $i$, and the answer on the pair $(D,i)$ determines
whether $D$ contains a vertex colored $i$. The notion of subset queries was
proposed in [23].

  * •

The $\textsc{Con-$p$-Division}[<\varepsilon]$ problem: As in the standard
Con-$p$-Division problem, the input consists of $m$ continuous valuation
functions $v_{1},\ldots,v_{m}$ over $[0,1]$, and a solution is a partition of
the unit interval into $p$ pieces $A_{1},\ldots,A_{p}$ with at most
$(p-1)\cdot m$ cuts. Here, however, the solution is required to satisfy

$\displaystyle|v_{i}(A_{t})-v_{i}(A_{t^{\prime}})|<\varepsilon$ (1)

for all $i\in[m]$ and $t,t^{\prime}\in[p]$. Namely, the difference from the
standard Con-$p$-Division problem with precision parameter $\varepsilon$ is
that the inequality in (1) is strict. In particular, for $\varepsilon=1$,
assuming that the valuation functions are normalized (i.e., return values in
$[0,1]$), the solution is just required to be non-trivial. This means that the
solution is just not allowed to include two pieces $A_{t}$ and
$A_{t^{\prime}}$ such that $v_{i}(A_{t})=1$ and $v_{i}(A_{t^{\prime}})=0$ for
some $i\in[m]$, but the value of $|v_{i}(A_{t})-v_{i}(A_{t^{\prime}})|$ may
approach $1$ as $m$ grows. When $p=2$, the problem is denoted by $\textsc{Con-
Halving}[<\varepsilon]$.

We prove the following theorem, which concerns the case $p=2$.

######  Theorem 1.2.

There exists a polynomial-time reduction from the Kneser problem with subset
queries to the $\textsc{Con-Halving}[<1]$ problem on normalized monotone
functions.

As alluded to before, the complexity of the Kneser problem (with or without
subset queries) is not well understood. Theorem 1.2 implies that any hardness
result for the Kneser problem with subset queries would imply a very strong
hardness result for the Con-Halving problem on normalized monotone functions,
ruling out the possibility to obtain an efficient algorithm for any non-
trivial approximation of the problem. On the other hand, an efficient
algorithm for Con-Halving that guarantees some non-trivial approximation on
normalized monotone functions would imply an efficient algorithm for the
Kneser problem with subset queries. We find these consequences of the
reduction quite surprising and unusual, especially because of the discrete
nature of the Kneser problem. For comparison, the efficient reduction from the
(discrete) Splitting Necklaces problem with two thieves to the Con-Halving
problem with precision parameter $\varepsilon$, which is given in [14] and
builds on an argument of [2], requires $\varepsilon$ to be inverse-polynomial
in the number of valuation functions (note that those functions are additive,
though). Let us stress that Theorem 1.2 addresses the $\textsc{Con-
Halving}[<1]$ problem when restricted to normalized monotone valuation
functions but not to probability measures. Recall that for this stronger
restriction, an algorithm of [4] does provide a non-trivial solution in
polynomial time. We finally note that the proof of Theorem 1.2 essentially
supplies a reduction to the version of Con-Halving, studied in [20], of
finding a consensus halving of an unordered collection of items rather than of
the unit interval. This makes the result stronger, as this version is
efficiently reducible to the standard one.

Our next result relates the $\textsc{Kneser}^{p}$ problem with subset queries
to the Con-$p$-Division problem for every prime $p\geq 3$. Here, the precision
parameter of the latter is $\tfrac{1}{2}$.

######  Theorem 1.3.

For every prime $p\geq 3$, there exists a polynomial-time reduction from the
$\textsc{Kneser}^{p}$ problem with subset queries to the
$\textsc{Con-$p$-Division}[<\tfrac{1}{2}]$ problem on normalized monotone
functions.

It is noteworthy that Theorems 1.2 and 1.3 are proved in a more general form.
Namely, we reduce from a generalized variant of the $\textsc{Kneser}^{p}$
problem, where the input is a coloring of a hypergraph $K^{p}({\cal F})$ for
some set family ${\cal F}$ taken from a prescribed sequence of set families,
which is assumed to be efficiently computable (see Definitions 4.2 and 4.3).
The number of colors used by the input coloring may be any number smaller than
Kriz’s lower bound on the chromatic number of $K^{p}({\cal F})$, as given by
Theorem 1.1. For the precise statements, see Theorems 4.8 and 4.10.

We proceed with additional results on the computational complexity of the
$\textsc{Kneser}^{p}$ problem (in its standard version, without subset
queries). The following theorem settles a question of [16].

######  Theorem 1.4.

For every prime $p$, the $\textsc{Kneser}^{p}$ problem lies in
$\mathsf{PPA}\textsc{-}p$.

In fact, we provide two results that strengthen Theorem 1.4 in two
incomparable forms. Firstly, as before, we present a generalized result
handling a variant of the $\textsc{Kneser}^{p}$ problem of finding a
monochromatic hyperedge in a hypergraph $K^{p}({\cal F})$, given a coloring
that uses fewer colors than Kriz’s lower bound on its chromatic number. Again,
${\cal F}$ is taken from a prescribed sequence of set families satisfying
certain computational assumptions (see Definition 5.3 and Corollary 5.6).
Secondly, we show that the membership in $\mathsf{PPA}\textsc{-}p$ holds for
the $\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{p}$ problem. This problem
asks to find a monochromatic hyperedge in the sub-hypergraph of $K^{p}(n,k)$
induced by the $k$-subsets of $[n]$ that are almost stable (i.e., include no
two consecutive elements, but can include both $1$ and $n$). The input
coloring may use here any number of colors smaller than the chromatic number
of this hypergraph, which, as proved in [32], is equal to that of
$K^{p}(n,k)$.

######  Theorem 1.5.

For every prime $p$, the $\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{p}$
problem lies in $\mathsf{PPA}\textsc{-}p$.

The proofs of Theorems 1.4 and 1.5 crucially rely on the mathematical
arguments due to Ziegler [36] and Meunier [32], which imply the totality of
the studied problems. We verify that their arguments can be transformed into
efficient reductions to a computational problem associated with a
${\mathbb{Z}}_{p}$-variant of Tucker’s lemma, which was shown to lie in the
complexity class $\mathsf{PPA}\textsc{-}p$ by Filos-Ratsikas et al. [16].

Finally, we apply Theorems 1.4 and 1.5 to derive limitations on the complexity
of variants of the $\textsc{Kneser}^{r}$ problem, restricted to colorings with
a bounded number of colors (see Theorem 5.9 and Corollary 5.11). In
particular, we show that the problem of finding a monochromatic edge in a
graph $S(n,k)$ given a coloring of its vertices with $\lfloor n/2\rfloor-2k+1$
colors, lies in the complexity class $\mathsf{PPA}\textsc{-}3$ (see Corollary
5.12). As mentioned earlier, it was shown in [24] that the latter is
efficiently reducible to the Kneser problem. It thus follows that, unless
$\mathsf{PPA}\subseteq\mathsf{PPA}\textsc{-}3$, this reduction cannot yield a
$\mathsf{PPA}$-hardness result for the Kneser problem. We note that it is
common to believe that the classes $\mathsf{PPA}\textsc{-}p$ for primes $p$ do
not contain each other, and that an unconditional separation between their
black-box versions was provided in [26, 21].

###  1.2 Outline

The rest of the paper is organized as follows. In Section 2, we gather some
definitions that will be used throughout the paper. In Section 3, we present
our novel proof of Theorem 1.1. In Section 4, we study this proof from a
computational perspective and prove Theorems 1.2 and 1.3 in generalized forms.
Finally, in Section 5, we prove a generalized form of Theorem 1.4. We further
prove there Theorem 1.5 and obtain some limitations on the complexity of the
$\textsc{Kneser}^{r}$ problem.

##  2 Preliminaries

For integers $n$ and $k$, let $\binom{[n]}{k}$ denote the family of
$k$-subsets of $[n]=\\{1,2,\ldots,n\\}$. A subset of $[n]$ is called stable if
it does not include two consecutive elements modulo $n$, equivalently, it
forms an independent set in the cycle on the vertex set $[n]$ with the natural
order along the cycle. Let $\binom{[n]}{k}_{\mathrm{stab}}$ denote the family
of stable $k$-subsets of $[n]$. A subset of $[n]$ is called almost stable if
it does not include two consecutive elements, equivalently, it forms an
independent set in the path on the vertex set $[n]$ with the natural order
along the path. Let $\binom{[n]}{k}_{\widetilde{\mathrm{stab}}}$ denote the
family of almost stable $k$-subsets of $[n]$. Note that
$\binom{[n]}{k}_{\mathrm{stab}}\subseteq\binom{[n]}{k}_{\widetilde{\mathrm{stab}}}\subseteq\binom{[n]}{k}$.

The family of Kneser hypergraphs is defined as follows.

######  Definition 2.1 (Kneser Hypergraphs).

For an integer $r\geq 2$ and a set family ${\cal F}$, the $r$-uniform Kneser
hypergraph $K^{r}({\cal F})$ is the hypergraph on the vertex set ${\cal F}$,
whose hyperedges are all the $r$-subsets of ${\cal F}$ whose members are
pairwise disjoint. For integers $n$ and $k$ with $n\geq r\cdot k$, let
$K^{r}(n,k)$, $K^{r}(n,k)_{\widetilde{\mathrm{stab}}}$, and
$K^{r}(n,k)_{\mathrm{stab}}$, respectively, denote the hypergraphs
$K^{r}(\binom{[n]}{k})$, $K^{r}(\binom{[n]}{k}_{\widetilde{\mathrm{stab}}})$,
and $K^{r}(\binom{[n]}{k}_{\mathrm{stab}})$. When $r=2$, the superscript $r$
may be omitted.

For an integer $t\geq 1$, a hypergraph $H=(V,E)$ is said to be $t$-colorable
if it admits a proper $t$-coloring, that is, a coloring of the vertices of $V$
with $t$ colors such that no hyperedge of $E$ is monochromatic. The chromatic
number of $H$, denoted by $\chi(H)$, is the smallest integer $t$ for which $H$
is $t$-colorable. It is known (see [3, 32, 18]) that for all integers $r\geq
2$, $k$, and $n\geq r\cdot k$, it holds that

$\displaystyle\chi(K^{r}(n,k))=\chi(K^{r}(n,k)_{\widetilde{\mathrm{stab}}})=\chi(K^{r}(n,k)_{\mathrm{stab}})=\Big{\lceil}\frac{n-r(k-1)}{r-1}\Big{\rceil}.$
(2)

Theorem 1.1, proved by Kriz [28], relates the chromatic number of Kneser
hypergraphs to the notion of colorability defect, defined as follows.

######  Definition 2.2 (Colorability Defect).

For an integer $r\geq 2$ and a family ${\cal F}$ of non-empty subsets of a set
$X$, the $r$-colorability defect of ${\cal F}$, denoted by
$\mathop{\mathrm{cd}}_{r}({\cal F})$, is the smallest size of a set
$Y\subseteq X$, such that the sub-hypergraph of $(X,{\cal F})$ induced by
$X\setminus Y$ is $r$-colorable, that is,

${\mathop{\mathrm{cd}}}_{r}({\cal F})=\min\big{\\{}|Y|~{}\mid~{}(X\setminus
Y,\\{e\in{\cal F}\mid e\cap
Y=\emptyset\\})\mbox{~{}is~{}$r$-colorable}\big{\\}}.$

The following lemma, given in [36, Lemma 3.2], determines the $r$-colorability
defect of $\binom{[n]}{k}$.

######  Lemma 2.3 ([36]).

For integers $n,k,r$ with $n\geq r\cdot k$, it holds that
$\mathop{\mathrm{cd}}_{r}(\binom{[n]}{k})=n-r(k-1)$.

We next state the Consensus Division theorem due to Filos-Ratsikas et al. [16,
Theorem 6.5]. In what follows, let ${\cal B}([0,1])$ denote the set of
Lebesgue-measurable subsets of the interval $[0,1]$, and let $\mu:{\cal
B}([0,1])\rightarrow[0,1]$ denote the Lebesgue measure on $[0,1]$. In
addition, let $\triangle$ stand for the symmetric difference of sets, defined
by $E_{1}\triangle E_{2}=(E_{1}\setminus E_{2})\cup(E_{2}\setminus E_{1})$.

######  Theorem 2.4 (Consensus Division Theorem [16]).

Let $p$ be a prime, and let $m\geq 1$ be an integer. Let
$v_{1},\ldots,v_{m}:{\cal B}([0,1])\rightarrow\mathbb{R}$ be functions such
that for each $i\in[m]$, $v_{i}$ satisfies the following continuity condition:
for any $\varepsilon>0$ there exists $\delta>0$ such that for all
$E_{1},E_{2}\in{\cal B}([0,1])$ with $\mu(E_{1}\triangle E_{2})\leq\delta$, it
holds that $|v_{i}(E_{1})-v_{i}(E_{2})|\leq\varepsilon$. Then, there exists a
consensus-$p$-division, that is, it is possible to partition the unit interval
into $p$ (not necessarily connected) pieces $A_{1},\ldots,A_{p}$ using at most
$(p-1)\cdot m$ cuts, such that $v_{i}(A_{t})=v_{i}(A_{t^{\prime}})$ for all
$i\in[m]$ and $t,t^{\prime}\in[p]$.

As for the continuity property, we will sometimes consider the stronger notion
of Lipschitz-continuity. For $L\geq 0$, a function $v:{\cal
B}([0,1])\rightarrow\mathbb{R}$ is said to be $L$-Lipschitz-continuous, if for
all $E_{1},E_{2}\in{\cal B}([0,1])$, it holds that $|v(E_{1})-v(E_{2})|\leq
L\cdot\mu(E_{1}\triangle E_{2})$.

##  3 The Chromatic Number of Kneser Hypergraphs

In this section, we present our new proof of Kriz’s lower bound on the
chromatic number of Kneser hypergraphs [28], stated as Theorem 1.1. The proof
applies the Consensus Division theorem, stated as Theorem 2.4. Note that we
focus here on the mathematical proof rather than on its computational aspects,
which will be explored in the next section. As is usual for results of this
type, we first consider the case where the uniformity $r$ of the hypergraphs
is a prime number.

######  Theorem 3.1.

For every prime $p$ and for every family ${\cal F}$ of non-empty sets,

$\chi(K^{p}({\cal F}))\geq\Big{\lceil}\frac{\mathop{\mathrm{cd}}_{p}({\cal
F})}{p-1}\Big{\rceil}.$

  * Proof:

Let $p$ be a prime, and let ${\cal F}$ be a family of non-empty sets. Assume
without loss of generality that all members of ${\cal F}$ are subsets of $[n]$
for some integer $n$. Let $m$ be an integer satisfying
$m<\frac{\mathop{\mathrm{cd}}_{p}({\cal F})}{p-1}$, and suppose for the sake
of contradiction that there exists a proper coloring $c:{\cal
F}\rightarrow[m]$ of the $p$-uniform Kneser hypergraph $K^{p}({\cal F})$.

For each $i\in[m]$, let $\widetilde{u}_{i}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
denote the indicator function that determines for every subset of $[n]$
whether it contains a set of ${\cal F}$ whose color according to $c$ is $i$,
that is, for every $D\subseteq[n]$, define $\widetilde{u}_{i}(D)=1$ if there
exists a set $B\in{\cal F}$ satisfying $B\subseteq D$ and $c(B)=i$, and define
$\widetilde{u}_{i}(D)=0$ otherwise. Here and throughout, we identify the
subsets of $[n]$ with their characteristic vectors in $\\{0,1\\}^{n}$. Note
that the function $\widetilde{u}_{i}$ is monotone with respect to inclusion.

For each $i\in[m]$, consider the extension $u_{i}:[0,1]^{n}\rightarrow[0,1]$
of $\widetilde{u}_{i}$ that maps any vector $x\in[0,1]^{n}$ to the largest
value $a\in[0,1]$ such that the set $\\{j\in[n]\mid x_{j}\geq a\\}$ contains a
set of ${\cal F}$ colored $i$ by $c$ if such a value exists, and to $0$
otherwise. Equivalently, for any $x\in[0,1]^{n}$, let $\pi$ be a permutation
of $[n]$ with $x_{\pi(1)}\leq x_{\pi(2)}\leq\cdots\leq x_{\pi(n)}$, and define
$u_{i}(x)=x_{\pi(j)}$ for the largest integer $j$ satisfying
$\widetilde{u}_{i}(\\{\pi(j),\pi(j+1),\ldots,\pi(n)\\})=1$ if such a $j$
exists, and $u_{i}(x)=0$ otherwise. Observe that, under the convention
$x_{\pi(0)}=0$, the value of $u_{i}(x)$ can be written as

$u_{i}(x)=\sum_{j=1}^{n}{(x_{\pi(j)}-x_{\pi(j-1)})\cdot\widetilde{u}_{i}(\\{\pi(j),\pi(j+1),\ldots,\pi(n)\\})}.$

Notice that the function $u_{i}$ is an extension of the function
$\widetilde{u}_{i}$. Notice further that $u_{i}$ is monotone, in the sense
that the value of $u_{i}(x)$ does not decrease when the value of some entry of
$x$ increases. Finally, notice that changing some entry of $x$ by
$\varepsilon$ changes $u_{i}(x)$ by at most $\varepsilon$, hence the function
$u_{i}$ is continuous.

Now, for each $j\in[n]$, consider the open sub-interval
$I_{j}=(\frac{j-1}{n},\frac{j}{n})$, and associate it with the element $j$.
For each $i\in[m]$, let $v_{i}:{\cal B}([0,1])\rightarrow[0,1]$ be the
function defined as follows. For every $E\in{\cal B}([0,1])$, let
$x^{E}\in[0,1]^{n}$ denote the vector that consists of the normalized Lebesgue
measures of $E$ on the sub-intervals $I_{1},\ldots,I_{n}$, that is,
$x^{E}_{j}=n\cdot\mu(E\cap I_{j})$ for all $j\in[n]$, and define
$v_{i}(E)=u_{i}(x^{E})$. Note that the function $v_{i}$ is the composition of
the function $u_{i}$ with the function that maps any set $E\in{\cal B}([0,1])$
to the vector $x^{E}$. Since the function $u_{i}$ is monotone and continuous,
it follows that so is $v_{i}$

Applying Theorem 2.4, we obtain that there exists a consensus-$p$-division of
$v_{1},\ldots,v_{m}$, that is, a partition of the unit interval into $p$
pieces $A_{1},\ldots,A_{p}$ using at most $(p-1)\cdot m$ cuts, such that
$v_{i}(A_{t})=v_{i}(A_{t^{\prime}})$ for all $i\in[m]$ and
$t,t^{\prime}\in[p]$. Let $Y$ denote the set of indices $j\in[n]$ for which
the open sub-interval $I_{j}$ includes a cut, and notice that
$|Y|\leq(p-1)\cdot m<\mathop{\mathrm{cd}}_{p}({\cal F})$. Thus, every sub-
interval $I_{j}$ with $j\in[n]\setminus Y$ is fully contained in one of the
pieces $A_{1},\ldots,A_{p}$. Consider the coloring that assigns to every
$j\in[n]\setminus Y$ the index $t\in[p]$ of the piece $A_{t}$ that contains
$I_{j}$. By $|Y|<\mathop{\mathrm{cd}}_{p}({\cal F})$, the hypergraph
$([n]\setminus Y,\\{e\in{\cal F}\mid e\cap Y=\emptyset\\})$ is not
$p$-colorable. This implies that for some $t\in[p]$, there exists a set
$B\in{\cal F}$ all of whose elements share the color $t$, and thus, for all
$j\in B$, it holds that $I_{j}\subseteq A_{t}$. Denoting by $\ell=c(B)$ the
color assigned to $B$ by the given coloring $c$, it follows from the
definition of $v_{\ell}$ that $v_{\ell}(\cup_{j\in B}{I_{j}})=1$. By
monotonicity, it further follows that $v_{\ell}(A_{t})=1$, which yields, by
Theorem 2.4, that $v_{\ell}(A_{t^{\prime}})=1$ for all $t^{\prime}\in[p]$.

Finally, for every $t^{\prime}\in[p]$, the fact that
$v_{\ell}(A_{t^{\prime}})=1$ implies that there exists a set
$B_{t^{\prime}}\in{\cal F}$ with $c(B_{t^{\prime}})=\ell$ such that
$\mu(A_{t^{\prime}}\cap I_{j})=\tfrac{1}{n}$ for all $j\in B_{t^{\prime}}$.
Since the pieces $A_{1},\ldots,A_{p}$ are pairwise disjoint, so are the sets
$B_{1},\ldots,B_{p}$. It thus follows that these sets form a monochromatic
hyperedge in $K^{p}({\cal F})$, in contradiction to the assumption that the
coloring $c$ is proper. This completes the proof.

It is well known that Theorem 3.1 implies Theorem 1.1 (see, e.g., [36]). We
provide the quick proof for completeness.

  * Proof of Theorem 1.1:

Theorem 3.1 shows that Theorem 1.1 holds whenever $r$ is prime. It therefore
suffices to prove that for every pair of integers $r_{1},r_{2}\geq 2$, if the
theorem holds for $r\in\\{r_{1},r_{2}\\}$ then it holds for $r=r_{1}r_{2}$. So
suppose that it holds for $r_{1}$ and $r_{2}$. Let ${\cal F}$ be a family of
non-empty subsets of $[n]$ for an integer $n$, and let $c:{\cal
F}\rightarrow[m]$ be a proper coloring of the hypergraph $K^{r_{1}r_{2}}({\cal
F})$ for an integer $m$. Our goal is to prove that
$m\geq\frac{\mathop{\mathrm{cd}}_{r_{1}r_{2}}({\cal F})}{r_{1}r_{2}-1}$.

Consider the family

${\cal
G}=\Big{\\{}G\subseteq[n]~{}\Big{|}~{}{\mathop{\mathrm{cd}}}_{r_{1}}({\cal
F}|_{G})>m(r_{1}-1)\Big{\\}},$

where ${\cal F}|_{G}=\\{F\in{\cal F}\mid F\subseteq G\\}$. Define a coloring
$c^{\prime}:{\cal G}\rightarrow[m]$ as follows. For every $G\in{\cal G}$, let
$c^{\prime}(G)$ be a color of some monochromatic hyperedge in $K^{r_{1}}({\cal
F}|_{G})$ with respect to the coloring $c$. The existence of such a hyperedge
for every $G\in{\cal G}$ follows from our assumption that the theorem holds
for $r_{1}$, which yields that $\chi(K^{r_{1}}({\cal
F}|_{G}))\geq\frac{\mathop{\mathrm{cd}}_{r_{1}}({\cal F}|_{G})}{r_{1}-1}>m$,
where the second inequality is due to the definition of ${\cal G}$. We claim
that $c^{\prime}$ is a proper coloring of $K^{r_{2}}({\cal G})$, and thus
$\chi(K^{r_{2}}({\cal G}))\leq m$. Indeed, otherwise there would exist $r_{2}$
pairwise disjoint sets $G_{1},\ldots,G_{r_{2}}\in{\cal G}$ that are assigned
the same color by $c^{\prime}$. Since each set $G_{i}$ with $i\in[r_{2}]$
contains $r_{1}$ pairwise disjoint sets of ${\cal F}|_{G_{i}}$ that are
assigned by $c$ the color $c^{\prime}(G_{i})$, this gives us $r_{1}r_{2}$
pairwise disjoint sets of ${\cal F}$ with the same color by $c$, contradicting
the assumption that $c$ is a proper coloring of $K^{r_{1}r_{2}}({\cal F})$.

Finally, by the assumption that the theorem holds for $r_{2}$, we have
$\chi(K^{r_{2}}({\cal G}))\geq\frac{\mathop{\mathrm{cd}}_{r_{2}}({\cal
G})}{r_{2}-1}$, which implies that $\mathop{\mathrm{cd}}_{r_{2}}({\cal G})\leq
m(r_{2}-1)$. This means that it is possible to remove at most $m(r_{2}-1)$ of
the elements of $[n]$ and to partition the remaining elements into $r_{2}$
sets $F_{1},\ldots,F_{r_{2}}$, such that no set of ${\cal G}$ is contained in
any of them. In particular, for each $i\in[r_{2}]$, it holds that
$F_{i}\notin{\cal G}$, which implies that $\mathop{\mathrm{cd}}_{r_{1}}({\cal
F}|_{F_{i}})\leq m(r_{1}-1)$. This means that it is possible to remove at most
$m(r_{1}-1)$ elements from each $F_{i}$ and to partition the remaining
elements into $r_{1}$ sets, such that no set of ${\cal F}|_{F_{i}}$ is
contained in any of them. It thus follows that one can remove at most
$m(r_{2}-1)+r_{2}\cdot m(r_{1}-1)=m(r_{1}r_{2}-1)$ elements from $[n]$ and
partition the remaining elements into $r_{1}r_{2}$ sets, such that no set of
${\cal F}$ is contained in any of them. This implies that
$\mathop{\mathrm{cd}}_{r_{1}r_{2}}({\cal F})\leq m(r_{1}r_{2}-1)$, providing
the desired lower bound on $m$.

We conclude this section by verifying that
$\chi(K^{r}(n,k))=\lceil\frac{n-r(k-1)}{r-1}\rceil$ for all $r\geq 2$. The
lower bound on $\chi(K^{r}(n,k))$, originally proved in [3], follows by
combining Theorem 1.1 with Lemma 2.3. For the upper bound, which is given in
[13], put $t=\lceil\frac{n-r(k-1)}{r-1}\rceil$, let $X_{1},\ldots,X_{t-1}$ be
$t-1$ pairwise disjoint $(r-1)$-subsets of $[n]$, and observe that the number
of elements of $[n[$ that do not belong to any of these sets is
$n-(t-1)(r-1)\leq rk-1$. Consider the coloring that assigns to every
$k$-subset $B$ of $[n]$ a color $i\in[t-1]$ such that $B\cap
X_{i}\neq\emptyset$ if such an $i$ exists, and the color $t$ otherwise. It can
be easily checked that this coloring of $K^{r}(n,k)$ is proper.

##  4 Reduction from $\textsc{Kneser}^{p}$ to Approximate Con-$p$-Division

In this section, we use the proof technique presented in Section 3 to obtain
efficient reductions from the computational problems associated with Kneser
hypergraphs to those associated with approximate consensus division. We start
by formally introducing the involved computational problems and then present
the reductions.

###  4.1 The $\textsc{Kneser}^{r}$ Problem

In order to make our results as strong as possible, we introduce a problem of
finding monochromatic hyperedges in general Kneser hypergraphs, defined as
follows.

######  Definition 4.1 (The $\textsc{Kneser}^{r}({\cal F},m)$ Problem).

For a set ${\cal A}$, let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$
be a sequence of set families, where for each $\alpha\in{\cal A}$, ${\cal
F}_{\alpha}$ is a family of non-empty subsets of $[n_{\alpha}]$ for some
integer $n_{\alpha}$, and let $m:{\cal A}\rightarrow\mathbb{N}$ be a function.
In the $\textsc{Kneser}^{r}({\cal F},m)$ problem, the input consists of • an
element $\alpha\in{\cal A}$ and • a Boolean circuit
$C:\\{0,1\\}^{n_{\alpha}}\rightarrow[m(\alpha)]$ that represents a coloring
$c:{\cal F}_{\alpha}\rightarrow[m(\alpha)]$ of the sets of ${\cal F}_{\alpha}$
with $m(\alpha)$ colors, in the sense that for every $B\in{\cal F}_{\alpha}$,
it holds that $C(B)=c(B)$. The goal is to find a monochromatic hyperedge in
$K^{r}({\cal F}_{\alpha})$, that is, $r$ pairwise disjoint sets
$B_{1},B_{2},\ldots,B_{r}\in{\cal F}_{\alpha}$ such that
$C(B_{1})=C(B_{2})=\cdots=C(B_{r})$.

Note that for every sequence ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal
A}}$ and for every function $m:{\cal A}\rightarrow\mathbb{N}$ for which it
holds that $m(\alpha)<\chi(K^{r}({\cal F}_{\alpha}))$ for all $\alpha\in{\cal
A}$, the $\textsc{Kneser}^{r}({\cal F},m)$ problem is total. In particular, by
Theorem 1.1, the $\textsc{Kneser}^{r}({\cal
F},\lfloor\frac{{\mathop{\mathrm{cd}}}_{r}({\cal F}_{\alpha})-1}{r-1}\rfloor)$
problem is total.

We next define a variant of the $\textsc{Kneser}^{r}({\cal F},m)$ problem with
an extended access to the input coloring. This variant is referred to as the
$\textsc{Kneser}^{r}({\cal F},m)$ problem with subset queries.

######  Definition 4.2 (The $\textsc{Kneser}^{r}({\cal F},m)$ Problem with
Subset Queries).

For a set ${\cal A}$, let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$
be a sequence of set families, where for each $\alpha\in{\cal A}$, ${\cal
F}_{\alpha}$ is a family of non-empty subsets of $[n_{\alpha}]$ for some
integer $n_{\alpha}$, and let $m:{\cal A}\rightarrow\mathbb{N}$ be a function.
In the $\textsc{Kneser}^{r}({\cal F},m)$ problem with subset queries, the
input consists of • an element $\alpha\in{\cal A}$, • a Boolean circuit
$C:\\{0,1\\}^{n_{\alpha}}\rightarrow[m(\alpha)]$ that represents a coloring
$c:{\cal F}_{\alpha}\rightarrow[m(\alpha)]$ of the sets of ${\cal F}_{\alpha}$
with $m(\alpha)$ colors, in the sense that for every $B\in{\cal F}_{\alpha}$,
it holds that $C(B)=c(B)$, and • a Boolean circuit
$S:\\{0,1\\}^{n_{\alpha}}\times[m(\alpha)]\rightarrow\\{0,1\\}$ that is
supposed to allow subset queries to the coloring $c$, namely, for every set
$D\subseteq[n_{\alpha}]$ and a color $i\in[m(\alpha)]$, it is supposed to
satisfy $S(D,i)=1$ if there exists a set $B\in{\cal F}_{\alpha}$ such that
$B\subseteq D$ and $c(B)=i$, and $S(D,i)=0$ otherwise. The goal is to find
either a monochromatic hyperedge in $K^{r}({\cal F}_{\alpha})$ or a violation
of the circuit $S$, namely, • (false negative) two sets
$B,D\subseteq[n_{\alpha}]$ and a color $i\in[m(\alpha)]$ such that $B\in{\cal
F}_{\alpha}$, $B\subseteq D$, $C(B)=i$, and yet $S(D,i)=0$, or • (false
positive) a set $D\subseteq[n_{\alpha}]$ and a color $i\in[m(\alpha)]$ such
that $S(D,i)=1$ whereas for every set $D^{\prime}$ obtained from $D$ by
removing a single element it holds that $S(D^{\prime},i)=0$, and in addition,
either $D\notin{\cal F}_{\alpha}$ or $D\in{\cal F}_{\alpha}$ and $C(D)\neq i$.

Note that by allowing the solutions of the $\textsc{Kneser}^{r}({\cal F},m)$
problem with subset queries to form violations of the circuit $S$, we obtain a
non-promise problem.

We will be particularly interested in the following special cases of
Definitions 4.1 and 4.2. For any integer $r\geq 2$, let ${\cal A}^{(r)}$
denote the set of all pairs of integers $(n,k)$ with $n\geq r\cdot k$, and let
${\cal F}^{(r)}$, ${\cal F}^{(r,\mathrm{\mathrm{stab}})}$, and ${\cal
F}^{(r,\widetilde{\mathrm{stab}})}$ denote, respectively, the sequences of set
families defined by

${\cal F}^{(r)}_{(n,k)}=\binom{[n]}{k},~{}~{}~{}~{}~{}{\cal
F}^{(r,\mathrm{stab})}_{(n,k)}=\binom{[n]}{k}_{\mathrm{stab}},~{}~{}~{}~{}~{}{\cal
F}^{(r,\widetilde{\mathrm{stab}})}_{(n,k)}=\binom{[n]}{k}_{\widetilde{\mathrm{stab}}}$

for all $(n,k)\in{\cal A}^{(r)}$. Consider the function $m^{(r)}:{\cal
A}^{(r)}\rightarrow\mathbb{N}$ defined by
$m^{(r)}(n,k)=\lfloor\frac{n-r(k-1)-1}{r-1}\rfloor$, which by (2), satisfies
$m^{(r)}(n,k)=\chi(K^{r}(n,k))-1$. We define the three problems
$\textsc{Kneser}^{r}$, $\textsc{Kneser}^{r}_{\mathrm{stab}}$, and
$\textsc{Kneser}^{r}_{\widetilde{\mathrm{stab}}}$, respectively, to be
$\textsc{Kneser}^{r}({\cal F}^{(r)},m^{(r)})$, $\textsc{Kneser}^{r}({\cal
F}^{(r,\mathrm{stab})},m^{(r)})$, and $\textsc{Kneser}^{r}({\cal
F}^{(r,\widetilde{\mathrm{stab}})},m^{(r)})$. For any function $m:{\cal
A}^{(r)}\rightarrow\mathbb{N}$, we let
$\textsc{Kneser}_{\mathrm{stab}}^{r}(n,k,m)$ denote the
$\textsc{Kneser}^{r}({\cal F}^{(r,\mathrm{stab})},m)$ problem. When $r=2$, the
superscript $r$ may be omitted. For any function $m:{\cal
A}^{(2)}\rightarrow\mathbb{N}$, we let $\textsc{Kneser}(n,k,m)$ and
$\textsc{Schrijver}(n,k,m)$ denote, respectively, the problems
$\textsc{Kneser}({\cal F}^{(2)},m)$ and $\textsc{Kneser}({\cal
F}^{(2,\mathrm{stab})},m)$.

We will use the notion of polynomially computable sequences of set families,
defined below.

######  Definition 4.3.

For a set ${\cal A}$, let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$
be a sequence of set families, where for each $\alpha\in{\cal A}$, ${\cal
F}_{\alpha}$ is a family of non-empty subsets of $[n_{\alpha}]$ for some
integer $n_{\alpha}$. The sequence ${\cal F}$ is polynomially computable if
there exist polynomials $q_{1},q_{2}$ such that

  1. 1.

there exists an algorithm that given an element $\alpha\in{\cal A}$ and a set
$B\subseteq[n_{\alpha}]$ runs in time $q_{1}(n_{\alpha})$ and determines
whether $B\in{\cal F}_{\alpha}$, and

  2. 2.

there exists an algorithm that given an element $\alpha\in{\cal A}$ and a set
$D\subseteq[n_{\alpha}]$ runs in time $q_{2}(n_{\alpha})$, returns a subset of
$D$ that belongs to the family ${\cal F}_{\alpha}$ if such a subset exists,
and declares that no such subset exists otherwise.

The following lemma gives simple examples of polynomially computable
sequences.

######  Lemma 4.4.

For every integer $r\geq 2$, the sequence ${\cal F}^{(r)}$ is polynomially
computable.

  * Proof:

Fix an integer $r\geq 2$. Recall that ${\cal F}^{(r)}_{(n,k)}=\binom{[n]}{k}$
for all $(n,k)\in{\cal A}^{(r)}$. We show that ${\cal F}^{(r)}$ satisfies the
conditions of Definition 4.3. For Item 1, consider the algorithm that given a
pair $(n,k)\in{\cal A}^{(r)}$ and a set $B\subseteq[n]$, checks whether
$|B|=k$. For Item 2, consider the algorithm that given a pair $(n,k)\in{\cal
A}^{(r)}$ and a set $D\subseteq[n]$, checks whether $|D|\geq k$, and if so,
returns an arbitrary subset of $D$ of size $k$. Clearly, these algorithms can
be implemented in time polynomial in $n$, hence ${\cal F}^{(r)}$ is
polynomially computable.

We conclude this section with two lemmas on the $\textsc{Kneser}^{r}({\cal
F},m)$ problem with subset queries.

######  Lemma 4.5.

Let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$ be a polynomially
computable sequence of set families, where for each $\alpha\in{\cal A}$,
${\cal F}_{\alpha}$ is a family of non-empty subsets of $[n_{\alpha}]$ for
some integer $n_{\alpha}$, and let $m:{\cal A}\rightarrow\mathbb{N}$ be a
function. Given an instance $(\alpha,C,S)$ of the $\textsc{Kneser}^{r}({\cal
F},m)$ problem with subset queries and given a set $D\subseteq[n_{\alpha}]$
and a color $i\in[m(\alpha)]$ such that $S(D,i)=1$, it is possible to find in
polynomial time either a set $B\in{\cal F}_{\alpha}$ such that $B\subseteq D$
and $C(B)=i$ or a violation of the circuit $S$.

  * Proof:

Suppose that we are given an instance $(\alpha,C,S)$, a set
$D\subseteq[n_{\alpha}]$, and a color $i\in[m(\alpha)]$, as in the statement
of the lemma. Consider the algorithm that first checks if $D\in{\cal
F}_{\alpha}$ and $C(D)=i$. If so, the algorithm simply returns $D$, which
satisfies the required properties. Otherwise, the algorithm goes over all the
subsets $D^{\prime}\subseteq D$ obtained from $D$ by removing a single element
and evaluates the circuit $S$ at the pairs $(D^{\prime},i)$. If all those sets
$D^{\prime}$ satisfy $S(D^{\prime},i)=0$, then the set $D$ and the color $i$
form a false positive violation of the circuit $S$, and the algorithm returns
this violation. Otherwise, some $D^{\prime}$ satisfies $S(D^{\prime},i)=1$,
and the algorithm proceeds by repeating the process where $D$ is replaced by
such $D^{\prime}$. Note that the number of iterations does not exceed
$n_{\alpha}$. The total running time is polynomial, because ${\cal F}$ is
polynomially computable, which allows us to efficiently check membership in
${\cal F}_{\alpha}$, and because the circuits $C$ and $S$ can be evaluated in
polynomial time.

######  Lemma 4.6.

Let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$ be a polynomially
computable sequence of set families, where for each $\alpha\in{\cal A}$,
${\cal F}_{\alpha}$ is a family of non-empty subsets of $[n_{\alpha}]$ for
some integer $n_{\alpha}$, and let $m:{\cal A}\rightarrow\mathbb{N}$ be a
function. Given an instance $(\alpha,C,S)$ of the $\textsc{Kneser}^{r}({\cal
F},m)$ problem with subset queries and given two sets
$D_{1},D_{2}\subseteq[n_{\alpha}]$ and a color $i\in[m(\alpha)]$ such that
$D_{1}\subseteq D_{2}$, $S(D_{1},i)=1$, and $S(D_{2},i)=0$, it is possible to
find in polynomial time a violation of the circuit $S$.

  * Proof:

Suppose that we are given an instance $(\alpha,C,S)$, sets
$D_{1},D_{2}\subseteq[n_{\alpha}]$, and a color $i\in[m(\alpha)]$, as in the
statement of the lemma. Consider the algorithm that first checks whether
$D_{1}\in{\cal F}_{\alpha}$ and $C(D_{1})=i$. If so, the sets $D_{1},D_{2}$
and the color $i$ form a false negative violation of $S$, and the algorithm
returns this violation. Otherwise, $D_{1}\notin{\cal F}_{\alpha}$ or
$C(D_{1})\neq i$. In this case, by running the algorithm from Lemma 4.5 on
$(D_{1},i)$, we get either a set $B\in{\cal F}_{\alpha}$ such that $B\subseteq
D_{1}$ and $C(B)=i$ or a violation of $S$. Notice that in the former case, the
sets $B,D_{2}$ and the color $i$ form a false negative violation of $S$, hence
in both cases, the algorithm can return a violation of $S$, and we are done.
Note that the running time of the algorithm is polynomial.

###  4.2 The Con-$p$-Division Problem

We present now the formal definition of the approximate Con-$p$-Division
problem for any prime $p$. The definition essentially extends the one given
for $p=2$ in [9, Appendix B, Definition 8]. One difference between the
definitions is that we require a strict inequality in the condition (3) below.
For this reason, we denote the problem by
$\textsc{Con-$p$-Division}[<\varepsilon]$ and deviate from the notation
$\varepsilon\textsc{-}\textsc{Con-$p$-Division}$ used in the literature. Note
that we do not make any assumptions on the input valuation functions, and
therefore allow solutions that demonstrate violations of their expected
properties.

######  Definition 4.7 (The Con-$p$-Division Problem).

For an $\varepsilon\in(0,1]$, a prime $p$, and a fixed polynomial $q$, the
$\textsc{Con-$p$-Division}[<\varepsilon]$ problem on normalized monotone
functions is defined as follows. The input consists of • a Lipschitz parameter
$L\geq 0$ and • $m$ Turing machines $v_{1},\ldots,v_{m}$ that are supposed to
compute $L$-Lipschitz-continuous normalized monotone valuation functions in
${\cal B}([0,1])\rightarrow[0,1]$. The goal is to find either a partition of
$[0,1]$ into $p$ pieces $A_{1},\ldots,A_{p}$ using at most $(p-1)\cdot m$
cuts, such that
$\displaystyle|v_{i}(A_{t})-v_{i}(A_{t^{\prime}})|<\varepsilon~{}~{}~{}~{}~{}\text{for
all $i\in[m]$ and $t,t^{\prime}\in[p]$,}$ (3) or a violation of some valuation
function $v_{i}$, namely, • a violation of the normalization of $v_{i}$, or •
a violation of the running time of $v_{i}$, i.e., an input $E$ on which
$v_{i}$ does not terminate within $q(|E|+|v_{i}|)$ steps, or • a violation of
the monotonicity of $v_{i}$, or • a violation of the $L$-Lipschitz-continuity
of $v_{i}$. When $p=2$, we refer to the
$\textsc{Con-$2$-Division}[<\varepsilon]$ problem as $\textsc{Con-
Halving}[<\varepsilon]$.

Theorem 2.4 implies that for any $\varepsilon\in(0,1]$ and for every prime
$p$, the $\textsc{Con-$p$-Division}[<\varepsilon]$ problem is total and thus
lies in $\mathsf{TFNP}$.

###  4.3 From Kneser to $\textsc{Con-Halving}[<1]$

We consider now the case $p=2$ and present our reduction from the general
$\textsc{Kneser}({\cal F},m)$ problem with subset queries, where $m$ is
smaller by one than the bound given by Theorem 1.1, to the $\textsc{Con-
Halving}[<\varepsilon]$ problem with $\varepsilon=1$. As a consequence, we
will obtain Theorem 1.2.

######  Theorem 4.8.

Let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$ be a polynomially
computable sequence of set families. Then, there exists a polynomial-time
reduction from the $\textsc{Kneser}({\cal F},\mathop{\mathrm{cd}}_{2}({\cal
F}_{\alpha})-1)$ problem with subset queries to the $\textsc{Con-Halving}[<1]$
problem on normalized monotone functions.

  * Proof:

For a polynomially computable sequence of set families ${\cal F}=({\cal
F}_{\alpha})_{\alpha\in{\cal A}}$, consider an instance of the
$\textsc{Kneser}({\cal F},\mathop{\mathrm{cd}}_{2}({\cal F}_{\alpha})-1)$
problem with subset queries, that is, an element $\alpha\in{\cal A}$ and
Boolean circuits $C:\\{0,1\\}^{n}\rightarrow[m]$ and
$S:\\{0,1\\}^{n}\times[m]\rightarrow\\{0,1\\}$ that are supposed to represent
a coloring $c:{\cal F}_{\alpha}\rightarrow[m]$ of the vertices of $K({\cal
F}_{\alpha})$ where $n=n_{\alpha}$ and $m=\mathop{\mathrm{cd}}_{2}({\cal
F}_{\alpha})-1$ (see Definition 4.2). Consider the reduction that given such
an input returns $m$ Turing machines that compute the valuation functions
$v_{1},\ldots,v_{m}:{\cal B}([0,1])\rightarrow[0,1]$ defined as follows. For
each $i\in[m]$ and any $E\in{\cal B}([0,1])$, let $x^{E}\in[0,1]^{n}$ denote
the vector defined by $x^{E}_{j}=n\cdot\mu(E\cap I_{j})$ where
$I_{j}=(\frac{j-1}{n},\frac{j}{n})$ for all $j\in[n]$, let $\pi$ be a
permutation of $[n]$ such that $x^{E}_{\pi(1)}\leq
x^{E}_{\pi(2)}\leq\cdots\leq x^{E}_{\pi(n)}$, and define

$\displaystyle v_{i}(E)=\sum_{j=1}^{n}{(x^{E}_{\pi(j)}-x^{E}_{\pi(j-1)})\cdot
S(\\{\pi(j),\pi(j+1),\ldots,\pi(n)\\},i)},$ (4)

where $x^{E}_{\pi(0)}=0$. Notice that $v_{i}(E)$ is a combination of $0,1$
values with non-negative coefficients whose sum is at most $1$. This implies
that $v_{i}(E)\in[0,1]$ for all $E\in{\cal B}([0,1])$, that is, $v_{i}$ is
normalized.

We claim that given the Boolean circuit $S$, it is possible to produce in
polynomial time efficient Turing machines that compute the functions
$v_{1},\ldots,v_{m}$. Indeed, for each $i\in[m]$, consider the Turing machine
that given any $E\in{\cal B}([0,1])$, represented as a union of sub-intervals
of $[0,1]$ with rational endpoints, computes the vector $x^{E}$ whose values
are the normalized Lebesgue measures of $E$ on the intervals
$I_{1},\ldots,I_{n}$ and finds a permutation $\pi$ of $[n]$ that corresponds
to a non-decreasing order of these values. Then, the machine determines the
value of $v_{i}(E)$ given in (4) using $n$ evaluations of the Boolean circuit
$S$. Observe that the running time of such a machine is polynomial in the size
of the representation of $E$ and in the size of the circuit $S$, which is not
larger than the size of the encoding of the machine itself. We further define
the Lipschitz parameter to be $L=n$. This gives us an instance of the
$\textsc{Con-Halving}[<1]$ problem on normalized monotone functions.

Before proving the correctness of the reduction, let us add some notation. For
a set $E\in{\cal B}([0,1])$ and a color $i\in[m]$, let $a^{E}_{i}$ denote the
largest value $a\in[0,1]$ such that $S(\\{j\in[n]\mid x^{E}_{j}\geq a\\},i)=1$
if such an $a$ exists, and $a^{E}_{i}=0$ otherwise. Observe, using (4), that
if the answers of the circuit $S$ are consistent with some coloring as
described in Definition 4.2, then for all $E\in{\cal B}([0,1])$ and $i\in[m]$,
it holds that $v_{i}(E)=a^{E}_{i}$. The following lemma shows that given a set
$E$ and a color $i$ for which this equality does not hold, it is possible to
efficiently find a violation of the circuit $S$.

######  Lemma 4.9.

Given a set $E\in{\cal B}([0,1])$ and a color $i\in[m]$ such that
$v_{i}(E)\neq a^{E}_{i}$, it is possible to find in polynomial time a
violation of the circuit $S$.

  * Proof:

Consider the algorithm that given a set $E\in{\cal B}([0,1])$ and a color
$i\in[m]$ with $v_{i}(E)\neq a^{E}_{i}$, computes the vector $x^{E}$ and a
permutation $\pi$ of $[n]$ that corresponds to a non-decreasing order of the
values of $x^{E}$. Then, for each $j\in[n]$, the algorithm evaluates the
circuit $S$ at the pair $(T_{j},i)$, where
$T_{j}=\\{\pi(j),\pi(j+1),\ldots,\pi(n)\\}$. By $v_{i}(E)\neq a^{E}_{i}$,
using (4), it follows that some $j$ satisfies that $S(T_{j},i)=0$ and
$S(T_{j+1},i)=1$. Such a $j$ can be found efficiently, and by Lemma 4.6, the
sets $T_{j},T_{j+1}$ (which satisfy $T_{j+1}\subseteq T_{j}$) and the color
$i$ can be used to efficiently find a violation of $S$.

We prove now the correctness of the reduction, namely, that given a solution
for the produced $\textsc{Con-Halving}[<1]$ instance, it is possible to find
in polynomial time a solution for the given instance of $\textsc{Kneser}({\cal
F},\mathop{\mathrm{cd}}_{2}({\cal F}_{\alpha})-1)$ with subset queries.
Suppose first that the given solution is a violation of some valuation
function $v_{i}$ with $i\in[m]$. By construction, it is impossible to violate
the normalization of $v_{i}$ or the running time of the Turing machine that
computes it, hence the solution violates either the monotonicity or the
$L$-Lipschitz-continuity of $v_{i}$.

If the solution violates the monotonicity of $v_{i}$, then we are given two
sets $E_{1},E_{2}\in{\cal B}([0,1])$ such that $E_{1}\subseteq E_{2}$ and
$v_{i}(E_{2})<v_{i}(E_{1})$. We may assume that $v_{i}(E_{1})=a^{E_{1}}_{i}$
and $v_{i}(E_{2})=a^{E_{2}}_{i}$, and thus $a^{E_{2}}_{i}<a^{E_{1}}_{i}$, as
otherwise, by Lemma 4.9, it is possible to efficiently find a violation of the
circuit $S$. Put $D_{1}=\\{j\in[n]\mid x^{E_{1}}_{j}\geq a^{E_{1}}_{i}\\}$,
and notice that the definition of $a^{E_{1}}_{i}$ implies that $S(D_{1},i)=1$.
Put $D_{2}=\\{j\in[n]\mid x^{E_{2}}_{j}\geq a^{E_{1}}_{i}\\}$, and use the
fact that $E_{1}\subseteq E_{2}$ to obtain that $x^{E_{1}}_{j}\leq
x^{E_{2}}_{j}$ for all $j\in[n]$, which implies that $D_{1}\subseteq D_{2}$.
However, using $a^{E_{2}}_{i}<a^{E_{1}}_{i}$, it follows that $S(D_{2},i)=0$.
By Lemma 4.6, the sets $D_{1},D_{2}$ and the color $i$ can be used to
efficiently find a violation of $S$.

If the solution violates the $L$-Lipschitz-continuity of $v_{i}$ for $L=n$,
then we are given two sets $E_{1},E_{2}\in{\cal B}([0,1])$ such that for some
$\delta>0$, $\mu(E_{1}\triangle E_{2})=\delta$ and
$|v_{i}(E_{1})-v_{i}(E_{2})|>n\cdot\delta$. Assume without loss of generality
that $v_{i}(E_{1})\geq v_{i}(E_{2})$, which implies that
$v_{i}(E_{1})>v_{i}(E_{2})+n\cdot\delta$. Put $E_{3}=E_{1}\cup E_{2}$. We may
assume that $v_{i}(E_{3})\geq v_{i}(E_{1})$, and thus
$v_{i}(E_{3})>v_{i}(E_{2})+n\cdot\delta$, as otherwise the sets $E_{1}$ and
$E_{3}$ violate the monotonicity of $v_{i}$, and this violation can be handled
as before. We may also assume, by Lemma 4.9, that $v_{i}(E_{2})=a^{E_{2}}_{i}$
and $v_{i}(E_{3})=a^{E_{3}}_{i}$, implying that
$a_{i}^{E_{3}}>a_{i}^{E_{2}}+n\cdot\delta$. Put $D_{3}=\\{j\in[n]\mid
x^{E_{3}}_{j}\geq a^{E_{3}}_{i}\\}$, and notice that the definition of
$a^{E_{3}}_{i}$ implies that $S(D_{3},i)=1$. Now, put $D_{2}=\\{j\in[n]\mid
x^{E_{2}}_{j}\geq a^{E_{3}}_{i}-n\cdot\delta\\}$. By $\mu(E_{1}\triangle
E_{2})=\delta$, it follows that $x^{E_{3}}_{j}\leq x^{E_{2}}_{j}+n\cdot\delta$
for all $j\in[n]$, which implies that $D_{3}\subseteq D_{2}$. However, using
$a^{E_{2}}_{i}<a^{E_{3}}_{i}-n\cdot\delta$, it follows that $S(D_{2},i)=0$. By
Lemma 4.6, the sets $D_{2},D_{3}$ and the color $i$ can be used to efficiently
find a violation of $S$.

It remains to consider a solution which forms a partition of the unit interval
into two pieces $A_{1}$ and $A_{2}$ with at most $m$ cuts, such that
$|v_{i}(A_{1})-v_{i}(A_{2})|<1$ for all $i\in[m]$. Given such a solution, it
is possible to efficiently construct the set $Y$ of indices $j\in[n]$ for
which the sub-interval $I_{j}$ contains a cut. Every sub-interval $I_{j}$ with
$j\in[n]\setminus Y$ is fully contained in either $A_{1}$ or $A_{2}$. For
$t\in[2]$, put $M_{t}=\\{j\in[n]\setminus Y\mid I_{j}\subseteq A_{t}\\}$. By
$|Y|\leq m<\mathop{\mathrm{cd}}_{2}({\cal F}_{\alpha})$, it follows that for
some $t_{1}\in[2]$, there exists a set $B_{1}\in{\cal F}_{\alpha}$ such that
$B_{1}\subseteq M_{t_{1}}$. Moreover, such a set $B_{1}$ can be found
efficiently, because the sequence ${\cal F}$ is polynomially computable (see
Definition 4.3, Item 2). Note that for each $j\in B_{1}$, it holds that
$\mu(A_{t_{1}}\cap I_{j})=\tfrac{1}{n}$.

Let $\ell=c(B_{1})$ denote the color assigned to the set $B_{1}$ by the input
coloring $c$. This color can be efficiently determined using the circuit $C$.
It may be assumed that $S(B_{1},\ell)=1$, as otherwise $B_{1}$ and $\ell$
provide a false negative violation of the circuit $S$. Put $E=\cup_{j\in
B_{1}}{I_{j}}$. By Lemma 4.9, we may assume that $v_{\ell}(E)=a^{E}_{\ell}=1$.
Since $E\subseteq A_{t_{1}}$, if $v_{\ell}(A_{t_{1}})<1$ we obtain a violation
of the monotonicity of $v_{\ell}$, which can be handled as before. Otherwise,
it holds that $v_{\ell}(A_{t_{1}})=1$. Our assumption on the given solution
implies that $|v_{\ell}(A_{1})-v_{\ell}(A_{2})|<1$, so letting $t_{2}$ denote
the element of $[2]\setminus\\{t_{1}\\}$, it follows that
$v_{\ell}(A_{t_{2}})>0$. Again, by Lemma 4.9, we may assume that
$v_{\ell}(A_{t_{2}})=a^{A_{t_{2}}}_{\ell}>0$. This yields that the set
$D=\\{j\in[n]\mid x^{A_{t_{2}}}_{j}\geq a^{A_{t_{2}}}_{\ell}\\}$ satisfies
$S(D,\ell)=1$. By Lemma 4.5, it is possible to efficiently find either a
violation of $S$ or a set $B_{2}\in{\cal F}_{\alpha}$ such that
$B_{2}\subseteq D$ and $C(B_{2})=\ell$. We finally observe that the sets
$B_{1}$ and $B_{2}$ are disjoint. Indeed, for each $j\in[n]$, if $j\in B_{1}$
then $\mu(A_{t_{1}}\cap I_{j})=\tfrac{1}{n}$ and if $j\in B_{2}$ then
$\mu(A_{t_{2}}\cap I_{j})\geq\tfrac{1}{n}\cdot a^{A_{t_{2}}}_{\ell}>0$, but
these two conditions cannot hold simultaneously, because $A_{1}$ and $A_{2}$
form a partition of $[0,1]$, hence $\mu(A_{t_{1}}\cap I_{j})+\mu(A_{t_{2}}\cap
I_{j})=\mu(I_{j})=\tfrac{1}{n}$. This implies that the sets $B_{1}$ and
$B_{2}$ form a monochromatic edge in $K({\cal F}_{\alpha})$ and thus a
solution for the given instance of $\textsc{Kneser}({\cal
F},\mathop{\mathrm{cd}}_{2}({\cal F}_{\alpha})-1)$ with subset queries,
completing the proof.

We are ready to derive Theorem 1.2.

  * Proof of Theorem 1.2:

By Lemma 4.4, the sequence ${\cal F}^{(2)}$ is polynomially computable. This
allows us to apply Theorem 4.8, which yields that there exists a polynomial-
time reduction from $\textsc{Kneser}({\cal
F}^{(2)},\mathop{\mathrm{cd}}_{2}({\cal F}^{(2)}_{(n,k)})-1)$ with subset
queries to $\textsc{Con-Halving}[<1]$ on normalized monotone functions. By
Lemma 2.3, it holds that $\mathop{\mathrm{cd}}_{2}({\cal
F}^{(2)}_{(n,k)})=n-2k+2$. It thus follows that the $\textsc{Kneser}({\cal
F}^{(2)},\mathop{\mathrm{cd}}_{2}({\cal F}^{(2)}_{(n,k)})-1)$ problem
coincides with the Kneser problem, and we are done.

###  4.4 From $\textsc{Kneser}^{p}$ to
$\textsc{Con-$p$-Division}[<\tfrac{1}{2}]$

We next present a reduction, for any prime $p\geq 3$, from the
$\textsc{Kneser}^{p}({\cal F},m)$ problem with subset queries, where $m$ is
smaller than the bound given by Theorem 1.1, to the
$\textsc{Con-$p$-Division}[<\varepsilon]$ problem with
$\varepsilon=\tfrac{1}{2}$. As a consequence, we will obtain Theorem 1.3.

######  Theorem 4.10.

Let $p\geq 3$ be a prime, and let ${\cal F}=({\cal
F}_{\alpha})_{\alpha\in{\cal A}}$ be a polynomially computable sequence of set
families. Then, there exists a polynomial-time reduction from the
$\textsc{Kneser}^{p}({\cal F},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\rfloor)$ problem with subset queries to the
$\textsc{Con-$p$-Division}[<\tfrac{1}{2}]$ problem on normalized monotone
functions.

  * Proof:

Fix a prime $p\geq 3$. For a polynomially computable sequence of set families
${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$, consider an instance of
the $\textsc{Kneser}^{p}({\cal F},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\rfloor)$ problem with subset queries, that is, an element
$\alpha\in{\cal A}$ and Boolean circuits $C:\\{0,1\\}^{n}\rightarrow[m]$ and
$S:\\{0,1\\}^{n}\times[m]\rightarrow\\{0,1\\}$ that are supposed to represent
a coloring $c:{\cal F}_{\alpha}\rightarrow[m]$ of the vertices of $K^{p}({\cal
F}_{\alpha})$ where $n=n_{\alpha}$ and
$m=\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal F}_{\alpha})-1}{p-1}\rfloor$
(see Definition 4.2). Consider the reduction that given such an input returns
$m$ Turing machines that compute the valuation functions
$v_{1},\ldots,v_{m}:{\cal B}([0,1])\rightarrow[0,1]$ defined as follows. For
each $i\in[m]$ and any $E\in{\cal B}([0,1])$, let $x^{E}\in[0,1]^{n}$ denote
the vector defined by $x^{E}_{j}=n\cdot\mu(E\cap I_{j})$ where
$I_{j}=(\frac{j-1}{n},\frac{j}{n})$ for all $j\in[n]$, let $\pi$ be a
permutation of $[n]$ such that $x^{E}_{\pi(1)}\leq
x^{E}_{\pi(2)}\leq\cdots\leq x^{E}_{\pi(n)}$, and define

$\displaystyle v_{i}(E)=\sum_{j=1}^{n}{(x^{E}_{\pi(j)}-x^{E}_{\pi(j-1)})\cdot
S(\\{\pi(j),\pi(j+1),\ldots,\pi(n)\\},i)},$

where $x^{E}_{\pi(0)}=0$. As shown in the proof of Theorem 4.8, the functions
$v_{1},\ldots,v_{m}$ are normalized, and it is possible to produce in
polynomial time efficient Turing machines that compute them. We further define
the Lipschitz parameter to be $L=n$. This gives us an instance of the
$\textsc{Con-$p$-Division}[<\tfrac{1}{2}]$ problem on normalized monotone
functions.

For correctness, we show that given a solution for the produced
$\textsc{Con-$p$-Division}[<\tfrac{1}{2}]$ instance, it is possible to
efficiently find a solution for the given instance of
$\textsc{Kneser}^{p}({\cal F},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\rfloor)$ with subset queries. As shown in the proof of
Theorem 4.8, if the given solution is a violation of one of the valuation
functions, then it can be used to efficiently find a violation of the circuit
$S$. To avoid repetitions, we omit the details here and focus on the case
where the given solution is a partition of the unit interval into $p$ pieces
$A_{1},\ldots,A_{p}$ with at most $(p-1)\cdot m$ cuts, such that
$|v_{i}(A_{t})-v_{i}(A_{t^{\prime}})|<\tfrac{1}{2}$ for all $i\in[m]$ and
$t,t^{\prime}\in[p]$. Given such a solution, it is possible to efficiently
construct the set $Y$ of indices $j\in[n]$ for which the sub-interval $I_{j}$
contains a cut. Every sub-interval $I_{j}$ with $j\in[n]\setminus Y$ is fully
contained in one of the pieces $A_{1},\ldots,A_{p}$. For each $t\in[p]$, put
$M_{t}=\\{j\in[n]\mid I_{j}\subseteq A_{t}\\}$. By $|Y|\leq(p-1)\cdot
m<\mathop{\mathrm{cd}}_{p}({\cal F}_{\alpha})$, it follows that for some
$t_{1}\in[p]$, there exists a set $B\in{\cal F}_{\alpha}$ such that
$B\subseteq M_{t_{1}}$. Moreover, such a set $B$ can be found efficiently,
because the sequence ${\cal F}$ is polynomially computable (see Definition
4.3, Item 2). Note that for each $j\in B$, it holds that $\mu(A_{t_{1}}\cap
I_{j})=\tfrac{1}{n}$. We will assume from now on that for any given set
$E\in{\cal B}([0,1])$ and color $i\in[m]$, it holds that $v_{i}(E)=a^{E}_{i}$,
where $a^{E}_{i}$ is the largest value $a\in[0,1]$ such that $S(\\{j\in[n]\mid
x^{E}_{j}\geq a\\},i)=1$ if such an $a$ exists, and $a^{E}_{i}=0$ otherwise.
As shown in the proof of Theorem 4.8, if this is not the case, then $E$ and
$i$ can be used to efficiently obtain a violation of the circuit $S$.

Let $\ell=c(B)$ denote the color assigned to the set $B$ by the input coloring
$c$. This color can be efficiently determined using the circuit $C$. It may be
assumed that $S(B,\ell)=1$, as otherwise $B$ and $\ell$ provide a false
negative violation of the circuit $S$. Put $E=\cup_{j\in B}{I_{j}}$, and
observe that $v_{\ell}(E)=a^{E}_{\ell}=1$. Since $E\subseteq A_{t_{1}}$, if
$v_{\ell}(A_{t_{1}})<1$ we obtain a violation of the monotonicity of
$v_{\ell}$. Otherwise, it holds that $v_{\ell}(A_{t_{1}})=1$. Our assumption
on the given solution implies that for each $t\in[p]$, it holds that
$|v_{\ell}(A_{t_{1}})-v_{\ell}(A_{t})|<\tfrac{1}{2}$ and thus
$v_{\ell}(A_{t})=a_{\ell}^{A_{t}}>\tfrac{1}{2}$.

Now, for each $t\in[p]$, put $M_{t}=\\{j\in[n]\mid x_{j}^{A_{t}}\geq
a_{\ell}^{A_{t}}\\}$, and observe that $S(M_{t},\ell)=1$. By Lemma 4.5, it is
possible to efficiently find either a violation of $S$ or a set $B_{t}\in{\cal
F}_{\alpha}$ such that $B_{t}\subseteq M_{t}$ and $C(B_{t})=\ell$. If no
violation is found, the obtained sets $B_{1},\ldots,B_{p}$ are pairwise
disjoint, because for each $j\in[n]$, it holds that
$\sum_{t=1}^{p}{\mu(A_{t}\cap I_{j})}=\mu(I_{j})=\tfrac{1}{n}$, hence at most
one $t\in[p]$ can satisfy $\mu(A_{t}\cap I_{j})=\frac{1}{n}\cdot
x_{j}^{A_{t}}\geq\frac{1}{n}\cdot a_{\ell}^{A_{t}}>\tfrac{1}{2n}$. This
implies that the sets $B_{1},\ldots,B_{p}$ form a monochromatic hyperedge in
$K^{p}({\cal F}_{\alpha})$ and thus a solution for the given instance of
$\textsc{Kneser}^{p}({\cal F},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\rfloor)$ with subset queries, completing the proof.

We are ready to derive Theorem 1.3.

  * Proof of Theorem 1.3:

Fix a prime $p\geq 3$. By Lemma 4.4, the sequence ${\cal F}^{(p)}$ is
polynomially computable, allowing us to apply Theorem 4.10, which yields that
there exists a polynomial-time reduction from $\textsc{Kneser}^{p}({\cal
F}^{(p)},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}^{(p)}_{(n,k)})-1}{p-1}\rfloor)$ with subset queries to
$\textsc{Con-$p$-Division}[<\tfrac{1}{2}]$ on normalized monotone functions.
By Lemma 2.3, it holds that $\mathop{\mathrm{cd}}_{p}({\cal
F}^{(p)}_{(n,k)})=n-p(k-1)$. It thus follows that the
$\textsc{Kneser}^{p}({\cal
F}^{(p)},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}^{(p)}_{(n,k)})-1}{p-1}\rfloor)$ problem coincides with the
$\textsc{Kneser}^{p}$ problem, and we are done.

##  5 $\textsc{Kneser}^{p}$ lies in $\mathsf{PPA}\textsc{-}p$

In this section, we prove the membership of the $\textsc{Kneser}^{p}$ problem
in the complexity class $\mathsf{PPA}\textsc{-}p$ for every prime $p$,
confirming Theorem 1.4. The result is proved in two stronger forms through
known connections between the chromatic number of Kneser hypergraphs and a
${\mathbb{Z}}_{p}$-variant of Tucker’s lemma. We then establish limitations on
the complexity of variants of the $\textsc{Kneser}^{r}$ problem, restricted to
colorings with a bounded number of colors. We start by presenting the
computational search problem associated with the ${\mathbb{Z}}_{p}$-Tucker
lemma.

###  5.1 The ${\mathbb{Z}}_{p}\textsc{-Tucker}$ Problem

The definition of the ${\mathbb{Z}}_{p}\textsc{-Tucker}$ problem requires a
few notations. For a prime $p$, we denote the elements of the cyclic group
${\mathbb{Z}}_{p}$ of order $p$ by $\omega^{t}$ for $t\in[p]$. A signed set
over ${\mathbb{Z}}_{p}$ is a set whose elements are associated with signs from
${\mathbb{Z}}_{p}$. A signed subset of $[n]$ over ${\mathbb{Z}}_{p}$ can be
represented by a vector $X\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}$, where the
subset consists of the elements $j\in[n]$ with $X_{j}\neq 0$, and the sign of
every such $j$ is $X_{j}$. For two signed sets
$X,Y\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}$, we denote by $X\preceq Y$ the fact
that for every $j\in[n]$, if $X_{j}\neq 0$ then $X_{j}=Y_{j}$.

######  Definition 5.1.

(The ${\mathbb{Z}}_{p}\textsc{-Tucker}$ Problem) For a prime $p$, the
${\mathbb{Z}}_{p}\textsc{-Tucker}$ problem is defined as follows. Its input
consists of two integers $n$ and $s$ satisfying
$s\leq\lfloor\frac{n-1}{p-1}\rfloor$ along with a Boolean circuit that
represents a ${\mathbb{Z}}_{p}$-equivariant map
$\lambda:({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}\rightarrow{\mathbb{Z}}_{p}\times[s]$,
that is, a function that maps every nonzero
$X\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}$ to a pair
$\lambda(X)=(\lambda_{1}(X),\lambda_{2}(X))$ in ${\mathbb{Z}}_{p}\times[s]$,
where for each $t\in[p]$ it holds that
$\lambda(\omega^{t}X)=(\omega^{t}\lambda_{1}(X),\lambda_{2}(X))$. The goal is
to find a chain of $p$ signed sets $X_{1}\preceq X_{2}\preceq\cdots\preceq
X_{p}$ in $({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}$ that are
assigned by $\lambda$ the same absolute value with pairwise distinct signs,
that is, for some permutation $\pi$ of $[p]$ and some $\ell\in[s]$, it holds
that $\lambda(X_{t})=(\omega^{\pi(t)},\ell)$ for all $t\in[p]$.

Note that the assumption that the map $\lambda$ is
${\mathbb{Z}}_{p}$-equivariant can be enforced syntactically. The existence of
a solution for every instance of the ${\mathbb{Z}}_{p}\textsc{-Tucker}$
problem was proved by Ziegler [36]. Its membership in
$\mathsf{PPA}\textsc{-}p$, stated below, follows from a much more general
result due to Filos-Ratsikas et al. [16, Theorem 5.2].

######  Theorem 5.2 ([16]).

For every prime $p$, the ${\mathbb{Z}}_{p}\textsc{-Tucker}$ problem lies in
$\mathsf{PPA}\textsc{-}p$.

In order to obtain the membership of the $\textsc{Kneser}^{p}$ problem in
$\mathsf{PPA}\textsc{-}p$ for general sequences of set families, we need the
following definition.

######  Definition 5.3.

For a set ${\cal A}$, let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$
be a sequence of set families, where for each $\alpha\in{\cal A}$, ${\cal
F}_{\alpha}$ is a family of non-empty subsets of $[n_{\alpha}]$ for some
integer $n_{\alpha}$. The sequence ${\cal F}$ is strongly polynomially
computable if it is possible to associate with each family ${\cal F}_{\alpha}$
a linear order on its members, denoted $\leq$, such that there exist
polynomials $q_{1},q_{2},q_{3}$ satisfying that

  1. 1.

there exists an algorithm that given an element $\alpha\in{\cal A}$ runs in
time $q_{1}(n_{\alpha})$ and returns a Boolean circuit
$C_{1}:\\{0,1\\}^{2n_{\alpha}}\rightarrow\\{0,1\\}$ such that for every pair
of sets $B_{1},B_{2}\in{\cal F}_{\alpha}$, it holds that
$C_{1}(B_{1},B_{2})=1$ if and only if $B_{1}\leq B_{2}$,

  2. 2.

there exists an algorithm that given an element $\alpha\in{\cal A}$ runs in
time $q_{2}(n_{\alpha})$ and returns a Boolean circuit
$C_{2}:\\{0,1\\}^{n_{\alpha}}\rightarrow\\{0,1\\}^{n_{\alpha}}$ such that for
every set $D\subseteq[n_{\alpha}]$, $C_{2}(D)$ is the minimal subset of $D$,
with respect to the order $\leq$, that belongs to the family ${\cal
F}_{\alpha}$ if such a subset exists, and the empty set otherwise, and

  3. 3.

for every prime $p$, there exists an algorithm that given an element
$\alpha\in{\cal A}$ runs in time $q_{3}(n_{\alpha})$ and returns the value of
${\mathop{\mathrm{cd}}}_{p}({\cal F}_{\alpha})$.

The following lemma gives simple examples of strongly polynomially computable
sequences.

######  Lemma 5.4.

For every integer $r\geq 2$, the sequence ${\cal F}^{(r)}$ is strongly
polynomially computable.

  * Proof:

Fix an integer $r\geq 2$. Recall that ${\cal F}^{(r)}_{(n,k)}=\binom{[n]}{k}$
for all $(n,k)\in{\cal A}^{(r)}$. We associate with the sets of ${\cal
F}^{(r)}_{(n,k)}$ the linear order $\leq$, defined by $B_{1}\leq B_{2}$ if
$B_{1}=B_{2}$ or the smallest element of $B_{1}\triangle B_{2}$ belongs to
$B_{1}$. Similarly to the proof of Lemma 4.4, it can be verified that ${\cal
F}^{(r)}$ satisfies the conditions of Definition 5.3. Note that Item 3 follows
from Lemma 2.3.

###  5.2 From $\textsc{Kneser}^{p}$ to ${\mathbb{Z}}_{p}\textsc{-Tucker}$

The following theorem asserts that the $\textsc{Kneser}^{p}({\cal F},m)$
problem is efficiently reducible to the ${\mathbb{Z}}_{p}\textsc{-Tucker}$
problem for every strongly polynomially computable sequence ${\cal F}$,
whenever the number of colors $m$ is smaller than the bound given by Theorem
1.1. Its proof verifies that a mathematical argument of Ziegler [36] can be
transformed into an efficient reduction. We present it here with the details
for completeness.

######  Theorem 5.5.

Let $p$ be a prime, and let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$
be a strongly polynomially computable sequence of set families. Then,
$\textsc{Kneser}^{p}({\cal F},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\rfloor)$ is polynomial-time reducible to
${\mathbb{Z}}_{p}\textsc{-Tucker}$.

  * Proof:

Fix a prime $p$ and a strongly polynomially computable sequence of set
families ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$. Consider an
instance of $\textsc{Kneser}^{p}({\cal
F},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal F}_{\alpha})-1}{p-1}\rfloor)$,
that is, an element $\alpha\in{\cal A}$ along with a Boolean circuit that
represents a coloring $c:{\cal F}_{\alpha}\rightarrow[m]$ of the vertices of
$K^{p}({\cal F}_{\alpha})$, where ${\cal F}_{\alpha}$ is a family of subsets
of $[n]$ for some $n=n_{\alpha}$ and
$m=m(\alpha)=\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\rfloor$. It may be assumed that $p-1$ divides $n-1$.
Indeed, otherwise increase the size $n$ of the ground set of ${\cal
F}_{\alpha}$ by at most $p-2$, so that this condition will be satisfied. This
change of $n$ does not affect the chromatic number of $K^{p}({\cal
F}_{\alpha})$ nor the value of ${\mathop{\mathrm{cd}}}_{p}({\cal
F}_{\alpha})$.

Consider the function
$\lambda:({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}\rightarrow{\mathbb{Z}}_{p}\times[s]$
defined as follows. For a given
$X\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}$, put
$X^{t}=\\{j\in[n]\mid X_{j}=\omega^{t}\\}$ for each $t\in[p]$, and let
$|X|=\sum_{t=1}^{p}{|X^{t}|}$ denote the number of nonzero elements in $X$. We
define $\lambda(X)=(\lambda_{1}(X),\lambda_{2}(X))$ according to the following
two cases.

    1. 1.

If $|X|\leq n-\mathop{\mathrm{cd}}_{p}({\cal F}_{\alpha})$, then let $t\in[p]$
denote the index of the set $X^{t}$ that includes the smallest element of
$\cup_{t^{\prime}\in[p]}{X^{t^{\prime}}}$, and define
$\lambda(X)=(\omega^{t},\lceil\frac{|X|}{p-1}\rceil)$.

    2. 2.

If $|X|>n-\mathop{\mathrm{cd}}_{p}({\cal F}_{\alpha})$, then it follows that
some $X^{t}$ contains a set of ${\cal F}_{\alpha}$. Among the sets of ${\cal
F}_{\alpha}$ that are contained in the sets $X^{1},\ldots,X^{p}$, let $B$
denote the minimal one with respect to the linear order associated with ${\cal
F}_{\alpha}$. Let $t\in[p]$ denote the index satisfying $B\subseteq X^{t}$,
and define
$\lambda(X)=(\omega^{t},c(B)+\lceil\frac{n-\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})}{p-1}\rceil)$.

Observe that $\lambda$ returns pairs in ${\mathbb{Z}}_{p}\times[s]$ for

$s=m+\Big{\lceil}\frac{n-\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})}{p-1}\Big{\rceil}=\Big{\lfloor}\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\Big{\rfloor}+\Big{\lfloor}\frac{n-\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\Big{\rfloor}+1=\frac{n-1}{p-1},$

where in the last equality we use the fact that $p-1$ divides $n-1$. We claim
that the function $\lambda$ is ${\mathbb{Z}}_{p}$-equivariant. To see this,
consider some $X\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}$ and
$t\in[p]$, and notice that $|X|=|\omega^{t}X|$. Notice further that for each
$t^{\prime}\in[p]$, the indices of the entries in $X$ that are equal to
$\omega^{t^{\prime}}$ are precisely the indices of the entries in
$\omega^{t}X$ that are equal to $\omega^{t+t^{\prime}}$. In particular, if the
first nonzero element in $X$ is $\omega^{t^{\prime}}$ then the first nonzero
element in $\omega^{t}X$ is $\omega^{t+t^{\prime}}$. By considering the two
cases in the definition of $\lambda$, it follows that
$\lambda(\omega^{t}X)=(\omega^{t}\lambda_{1}(X),\lambda_{2}(X))$, as required.
The assumption that ${\cal F}$ is strongly polynomially computable (see
Definition 5.3) implies that given a Boolean circuit that represents the
coloring $c$, it is possible to construct in polynomial time a Boolean circuit
that represents the function $\lambda$.

To prove the correctness of the reduction, consider a solution for the
produced instance of ${\mathbb{Z}}_{p}\textsc{-Tucker}$, that is, a chain of
$p$ signed sets $X_{1}\preceq X_{2}\preceq\cdots\preceq
X_{p}\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}$ for which there
exist a permutation $\pi$ of $[p]$ and an $\ell\in[s]$, such that
$\lambda(X_{t})=(\omega^{\pi(t)},\ell)$ for all $t\in[p]$. We first claim that
$\ell>\lceil\frac{n-\mathop{\mathrm{cd}}_{p}({\cal F}_{\alpha})}{p-1}\rceil$.
To see this, suppose for contradiction that
$\ell\leq\lceil\frac{n-\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})}{p-1}\rceil$, and observe that the definition of $\lambda$
implies that $\ell=\lceil\frac{|X_{t}|}{p-1}\rceil$ for all $t\in[p]$. It
follows that for some indices $t_{1}<t_{2}\in[p]$, it holds that
$|X_{t_{1}}|=|X_{t_{2}}|$. However, by $X_{t_{1}}\preceq X_{t_{2}}$, it
follows that $X_{t_{1}}=X_{t_{2}}$, in contradiction to the fact that
$\lambda_{1}(X_{t_{1}})\neq\lambda_{1}(X_{t_{2}})$.

Finally, using $\ell>\lceil\frac{n-\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})}{p-1}\rceil$, the definition of $\lambda$ implies that for every
$t\in[p]$, there exists a subset of $X_{t}^{\pi(t)}$ that belongs to ${\cal
F}_{\alpha}$. For each $t\in[p]$, let $B_{t}$ denote the minimal set of ${\cal
F}_{\alpha}$ that is contained in $X_{t}^{\pi(t)}$, with respect to the order
associated with ${\cal F}_{\alpha}$. By the definition of $\lambda$, we have
$\ell=c(B_{t})+\lceil\frac{n-\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})}{p-1}\rceil$ for all $t\in[p]$. The assumption that ${\cal F}$ is
strongly polynomially computable allows us to find the sets
$B_{1},\ldots,B_{p}$ efficiently (see Definition 5.3, Item 2). For any
$t_{1}<t_{2}\in[p]$, the fact that $X_{t_{1}}\preceq X_{t_{2}}$ implies that
$B_{t_{1}}$ and $B_{t_{2}}$ are disjoint. It thus follows that the sets
$B_{1},\ldots,B_{p}$ form a monochromatic hyperedge of the coloring $c$ of
$K^{p}({\cal F}_{\alpha})$. Since this monochromatic hyperedge can be found in
polynomial time given the signed sets $X_{1},X_{2},\ldots,X_{p}$, we are done.

By combining Theorem 5.2 with Theorem 5.5, we derive the following corollary.

######  Corollary 5.6.

Let $p$ be a prime, and let ${\cal F}=({\cal F}_{\alpha})_{\alpha\in{\cal A}}$
be a strongly polynomially computable sequence of set families. Then, the
$\textsc{Kneser}^{p}({\cal F},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}_{\alpha})-1}{p-1}\rfloor)$ problem lies in $\mathsf{PPA}\textsc{-}p$.

As a special case of Corollary 5.6, we derive Theorem 1.4.

  * Proof of Theorem 1.4:

Fix a prime $p$. By Lemma 5.4, the sequence ${\cal F}^{(p)}$ is strongly
polynomially computable, hence by Corollary 5.6, the
$\textsc{Kneser}^{p}({\cal
F}^{(p)},\lfloor\frac{\mathop{\mathrm{cd}}_{p}({\cal
F}^{(p)}_{(n,k)})-1}{p-1}\rfloor)$ problem lies in $\mathsf{PPA}\textsc{-}p$.
By Lemma 2.3, it holds that $\mathop{\mathrm{cd}}_{p}({\cal
F}^{(p)}_{(n,k)})=n-p(k-1)$, hence the latter problem coincides with the
$\textsc{Kneser}^{p}$ problem, and we are done.

We next consider the $\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{p}$ problem
associated with the hypergraph $K^{p}(n,k)_{\widetilde{\mathrm{stab}}}$, that
is, the sub-hypergraph of $K^{p}(n,k)$ induced by the almost stable
$k$-subsets of $[n]$. Corollary 5.6 can be applied to obtain a membership
result in $\mathsf{PPA}\textsc{-}p$ for this setting, however, it does not
give the largest possible number of colors. To obtain the result with an
optimal number of colors, which is smaller than the chromatic number only by
one, we apply a modified argument of Meunier [32], verifying that it provides
an efficient reduction. Let us mention, though, that the proof of [32] applies
a slightly different variant of the ${\mathbb{Z}}_{p}$-Tucker lemma, whose
proof relies on Dold’s theorem [11]. The proof below uses the version of the
lemma that corresponds to our definition of the
${\mathbb{Z}}_{p}\textsc{-Tucker}$ problem, which lies in
$\mathsf{PPA}\textsc{-}p$. See [16, Remark 1] for a discussion on the
computational aspects of Dold’s theorem.

######  Theorem 5.7.

For every prime $p$, $\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{p}$ is
polynomial-time reducible to ${\mathbb{Z}}_{p}\textsc{-Tucker}$.

  * Proof:

Fix a prime $p$, and consider an instance of
$\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{p}$, that is, integers $n$ and
$k$ with $n\geq p\cdot k$ along with a Boolean circuit that represents a
coloring $c:\binom{n}{k}_{\widetilde{\mathrm{stab}}}\rightarrow[m]$ of the
vertices of $K^{p}(n,k)_{\widetilde{\mathrm{stab}}}$ where
$m=\lfloor\frac{n-p(k-1)-1}{p-1}\rfloor$. As in the proof of Theorem 5.5, we
may assume that $p-1$ divides $n-1$.

Consider the function
$\lambda:({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}\rightarrow{\mathbb{Z}}_{p}\times[s]$
defined as follows. For a given $X$ in
$({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}$, let
$\mathop{\mathrm{alt}}(X)$ denote the length of a longest alternating
subsequence of nonzero terms of $X$, namely, the largest integer $r$ for which
there exist indices $i_{1}<\cdots<i_{r}$ such that $X_{i_{j}}\neq 0$ for all
$j\in[r]$ and $X_{i_{j}}\neq X_{i_{j+1}}$ for all $j\in[r-1]$. Put
$X^{t}=\\{j\in[n]\mid X_{j}=\omega^{t}\\}$ for each $t\in[p]$, and define
$\lambda(X)=(\lambda_{1}(X),\lambda_{2}(X))$ according to the following two
cases.

    1. 1.

If $\mathop{\mathrm{alt}}(X)\leq p(k-1)$, then let $t\in[p]$ denote the index
of the set $X^{t}$ that includes the smallest element of
$\cup_{t^{\prime}\in[p]}{X^{t^{\prime}}}$, and define
$\lambda(X)=(\omega^{t},\lceil\frac{\mathop{\mathrm{alt}}(X)}{p-1}\rceil)$.

    2. 2.

If $\mathop{\mathrm{alt}}(X)\geq p(k-1)+1$, then consider a longest
alternating subsequence of nonzero terms of $X$. Since its length is at least
$p(k-1)+1$, it follows that some $X^{t}$ contains an almost stable $k$-subset
of $[n]$. Among the almost stable $k$-subsets that are contained in the sets
$X^{1},\ldots,X^{p}$, let $B$ denote the minimal one with respect to some
linear order associated with $\binom{[n]}{k}_{\widetilde{\mathrm{stab}}}$
(say, $B_{1}\leq B_{2}$ if $B_{1}=B_{2}$ or the smallest element of
$B_{1}\triangle B_{2}$ belongs to $B_{1}$). Let $t\in[p]$ denote the index
satisfying $B\subseteq X^{t}$, and define
$\lambda(X)=(\omega^{t},c(B)+\lceil\frac{p(k-1)}{p-1}\rceil)$.

Observe that $\lambda$ returns pairs in ${\mathbb{Z}}_{p}\times[s]$ for

$s=m+\Big{\lceil}\frac{p(k-1)}{p-1}\Big{\rceil}=\Big{\lfloor}\frac{n-p(k-1)-1}{p-1}\Big{\rfloor}+\Big{\lceil}\frac{p(k-1)}{p-1}\Big{\rceil}=\frac{n-1}{p-1},$

where in the last equality we use the fact that $p-1$ divides $n-1$. We claim
that the function $\lambda$ is ${\mathbb{Z}}_{p}$-equivariant. This indeed
follows by considering the two cases in the definition of $\lambda$, using the
observation that for all
$X\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}$ and $t\in[p]$, it
holds that $\mathop{\mathrm{alt}}(X)=\mathop{\mathrm{alt}}(\omega^{t}X)$. It
can be verified that given a Boolean circuit that represents the coloring $c$,
it is possible to construct in polynomial time a Boolean circuit that
represents the function $\lambda$.

To prove the correctness of the reduction, consider a solution for the
produced instance of ${\mathbb{Z}}_{p}\textsc{-Tucker}$, that is, a chain of
$p$ signed sets $X_{1}\preceq X_{2}\preceq\cdots\preceq
X_{p}\in({\mathbb{Z}}_{p}\cup\\{0\\})^{n}\setminus\\{0\\}^{n}$ for which there
exist a permutation $\pi$ of $[p]$ and an $\ell\in[s]$, such that
$\lambda(X_{t})=(\omega^{\pi(t)},\ell)$ for all $t\in[p]$. We first claim that
$\ell>\lceil\frac{p(k-1)}{p-1}\rceil$. To see this, suppose for contradiction
that $\ell\leq\lceil\frac{p(k-1)}{p-1}\rceil$, and observe that the definition
of $\lambda$ implies that
$\ell=\lceil\frac{\mathop{\mathrm{alt}}(X_{t})}{p-1}\rceil$ for all $t\in[p]$.
It follows that some indices $t_{1}<t_{2}\in[p]$ satisfy that
$\mathop{\mathrm{alt}}(X_{t_{1}})=\mathop{\mathrm{alt}}(X_{t_{2}})$. However,
by $X_{t_{1}}\preceq X_{t_{2}}$, a longest alternating subsequence of nonzero
terms of $X_{t_{1}}$ is also a subsequence of $X_{t_{2}}$. This implies that
the first nonzero elements in $X_{t_{1}}$ and $X_{t_{2}}$ are equal, in
contradiction to the fact that
$\lambda_{1}(X_{t_{1}})\neq\lambda_{1}(X_{t_{2}})$.

Finally, using $\ell>\lceil\frac{p(k-1)}{p-1}\rceil$, the definition of
$\lambda$ implies that for every $t\in[p]$, there exists a subset of
$X_{t}^{\pi(t)}$ that belongs to $\binom{[n]}{k}_{\widetilde{\mathrm{stab}}}$.
For each $t\in[p]$, let $B_{t}$ denote the minimal subset of $X_{t}^{\pi(t)}$
that belongs to $\binom{[n]}{k}_{\widetilde{\mathrm{stab}}}$. By the
definition of $\lambda$, we have
$\ell=c(B_{t})+\lceil\frac{p(k-1)}{p-1}\rceil$ for all $t\in[p]$. For any
$t_{1}<t_{2}\in[p]$, the fact that $X_{t_{1}}\preceq X_{t_{2}}$ implies that
$B_{t_{1}}$ and $B_{t_{2}}$ are disjoint. It thus follows that the sets
$B_{1},\ldots,B_{p}$ form a monochromatic hyperedge of the coloring $c$ of
$K^{p}(n,k)_{\widetilde{\mathrm{stab}}}$. It can be verified that this
monochromatic hyperedge can be found in polynomial time given the signed sets
$X_{1},X_{2},\ldots,X_{p}$, so we are done.

By combining Theorem 5.2 with Theorem 5.7, the proof of Theorem 1.5 is
completed.

###  5.3 Limitations on the Complexity of $\textsc{Kneser}^{r}$ Problems

We next show that the results from the previous section imply limitations on
the complexity of variants of the $\textsc{Kneser}^{r}$ problem, restricted to
colorings with a bounded number of colors. We start with the following simple
lemma, which says that the $\textsc{Kneser}^{r}({\cal F},m)$ problem does not
become easier when $r$ increases.

######  Lemma 5.8.

Let $r_{1}\leq r_{2}$ be integers, let ${\cal F}=({\cal
F}_{\alpha})_{\alpha\in{\cal A}}$ be a sequence of set families, and let
$m:{\cal A}\rightarrow\mathbb{N}$ be a function such that
$m(\alpha)<\chi(K^{r_{2}}({\cal F}_{\alpha}))$ for all $\alpha\in{\cal A}$.
Then, $\textsc{Kneser}^{r_{1}}({\cal F},m)$ is polynomial-time reducible to
$\textsc{Kneser}^{r_{2}}({\cal F},m)$.

  * Proof:

Fix two integers $r_{1}\leq r_{2}$. Consider an instance of the
$\textsc{Kneser}^{r_{1}}({\cal F},m)$ problem, that is, an element
$\alpha\in{\cal A}$ and a Boolean circuit that represents a coloring of ${\cal
F}_{\alpha}$ with $m(\alpha)$ colors. We simply apply the identity reduction
to the $\textsc{Kneser}^{r_{2}}({\cal F},m)$ problem. A solution for the
obtained instance of $\textsc{Kneser}^{r_{2}}({\cal F},m)$, whose existence
follows by $m(\alpha)<\chi(K^{r_{2}}({\cal F}_{\alpha}))$, is a collection of
$r_{2}$ pairwise disjoint sets of ${\cal F}_{\alpha}$ with the same color. By
$r_{1}\leq r_{2}$, any $r_{1}$ sets from this collection form a solution for
the same input as an instance of $\textsc{Kneser}^{r_{1}}({\cal F},m)$. The
correctness of the reduction follows.

By combining Lemma 5.8 with Theorem 1.4, we obtain the following result.

######  Theorem 5.9.

For every integer $r$ and for every prime $p$ such that $r\leq p$,
$\textsc{Kneser}^{r}({\cal F}^{(p)},\lfloor\frac{n-p(k-1)-1}{p-1}\rfloor)$
lies in $\mathsf{PPA}\textsc{-}p$.

  * Proof:

Fix an integer $r$ and a prime $p$ such that $r\leq p$. Put
$m(n,k)=\lfloor\frac{n-p(k-1)-1}{p-1}\rfloor$, and apply Lemma 5.8 to obtain
that $\textsc{Kneser}^{r}({\cal F}^{(p)},m)$ is polynomial-time reducible to
$\textsc{Kneser}^{p}({\cal F}^{(p)},m)$. The latter coincides with the
$\textsc{Kneser}^{p}$ problem, which, by Theorem 1.4, lies in
$\mathsf{PPA}\textsc{-}p$. It thus follows that $\textsc{Kneser}^{r}({\cal
F}^{(p)},m)$ lies in $\mathsf{PPA}\textsc{-}p$, as required.

Theorem 5.9 yields, for any integer $r$, a limitation on the complexity of the
$\textsc{Kneser}^{r}$ problem, restricted to colorings with a bounded number
of colors. For example, consider the Kneser problem, which asks to find a
monochromatic edge in a graph $K(n,k)$ colored with $n-2k+1$ colors, and
recall that it lies in $\mathsf{PPA}$. By Theorem 5.9, applied with $r=2$ and
$p=3$, the $\textsc{Kneser}(n,k,\lfloor\frac{n-3k+2}{2}\rfloor)$ problem,
which asks to find a monochromatic edge in a graph $K(n,k)$ colored with only
$\lfloor\frac{n-3k+2}{2}\rfloor$ colors, lies in $\mathsf{PPA}\textsc{-}3$.
This implies that the latter problem is not $\mathsf{PPA}$-hard, unless
$\mathsf{PPA}\subseteq\mathsf{PPA}\textsc{-}3$. We next present analogue
consequences for the Schrijver problem.

We need the following simple lemma.

######  Lemma 5.10.

For every integer $r$,
$\textsc{Kneser}_{\mathrm{stab}}^{r}(n,k,\lfloor\frac{n-rk}{r-1}\rfloor)$ is
polynomial-time reducible to
$\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{r}$.

  * Proof:

For an integer $r$, consider an instance of
$\textsc{Kneser}_{\mathrm{stab}}^{r}(n,k,\lfloor\frac{n-rk}{r-1}\rfloor)$,
that is, integers $n$ and $k$ with $n\geq r\cdot k$ along with a coloring
$c:\binom{[n]}{k}_{\mathrm{stab}}\rightarrow[m]$ of the vertices of
$K^{r}(n,k)_{\mathrm{stab}}$ where $m=\lfloor\frac{n-rk}{r-1}\rfloor$. We
define a coloring
$c^{\prime}:{\binom{[n]}{k}}_{\widetilde{\mathrm{stab}}}\rightarrow[m+1]$ of
the vertices of ${K^{r}(n,k)}_{\widetilde{\mathrm{stab}}}$ as follows. For
every $A\in\binom{[n]}{k}_{\widetilde{\mathrm{stab}}}$, if $n\in A$ then
$c^{\prime}(A)=m+1$. Otherwise, it holds that
$A\in\binom{[n]}{k}_{\mathrm{stab}}$, and we define
$c^{\prime}(A)=c(A)\in[m]$. Note that the number of colors used by
$c^{\prime}$ is $m+1=\lfloor\frac{n-r(k-1)-1}{r-1}\rfloor$, as needed for an
instance of the $\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{r}$ problem.
Notice that given a Boolean circuit that represents the coloring $c$, it is
possible to construct in polynomial time a Boolean circuit that represents the
coloring $c^{\prime}$.

For correctness, consider a solution for the produced
$\textsc{Kneser}_{\widetilde{\mathrm{stab}}}^{r}$ instance, that is, a
monochromatic hyperedge of the coloring $c^{\prime}$ of
${K^{r}(n,k)}_{\widetilde{\mathrm{stab}}}$. By the definition of $c^{\prime}$,
the vertices colored $m+1$ are pairwise intersecting, hence the vertices of
the monochromatic hyperedge are not colored $m+1$, and thus do not include the
element $n$. Since an almost stable subset of $[n]$ that does not include $n$
is stable, this is a monochromatic hyperedge of the coloring $c$ of
$K^{r}(n,k)_{\mathrm{stab}}$ and thus a solution for the given instance of
$\textsc{Kneser}_{\mathrm{stab}}^{r}(n,k,\lfloor\frac{n-rk}{r-1}\rfloor)$, so
we are done.

By combining Lemma 5.10 with Theorem 1.5, we derive the following.

######  Corollary 5.11.

For every prime $p$, the
$\textsc{Kneser}_{\mathrm{stab}}^{p}(n,k,\lfloor\frac{n-pk}{p-1}\rfloor)$
problem lies in $\mathsf{PPA}\textsc{-}p$.

We further derive the following corollary.

######  Corollary 5.12.

The $\textsc{Schrijver}(n,k,\lfloor\frac{n-3k}{2}\rfloor)$ problem lies in
$\mathsf{PPA}\textsc{-}3$.

  * Proof:

Put $m(n,k)=\lfloor\frac{n-3k}{2}\rfloor$. By Lemma 5.8, the
$\textsc{Schrijver}(n,k,m)$ problem, which can be written as
$\textsc{Kneser}_{\mathrm{stab}}(n,k,m)$, is polynomial-time reducible to
$\textsc{Kneser}_{\mathrm{stab}}^{3}(n,k,m)$. By Corollary 5.11, the latter
lies in $\mathsf{PPA}\textsc{-}3$. It thus follows that
$\textsc{Schrijver}(n,k,m)$ lies in $\mathsf{PPA}\textsc{-}3$ as well.

We finally state the following consequence of Corollary 5.12 regarding the
$\textsc{Schrijver}(n,k,m)$ problem with the function $m(n,k)=\lfloor
n/2\rfloor-2k+1$ considered in [24]. We use here the fact that for all
integers $n$ and $k\geq 2$, it holds that $\lfloor
n/2\rfloor-2k+1\leq\lfloor\frac{n-3k}{2}\rfloor$.

######  Corollary 5.13.

The $\textsc{Schrijver}(n,k,\lfloor n/2\rfloor-2k+1)$ problem lies in
$\mathsf{PPA}\textsc{-}3$.

## Acknowledgments

We are grateful to Aris Filos-Ratsikas for a fruitful discussion and for a
clarification on [9] and to the anonymous reviewers for their useful comments.

## References

  * [1] M. Alishahi and H. Hajiabolhassan.  On the chromatic number of general Kneser hypergraphs.  J. Comb. Theory, Ser. B, 115:186–209, 2015.
  * [2] N. Alon.  Splitting necklaces.  Adv. Math., 63(3):247–253, 1987.
  * [3] N. Alon, P. Frankl, and L. Lovász.  The chromatic number of Kneser hypergraphs.  Trans. Amer. Math. Soc., 298(1):359–370, 1986.
  * [4] N. Alon and A. Graur.  Efficient splitting of necklaces.  In Proc. of the 48th International Colloquium on Automata, Languages, and Programming, (ICALP’21), pages 14:1–14:17, 2021.
  * [5] J. Aslam, S. Chen, E. Coldren, F. Frick, and L. Setiabrata.  On the generalized Erdös-Kneser conjecture: Proofs and reductions.  J. Comb. Theory, Ser. B, 135:227–237, 2019.
  * [6] I. Bárány, S. B. Shlosman, and A. Szücs.  On a topological generalization of a theorem of Tverberg.  J. London Math. Soc., s2-23(1):158–164, 1981.
  * [7] K. Borsuk.  Drei Sätze über die $n$-dimensionale euklidische Sphäre.  Fundamenta Mathematicae, 20(1):177–190, 1933.
  * [8] A. Deligkas, J. Fearnley, A. Hollender, and T. Melissourgos.  Constant inapproximability for PPA.  In Proc. of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC’22), pages 1010–1023, 2022.
  * [9] A. Deligkas, A. Filos-Ratsikas, and A. Hollender.  Two’s company, three’s a crowd: Consensus-halving for a constant number of agents.  Artif. Intell., 313(C):103784, 2022.  Preliminary version in EC’21.
  * [10] X. Deng, Z. Feng, and R. Kulkarni.  Octahedral Tucker is PPA-complete.  Electronic Colloquium on Computational Complexity (ECCC), 24:118, 2017.
  * [11] A. Dold.  Simple proofs of some Borsuk–Ulam results.  Contemp. Math., 19:65–69, 1983.
  * [12] V. Dol’nikov.  Transversals of families of sets.  In Studies in the theory of functions of several real variables (Russian), volume 29, pages 30–36. Yaroslavl’, 1981.
  * [13] P. Erdös.  Problems and results in combinatorial analysis.  Colloq. int. Teorie comb., Roma 1973, pages 3–17, 1976.
  * [14] A. Filos-Ratsikas and P. W. Goldberg.  Consensus halving is PPA-complete.  In Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18), pages 51–64, 2018.
  * [15] A. Filos-Ratsikas and P. W. Goldberg.  The complexity of splitting necklaces and bisecting ham sandwiches.  In Proc. of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC’19), pages 638–649, 2019.
  * [16] A. Filos-Ratsikas, A. Hollender, K. Sotiraki, and M. Zampetakis.  A topological characterization of modulo-_p_ arguments and implications for necklace splitting.  In Proc. of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA’21), pages 2615–2634, 2021.
  * [17] A. Filos-Ratsikas, A. Hollender, K. Sotiraki, and M. Zampetakis.  Consensus-halving: Does it ever get easier?  SIAM J. Comput., 52(2):412–451, 2023.  Preliminary version in EC’20.
  * [18] F. Frick.  Chromatic numbers of stable Kneser hypergraphs via topological Tverberg-type theorems.  Int. Math. Res. Not., 2020(13):4037–4061, 2020.
  * [19] P. Goldberg and J. Li.  Consensus division in an arbitrary ratio.  In Proc. of the 14th Innovations in Theoretical Computer Science Conference (ITCS’23), pages 57:1–57:18, 2023.
  * [20] P. W. Goldberg, A. Hollender, A. Igarashi, P. Manurangsi, and W. Suksompong.  Consensus halving for sets of items.  Math. Oper. Res., 47(4):2547–3399, 2022.  Preliminary version in WINE’20.
  * [21] M. Göös, P. Kamath, K. Sotiraki, and M. Zampetakis.  On the complexity of modulo-$q$ arguments and the Chevalley–Warning theorem.  In Proc. of the 35th Computational Complexity Conference (CCC’20), pages 19:1–19:42, 2020.
  * [22] I. Haviv.  The complexity of finding fair independent sets in cycles.  Comput. Complex., 31(2):14, 2022.  Preliminary version in ITCS’21.
  * [23] I. Haviv.  A fixed-parameter algorithm for the Kneser problem.  In Proc. of the 49th International Colloquium on Automata, Languages, and Programming (ICALP’22), pages 72:1–72:18, 2022.
  * [24] I. Haviv.  On finding constrained independent sets in cycles.  In Proc. of the 50th International Colloquium on Automata, Languages, and Programming (ICALP’23), pages 73:1–73:16, 2023.
  * [25] C. R. Hobby and J. R. Rice.  A moment problem in ${L}_{1}$ approximation.  Proc. Amer. Math. Soc., 16(4):665–670, 1965.
  * [26] A. Hollender.  The classes PPA-_k_ : Existence from arguments modulo _k_.  Theor. Comput. Sci., 885:15–29, 2021.  Preliminary version in WINE’19.
  * [27] M. Kneser.  Aufgabe 360.  Jahresbericht der Deutschen Mathematiker-Vereinigung, 58(2):27, 1955\.
  * [28] I. Kriz.  Equivariant cohomology and lower bounds for chromatic numbers.  Trans. Amer. Math. Soc., 333(2):567–577, 1992.
  * [29] L. Lovász.  Kneser’s conjecture, chromatic number, and homotopy.  J. Comb. Theory, Ser. A, 25(3):319–324, 1978.
  * [30] J. Matoušek.  A combinatorial proof of Kneser’s conjecture.  Combinatorica, 24(1):163–170, 2004.
  * [31] N. Megiddo and C. H. Papadimitriou.  On total functions, existence theorems and computational complexity.  Theor. Comput. Sci., 81(2):317–324, 1991.
  * [32] F. Meunier.  The chromatic number of almost stable Kneser hypergraphs.  J. Comb. Theory, Ser. A, 118(6):1820–1828, 2011.
  * [33] C. H. Papadimitriou.  On the complexity of the parity argument and other inefficient proofs of existence.  J. Comput. Syst. Sci., 48(3):498–532, 1994.
  * [34] A. Schrijver.  Vertex-critical subgraphs of Kneser graphs.  Nieuw Arch. Wiskd., 26(3):454–461, 1978.
  * [35] F. W. Simmons and F. E. Su.  Consensus-halving via theorems of Borsuk-Ulam and Tucker.  Math. Soc. Sci., 45(1):15–25, 2003.
  * [36] G. M. Ziegler.  Generalized Kneser coloring theorems with combinatorial proofs.  Invent. Math., 147(3):671–691, 2002.