# A Fixed-Parameter Algorithm for the Schrijver Problem

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

The Schrijver graph $S(n,k)$ is defined for integers $n$ and $k$ with $n\geq
2k$ as the graph whose vertices are all the $k$-subsets of
$\\{1,2,\ldots,n\\}$ that do not include two consecutive elements modulo $n$,
where two such sets are adjacent if they are disjoint. A result of Schrijver
asserts that the chromatic number of $S(n,k)$ is $n-2k+2$ (Nieuw Arch. Wiskd.,
1978). In the computational Schrijver problem, we are given an access to a
coloring of the vertices of $S(n,k)$ with $n-2k+1$ colors, and the goal is to
find a monochromatic edge. The Schrijver problem is known to be complete in
the complexity class $\mathsf{PPA}$. We prove that it can be solved by a
randomized algorithm with running time $n^{O(1)}\cdot k^{O(k)}$, hence it is
fixed-parameter tractable with respect to the parameter $k$.

##  1 Introduction

The Kneser graph $K(n,k)$ is defined for integers $n$ and $k$ with $n\geq 2k$
as the graph whose vertices are all the $k$-subsets of
$[n]=\\{1,2,\ldots,n\\}$ where two such sets are adjacent if they are
disjoint. In 1955, Kneser [19] observed that the chromatic number of the graph
$K(n,k)$ satisfies $\chi(K(n,k))\leq n-2k+2$, that is, there exists a proper
coloring of its vertices with $n-2k+2$ colors, and conjectured that this upper
bound on the chromatic number is tight. The conjecture was proved in 1978 by
Lovász [20] as an application of the Borsuk-Ulam theorem from algebraic
topology [2]. Following this result, topological methods have become a
powerful tool in combinatorics, discrete geometry, and theoretical computer
science (see, e.g., [22]).

The Schrijver graph $S(n,k)$ is defined as the subgraph of $K(n,k)$ induced by
the collection of all $k$-subsets of $[n]$ that do not include two consecutive
elements modulo $n$ (i.e., the $k$-subsets $A\subseteq[n]$ such that if $i\in
A$ then $i+1\notin A$, and if $n\in A$ then $1\notin A$). Schrijver proved in
[26], strengthening Lovász’s result, that the chromatic number of $S(n,k)$ is
equal to that of $K(n,k)$. His proof technique relies on a proof of Kneser’s
conjecture due to Bárány [1], which was obtained soon after the one of Lovász
and combined the topological Borsuk-Ulam theorem with a lemma of Gale [12]. It
was further proved in [26] that $S(n,k)$ is vertex-critical, that is, the
chromatic number of any proper induced subgraph of $S(n,k)$ is strictly
smaller than that of $S(n,k)$.

In the computational Kneser and Schrijver problems, we are given an access to
a coloring with $n-2k+1$ colors of the vertices of $K(n,k)$ and $S(n,k)$
respectively, and the goal is to find a monochromatic edge, i.e., two vertices
with the same color that correspond to disjoint sets. Since the number of
colors used by the input coloring is strictly smaller than the chromatic
number of the graph [20, 26], it follows that every instance of these problems
has a solution. However, the topological argument behind the lower bound on
the chromatic number is not constructive, in the sense that it does not
suggest an efficient algorithm for finding a monochromatic edge. By an
efficient algorithm we mean that its running time is polynomial in $n$,
whereas the number of vertices might be exponentially larger. Hence, it is
natural to assume that the input coloring is given as an access to an oracle
that given a vertex of the graph returns its color. The input can also be
given by some succinct representation, e.g., a Boolean circuit that computes
the color of any given vertex.

In recent years, it has been shown that the complexity class $\mathsf{PPA}$
perfectly captures the complexity of several total search problems for which
the existence of the solution relies on the Borsuk-Ulam theorem. This
complexity class belongs to a family of classes that were introduced in 1994
by Papadimitriou [25] in the attempt to characterize the mathematical
arguments that lie behind the existence of solutions to search problems of
$\mathsf{TFNP}$. The complexity class $\mathsf{TFNP}$, introduced in [24], is
the class of total search problems in $\mathsf{NP}$, namely, the search
problems in which a solution is guaranteed to exist and can be verified in
polynomial running time. Papadimitriou has introduced in [25] several
subclasses of $\mathsf{TFNP}$, each of which consists of the total search
problems that can be efficiently reduced to a problem that represents some
mathematical argument. One of those subclasses was $\mathsf{PPA}$ (Polynomial
Parity Argument) that corresponds to the fact that every (undirected) graph
with maximum degree $2$ that has a vertex of degree $1$ must have another
degree $1$ vertex. Hence, $\mathsf{PPA}$ is the class of all problems in
$\mathsf{TFNP}$ that can be efficiently reduced to the Leaf problem, in which
given a succinct representation of a graph with maximum degree $2$ and given a
vertex of degree $1$ in the graph, the goal is to find another such vertex.

A prominent example of a $\mathsf{PPA}$-complete problem whose totality is
related to the Borsuk-Ulam theorem is the one associated with the Consensus
Halving theorem [17, 27]. The $\mathsf{PPA}$-completeness of the problem was
proved for an inverse-polynomial precision parameter by Filos-Ratsikas and
Goldberg [7, 8], and this was improved to a constant precision parameter in a
recent work of Deligkas, Fearnley, Hollender, and Melissourgos [4]. The
hardness of the Consensus Halving problem was used to derive the
$\mathsf{PPA}$-completeness of several other problems. This includes the
Splitting Necklace problem with two thieves, the Discrete Sandwich problem [7,
8], the Fair Independent Set in Cycle problem, and the aforementioned
Schrijver problem (with the input coloring given as a Boolean circuit) [14].
As for the Kneser problem, the question of whether it is
$\mathsf{PPA}$-complete was proposed by Deng, Feng, and Kulkarni [5]. It is
interesting to mention that this question is motivated by connections of the
Kneser problem to a resource allocation problem called Agreeable Set, that was
introduced by Manurangsi and Suksompong [21] and further studied in [13, 15].
It is also motivated by the extension of the Kneser problem to Kneser
hypergraphs, for which the complexity question was raised by Filos-Ratsikas,
Hollender, Sotiraki, and Zampetakis [9].

In the area of parameterized complexity, a problem whose instances involve a
parameter $k$ is said to be fixed-parameter tractable with respect to $k$ if
it admits an algorithm whose running time is bounded by a polynomial in the
input size multiplied by an arbitrary function of $k$ (see, e.g., [3]).
Adopting this notion to our setting, where the instance is not given
explicitly but as an oracle access, we say that an algorithm for the Kneser
and Schrijver problems is fixed-parameter with respect to $k$ if its running
time on an input coloring of, respectively, $K(n,k)$ and $S(n,k)$ is bounded
by $n^{O(1)}\cdot f(k)$ for some function $f$. In a recent work of the author
[15], it was shown that the Kneser problem is fixed-parameter tractable with
respect to the parameter $k$. More specifically, it was shown there that there
exists a randomized algorithm that solves the Kneser problem on an input
coloring of a Kneser graph $K(n,k)$ in running time $n^{O(1)}\cdot k^{O(k)}$.

###  1.1 Our Contribution

In the current work, we prove that the Schrijver problem on graphs $S(n,k)$ is
fixed-parameter tractable with respect to the parameter $k$.

######  Theorem 1.1.

There exists a randomized algorithm that given integers $n$ and $k$ with
$n\geq 2k$ and an oracle access to a coloring of the vertices of the Schrijver
graph $S(n,k)$ with $n-2k+1$ colors, runs in time $n^{O(1)}\cdot k^{O(k)}$ and
returns a monochromatic edge with high probability.

A few remarks about Theorem 1.1 are in order here.

  * •

The algorithmic task of finding a monochromatic edge in the Schrijver graph
$S(n,k)$ given a coloring of its vertices with $n-2k+1$ colors is at least as
hard as that of finding a monochromatic edge in the Kneser graph $K(n,k)$
given such a coloring. Indeed, $S(n,k)$ is an induced subgraph of $K(n,k)$
with the same chromatic number. Therefore, the Kneser problem can be solved by
applying an algorithm for the Schrijver problem to the restriction of a
coloring of a Kneser graph to its Schrijver subgraph. This implies that
Theorem 1.1 strengthens the fixed-parameter tractability result of [15], and
yet achieves the same asymptotic dependence on $k$ in the running time.

  * •

In contrast to the current situation of the Kneser problem [5], the Schrijver
problem is known to be $\mathsf{PPA}$-complete [14]. Hence, the study of its
fixed-parameter tractability is motivated in a stronger sense.

  * •

As mentioned earlier, the Schrijver graph $S(n,k)$ was shown in [26] to be
vertex-critical. It follows that for every vertex $A$ of the graph $S(n,k)$,
there exists a coloring of its vertices with $n-2k+1$ colors, for which only
edges that are incident with $A$ are monochromatic. An algorithm for the
Schrijver problem, while running on such an input coloring, must be able to
find an edge that is incident with this specified vertex $A$. Nevertheless,
the algorithm given in Theorem 1.1 manages to do so in running time much
smaller than the number of vertices, provided that $n$ is sufficiently larger
than $k$.

  * •

Borrowing the terminology of the area of parameterized complexity, our
algorithm for the Schrijver problem can be viewed as a randomized polynomial
Turing kernelization algorithm for the problem (see, e.g., [10, Chapter 22]).
Namely, the problem of finding a monochromatic edge in a Schrijver graph
$S(n,k)$ can essentially be reduced by a randomized efficient algorithm to
finding a monochromatic edge in a Schrijver graph $S(n^{\prime},k)$ for
$n^{\prime}=O(k^{4})$. This aspect of the algorithm is common to the algorithm
for the Kneser problem given in [15] (see [15, Section 3.4] for the details).

Our algorithm for the Schrijver problem extends the approach developed in [15]
for the Kneser problem. The adaptation to the Schrijver problem relies on
structural properties of induced subgraphs of Schrijver graphs (see Section
3). Their proofs involve some ideas that were applied in the context of Frege
propositional proof systems by Istrate, Bonchis, and Craciun [18]. In the
remainder of this section, we give an overview of the proof of Theorem 1.1.

###  1.2 Proof Overview

Our algorithm for the Schrijver problem is based on the strategy developed in
[15] for the Kneser problem. We start by describing the algorithm of [15] for
the Kneser problem and then present the modification in the algorithm and in
its analysis needed for the Schrijver problem.

Suppose that we are given an oracle access to a coloring of the vertices of
the Kneser graph $K(n,k)$ with $n-2k+1$ colors. In order to find a
monochromatic edge in the graph, we use an efficient algorithm, called
‘element elimination’, that reduces our problem to that of finding a
monochromatic edge in a subgraph of $K(n,k)$ isomorphic to $K(n-1,k)$ whose
vertices are colored by $n-2k$ colors. Since the chromatic number of the
latter is $n-2k+1$ [20], such a coloring is guaranteed to have a monochromatic
edge in the subgraph. By repeatedly applying this algorithm, we obtain a
coloring with $n^{\prime}-2k+1$ colors of a subgraph of $K(n,k)$ isomorphic to
$K(n^{\prime},k)$. When the size $n^{\prime}$ of the ground set is
sufficiently small and depends only on $k$, a brute force algorithm that
queries the oracle for the colors of all vertices allows us to find a
monochromatic edge in running time that essentially depends only on $k$.

We turn to describe now the ‘element elimination’ algorithm. This algorithm
picks uniformly and independently polynomially many vertices of the graph
$K(n,k)$ and queries the oracle for their colors. If the random samples
include two vertices that form a monochromatic edge in the graph, then this
edge is returned and we are done. Otherwise, the algorithm identifies a color
$i\in[n-2k+1]$ that appears on a largest number of vertices among the random
samples and an element $j\in[n]$ that is particularly popular on the sampled
vertices colored $i$ (say, that belongs to a constant fraction of them). The
‘element elimination’ algorithm suggests to remove the element $j$ from the
ground set, and to keep looking for a monochromatic edge in the subgraph
induced by the $k$-subsets of $[n]\setminus\\{j\\}$.

The correctness of the ‘element elimination’ algorithm for Kneser graphs
relies on structural properties of intersecting families of $k$-subsets of
$[n]$. A stability result of Hilton and Milner [16] for the celebrated Erdös-
Ko-Rado theorem [6] says that any sufficiently large intersecting family of
$k$-subsets of $[n]$ satisfies that all of its members share a common element.
This is used in [15], combined with an idea of Frankl and Kupavskii [11], to
show that as long as $n\geq\Omega(k^{4})$, if a large color class of the input
coloring does not have an element that is quite popular on its members, then
the sampled vertices include with high probability a monochromatic edge.
Otherwise, for every color $i$ of a large color class there exists some
element $j$ that is popular on its vertices, and the algorithm finds such a
pair $(i,j)$ with high probability. If this element $j$ belongs to all the
vertices colored $i$, then the restriction of the input coloring to the
$k$-subsets of $[n]\setminus\\{j\\}$ is a coloring with $n-2k$ colors of a
graph isomorphic to $K(n-1,k)$, as required.

However, although the element $j$ belongs to a significant fraction of the
vertices colored $i$, the coloring might use the color $i$ for vertices that
do not include the element $j$. This might lead to an elimination of the
element $j$ while the restriction of the coloring to the $k$-subsets of
$[n]\setminus\\{j\\}$ still uses the color $i$, hence the corresponding
subgraph is not guaranteed to have a monochromatic edge. This situation is
handled in [15] by showing that every vertex colored $i$ that does not include
$j$ is disjoint from a non-negligible fraction of the vertices colored $i$.
Therefore, in case that the brute force algorithm that is applied to the
subgraph obtained after all iterations of the ‘element elimination’ algorithm
finds a vertex $A$ colored by a color $i$ that is associated with an
eliminated element $j$, we pick uniformly at random vertices from the subgraph
of the corresponding iteration and with high probability find a neighbor of
$A$ colored $i$ and thus a monochromatic edge. This completes the high-level
description of the algorithm for the Kneser problem from [15].

Our algorithm for finding a monochromatic edge in a Schrijver graph $S(n,k)$
given a coloring of its vertices with $n-2k+1$ colors also uses an ‘element
elimination’ algorithm as a main ingredient. Observe, however, that whenever
an element $j\in[n]$ is eliminated, the subgraph induced by the $k$-subsets of
$[n]\setminus\\{j\\}$ is not isomorphic to a Schrijver graph. We therefore
consider the subgraph of $S(n,k)$ that corresponds to the cyclic ordering of
the elements of $[n]\setminus\\{j\\}$ which is induced by the cyclic ordering
of the elements of $[n]$ (where $j-1$ precedes $j+1$). This allows the
algorithm to proceed by looking for a monochromatic edge in a graph isomorphic
to $S(n-1,k)$. As before, the eliminated element is chosen as an element
$j\in[n]$ that is quite popular on the vertices colored by a color $i$ that
corresponds to a large color class of the input coloring. The pair of the
color $i$ and the element $j$ is identified using polynomially many vertices
chosen uniformly at random from the vertex set of $S(n,k)$.

The main contribution of the current work lies in the analysis of the ‘element
elimination’ algorithm for Schrijver graphs. Consider first the case where the
input coloring has a large color class that does not have a popular element in
its members. For this case we prove that the selected random vertices include
a monochromatic edge with high probability. In contrast to the analysis used
for Kneser graphs, here we cannot apply the Hilton-Milner theorem [16] that
deals with intersecting families of general $k$-subsets of $[n]$. We overcome
this issue using a Hilton-Milner-type result for stable sets, i.e., for
vertices of the Schrijver graph, borrowing ideas that were applied by Istrate,
Bonchis, and Craciun [18] in the context of Frege propositional proof systems
(see Lemma 3.5). Note that this can be interpreted as an approximate stability
result for the analogue of the Erdös-Ko-Rado theorem for stable sets that was
proved in 2003 by Talbot [28]. The Hilton-Milner-type result is combined with
the approach of [15] and with an idea of [11] to prove that if the vertices of
a large color class do not have a popular element, then a pair of vertices
chosen uniformly at random from $S(n,k)$ forms a monochromatic edge with a
non-negligible probability (see Lemma 3.6). Hence, picking a polynomial number
of them suffices to catch such an edge.

Consider next the case where every large color class of the input coloring has
a popular element. Here, the ‘element elimination’ algorithm identifies with
high probability a color $i$ of a large color class and an element $j$ that is
popular on its vertices. If all the vertices colored $i$ include $j$ then we
can safely look for a monochromatic edge in the subgraph of $S(n,k)$ induced
by the cyclic ordering of $[n]$ without the element $j$, as this means that
the size of the ground set and the number of colors are both reduced by $1$.
However, for the scenario where the color class of $i$ involves vertices $A$
that do not include $j$, we prove, as in [15], that such an $A$ is disjoint
from a random set from the color class of $i$ with a non-negligible
probability. Note that the analysis in this case again employs the ideas
applied by Istrate et al. [18] (see Lemma 3.8). Then, when such a set $A$ is
found by the algorithm, we can go back to the subgraph of the run of the
‘element elimination’ algorithm that identified the color of $A$ and find a
neighbor of $A$ from this color class using random samples.

###  1.3 Outline

The rest of the paper is organized as follows. In Section 2, we gather several
definitions and results that will be used throughout the paper. In Section 3,
we present and prove several structural results on induced subgraphs of
Schrijver graphs needed for the analysis of our algorithm. Finally, in Section
4, we present and analyze our randomized fixed-parameter algorithm for the
Schrijver problem and prove Theorem 1.1.

##  2 Preliminaries

###  2.1 Kneser and Schrijver Graphs

Consider the following definition.

######  Definition 2.1.

For a family ${\cal F}$ of non-empty sets, let $K({\cal F})$ denote the graph
on the vertex set ${\cal F}$ in which two vertices are adjacent if they
represent disjoint sets.

For a set $X$ and an integer $k$, let $\binom{X}{k}$ denote the family of all
$k$-subsets of $X$. Note that the Kneser graph $K(n,k)$ can be defined for
integers $n$ and $k$ with $n\geq 2k$ as the graph $K(\binom{[n]}{k})$.

A set $A\subseteq[n]$ is said to be stable if it does not include two
consecutive elements modulo $n$, that is, it forms an independent set in the
$n$-vertex cycle with the numbering from $1$ to $n$ along the cycle. For
integers $n$ and $k$ with $n\geq 2k$, let $\binom{[n]}{k}_{\mathrm{stab}}$
denote the collection of all stable $k$-subsets of $[n]$. The Schrijver graph
$S(n,k)$ is defined as the graph $K(\binom{[n]}{k}_{\mathrm{stab}})$.
Equivalently, it is the subgraph of $K(n,k)$ induced by the vertex set
$\binom{[n]}{k}_{\mathrm{stab}}$.

For a set $X\subseteq[n]$ consider the natural cyclic ordering of the elements
of $X$ induced by that of $[n]$, and let $\binom{X}{k}_{\mathrm{stab}}$ denote
the collection of all $k$-subsets of $X$ that do not include two consecutive
elements according to this ordering. More formally, letting
$j_{1}<j_{2}<\cdots<j_{|X|}$ denote the elements of $X$,
$\binom{X}{k}_{\mathrm{stab}}$ stands for the collection of all independent
sets of size $k$ in the cycle on the vertex set $X$ with the numbering
$j_{1},\ldots,j_{|X|}$ along the cycle. Note that
$\binom{X}{k}_{\mathrm{stab}}\subseteq\binom{X^{\prime}}{k}_{\mathrm{stab}}$
whenever $X\subseteq X^{\prime}\subseteq[n]$. Note further that the graph
$K(\binom{X}{k}_{\mathrm{stab}})$ is isomorphic to the Schrijver graph
$S(|X|,k)$.

The chromatic number of the graph $S(n,k)$ was determined by Schrijver [26],
strengthening a result of Lovász [20].

######  Theorem 2.2 ([26]).

For all integers $n$ and $k$ with $n\geq 2k$, $\chi(S(n,k))=n-2k+2$.

A family ${\cal F}\subseteq\binom{[n]}{k}$ of $k$-subsets of $[n]$ is called
intersecting if for every two sets $F_{1},F_{2}\in{\cal F}$ it holds that
$F_{1}\cap F_{2}\neq\emptyset$. Note that such a family forms an independent
set in the graph $K(n,k)$. If the members of ${\cal F}$ share a common
element, then we say that the intersecting family ${\cal F}$ is trivial.

The computational search problem associated with the Schrijver graph is
defined as follows.

######  Definition 2.3.

In the Schrijver problem, the input is a coloring
$c:\binom{[n]}{k}_{\mathrm{stab}}\rightarrow[n-2k+1]$ of the vertices of the
Schrijver graph $S(n,k)$ with $n-2k+1$ colors for integers $n$ and $k$ with
$n\geq 2k$, and the goal is to find a monochromatic edge.

The existence of a solution to every instance of the Schrijver problem follows
from Theorem 2.2. In our algorithm for the Schrijver problem, we consider the
black-box input model, where the input coloring is given as an oracle access
that for a vertex $A$ returns its color $c(A)$. This reflects the fact that
the algorithm does not rely on the representation of the input coloring.

###  2.2 Chernoff-Hoeffding Bound

We need the following concentration result (see, e.g., [23, Theorem 2.1]).

######  Theorem 2.4 (Chernoff-Hoeffding Bound).

Let $0<p<1$, let $X_{1},\ldots,X_{m}$ be $m$ independent binary random
variables satisfying ${\Pr\left[{X_{i}=1}\right]}=p$ and
${\Pr\left[{X_{i}=0}\right]}=1-p$ for all $i$, and put
$\overline{X}=\frac{1}{m}\cdot\sum_{i=1}^{m}{X_{i}}$. Then, for any $\mu\geq
0$,

${\Pr\left[{|\overline{X}-p|\geq\mu}\right]}\leq 2\cdot e^{-2m\mu^{2}}.$

##  3 Induced Subgraphs of Schrijver Graphs

In this section, we provide a couple of lemmas on induced subgraphs of
Schrijver graphs that will play a central role in the analysis of our
algorithm for the Schrijver problem. We start with some preliminary claims
related to counting stable sets.

###  3.1 Counting Stable Sets

We need the following simple claim.

######  Claim 3.1.

For integers $k\geq 1$ and $n\geq 2k$, the number of $k$-subsets of $[n]$ with
no two consecutive elements (allowing both $1$ and $n$ to be in the subsets)
is $\binom{n-k+1}{k}$.

  * Proof:

Identify the subsets of $[n]$ with their characteristic vectors in
$\\{0,1\\}^{n}$, and in every such vector, interpret the zeros as balls and
the ones as separations between bins. It follows that every $k$-subset of
$[n]$ with no two consecutive elements corresponds to a partition of $n-k$
identical balls into $k+1$ bins, where all bins but the first and last are not
empty. The number of those partitions is equal to the number of partitions of
$n-2k+1$ identical balls into $k+1$ bins, which is $\binom{n-k+1}{k}$.

Using Claim 3.1, we derive the number of vertices in Schrijver graphs.

######  Claim 3.2.

For integers $k\geq 2$ and $n\geq 2k$, the number of vertices in $S(n,k)$ is
$\binom{n-k+1}{k}-\binom{n-k-1}{k-2}$.

  * Proof:

Recall that the vertex set $\binom{[n]}{k}_{\mathrm{stab}}$ of $S(n,k)$ is the
collection of all $k$-subsets of $[n]$ with no two consecutive elements modulo
$n$. By Claim 3.1, the number of $k$-subsets of $[n]$ with no two consecutive
elements (allowing both $1$ and $n$ to be in the subsets) is
$\binom{n-k+1}{k}$. To obtain the number of vertices of $S(n,k)$, one has to
subtract the number of $k$-subsets of $[n]$ with no two consecutive elements
that include both $1$ and $n$. The latter is equal to the number of
$(k-2)$-subsets of $[n-4]$ with no two consecutive elements, which by Claim
3.1 equals $\binom{n-k-1}{k-2}$, so we are done.

######  Remark 3.3.

We note that if $n\geq\alpha\cdot k$ for $\alpha\geq 2$, then the number of
vertices in $S(n,k)$ is at least

$\bigg{(}1-\frac{1}{(\alpha-1)^{2}}\bigg{)}\cdot\binom{n-k+1}{k}.$

To see this, notice that

$\displaystyle\binom{n-k-1}{k-2}$ $\displaystyle=$
$\displaystyle\frac{k\cdot(k-1)}{(n-k+1)\cdot(n-k)}\cdot\binom{n-k+1}{k}$
$\displaystyle\leq$
$\displaystyle\bigg{(}\frac{k}{n-k}\bigg{)}^{2}\cdot\binom{n-k+1}{k}\leq\frac{1}{(\alpha-1)^{2}}\cdot\binom{n-k+1}{k},$

which by Claim 3.2 implies the stated bound on the number of vertices in
$S(n,k)$.

The following claim employs an argument of Istrate, Bonchis, and Craciun [18].
We include its proof for completeness.

######  Claim 3.4.

For integers $k\geq 2$ and $n\geq 2k$ and for every two distinct integers
$a,b\in[n]$, the number of stable $k$-subsets $F$ of $[n]$ satisfying
$\\{a,b\\}\subseteq F$ is at most $\binom{n-k-2}{k-2}$.

  * Proof:

It is easy to see that the statement of the claim holds for $k=2$, hence we
assume from now on that $k\geq 3$. Suppose without loss of generality that
$a=1$. For an integer $b\in[n]\setminus\\{1\\}$, consider the stable
$k$-subsets $F$ of $[n]$ satisfying $\\{1,b\\}\subseteq F$.

For $b\in\\{2,n\\}$, there are no such sets, hence the required bound
trivially holds.

For $b\in\\{3,n-1\\}$, assume without loss of generality that $b=3$, and
observe that the desired sets $F$ have the form $F^{\prime}\cup\\{1,3\\}$,
where $F^{\prime}$ is a $(k-2)$-subset of $\\{5,\ldots,n-1\\}$ with no two
consecutive elements. In case that $n\geq 2k+1$, we have $n-5\geq
2\cdot(k-2)$, so using $k\geq 3$, we can apply Claim 3.1 to obtain that the
number of sets is

$\binom{(n-5)-(k-2)+1}{k-2}=\binom{n-k-2}{k-2},$

and therefore the required bound holds. For $n=2k$, notice that there is a
single $F^{\prime}$ as above, so the bound holds as well.

Similarly, for $b\in\\{4,n-2\\}$, assume without loss of generality that
$b=4$, for which the desired sets $F$ have the form $F^{\prime}\cup\\{1,4\\}$,
where $F^{\prime}$ is a $(k-2)$-subset of $\\{6,\ldots,n-1\\}$ with no two
consecutive elements. As before, for $n\geq 2k+2$, we can apply Claim 3.1 to
obtain that the number of sets is

$\binom{(n-6)-(k-2)+1}{k-2}=\binom{n-k-3}{k-2}\leq\binom{n-k-2}{k-2}.$

The bound also holds for $n\in\\{2k,2k+1\\}$, for which there is at most one
$F^{\prime}$ as above.

Otherwise, for $b\in\\{5,\ldots,n-3\\}$, the desired sets $F$ have the form
$F^{\prime}\cup\\{1,b\\}$, where $F^{\prime}$ is a $(k-2)$-subset of
$\\{3,\ldots,b-2\\}\cup\\{b+2,\ldots,n-1\\}$ with no two consecutive elements.
By shifting the elements of $F^{\prime}$ in the range $\\{3,\ldots,b-2\\}$ by
$2$, it follows that the number of those sets $F^{\prime}$ is equal to the
number of $(k-2)$-subsets of $\\{5,\ldots,n-1\\}$ with no two consecutive
elements and without the element $b+1$. As shown above (for $b=3$), the number
of these subsets, even without the requirement not to include $b+1$, does not
exceed the required bound, so we are done.

The following result stems from Claim 3.4 and can be viewed as an approximate
variant of the Hilton-Milner theorem of [16] for stable sets (see [18]).

######  Lemma 3.5.

For integers $k\geq 2$ and $n\geq 2k$, every non-trivial intersecting family
${\cal F}$ of stable $k$-subsets of $[n]$ satisfies $|{\cal F}|\leq
k^{2}\cdot\binom{n-k-2}{k-2}$.

  * Proof:

Let ${\cal F}$ be a non-trivial intersecting family of stable $k$-subsets of
$[n]$. Consider an arbitrary set $A=\\{a_{1},\ldots,a_{k}\\}$ in ${\cal F}$.
Since ${\cal F}$ is non-trivial, for every $t\in[k]$, there exists a set
$B_{t}\in{\cal F}$ satisfying $a_{t}\notin B_{t}$. Since ${\cal F}$ is
intersecting, every set in ${\cal F}$ intersects $A$, and therefore includes
the element $a_{t}$ for some $t\in[k]$. Such a set further intersects $B_{t}$,
hence it also includes some element $b\in B_{t}$ (which is different from
$a_{t}$). By Claim 3.4, the number of stable $k$-subsets of $[n]$ that include
both $a_{t}$ and $b$ does not exceed $\binom{n-k-2}{k-2}$. Since there are at
most $k^{2}$ ways to choose the elements $a_{t}$ and $b$, this implies that
$|{\cal F}|\leq k^{2}\cdot\binom{n-k-2}{k-2}$, as required.

###  3.2 Induced Subgraphs of Schrijver Graphs

We are ready to prove the lemmas that lie at the heart of the analysis of our
algorithm for the Schrijver problem. The first lemma, given below, shows that
in a large induced subgraph of the Schrijver graph $S(n,k)$ whose vertices do
not have a popular element, a random pair of vertices forms an edge with a
non-negligible probability.

######  Lemma 3.6.

For integers $k\geq 2$ and $n\geq 2k$, let ${\cal F}$ be a family of stable
$k$-subsets of $[n]$ whose size satisfies $|{\cal F}|\geq
k^{2}\cdot\binom{n-k-2}{k-2}$ and let $\gamma\in(0,1]$. Suppose that every
element of $[n]$ belongs to at most $\gamma$ fraction of the sets of ${\cal
F}$. Then, the probability that two random sets chosen uniformly and
independently from ${\cal F}$ are adjacent in $K({\cal F})$ is at least

$\frac{1}{2}\cdot\Biggr{(}1-\gamma-\frac{k^{2}}{|{\cal
F}|}\cdot\binom{n-k-2}{k-2}\Biggr{)}\cdot\Biggr{(}1-\frac{k^{2}}{|{\cal
F}|}\cdot\binom{n-k-2}{k-2}\Biggr{)}.$

  * Proof:

Let ${\cal F}\subseteq\binom{[n]}{k}_{\mathrm{stab}}$ be a family of sets as
in the statement of the lemma. We first claim that every subfamily ${\cal
F}^{\prime}\subseteq{\cal F}$ whose size satisfies

$\displaystyle|{\cal F}^{\prime}|\geq\gamma\cdot|{\cal
F}|+k^{2}\cdot\binom{n-k-2}{k-2}$ (1)

spans an edge in $K({\cal F})$. To see this, consider such an ${\cal
F}^{\prime}$, and notice that the assumption that every element of $[n]$
belongs to at most $\gamma$ fraction of the sets of ${\cal F}$, combined with
the fact that $|{\cal F}^{\prime}|>\gamma\cdot|{\cal F}|$, implies that ${\cal
F}^{\prime}$ is not a trivial family, that is, its sets do not share a common
element. In addition, using $|{\cal
F}^{\prime}|>k^{2}\cdot\binom{n-k-2}{k-2}$, it follows from Lemma 3.5 that
${\cal F}^{\prime}$ is not a non-trivial intersecting family. We thus conclude
that ${\cal F}^{\prime}$ is not an intersecting family, hence it spans an edge
in $K({\cal F})$.

We next show a lower bound on the size of a maximum matching in $K({\cal F})$.
Consider the process that maintains a subfamily ${\cal F}^{\prime}$ of ${\cal
F}$, initiated as ${\cal F}$, and that removes from ${\cal F}^{\prime}$ the
two endpoints of some edge spanned by ${\cal F}^{\prime}$ as long as its size
satisfies the condition given in (1). The pairs of vertices that are removed
during the process form a matching ${\cal M}$ in $K({\cal F})$, whose size
satisfies

$\displaystyle|{\cal M}|$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\cdot\Biggr{(}|{\cal F}|-\Biggr{(}\gamma\cdot|{\cal
F}|+k^{2}\cdot\binom{n-k-2}{k-2}\Biggr{)}\Biggr{)}$ (2) $\displaystyle=$
$\displaystyle\frac{1}{2}\cdot\Biggr{(}(1-\gamma)\cdot|{\cal
F}|-k^{2}\cdot\binom{n-k-2}{k-2}\Biggr{)}.$

We now consider the sum of the degrees of adjacent vertices in the graph
$K({\cal F})$. Let $A,B\in{\cal F}$ be any adjacent vertices in $K({\cal F})$.
Since $A$ and $B$ are adjacent, they satisfy $A\cap B=\emptyset$, hence every
vertex of ${\cal F}$ that is not adjacent to $A$ nor to $B$ must include two
distinct elements $a\in A$ and $b\in B$. For every two such elements, it
follows from Claim 3.4 that the number of stable $k$-subsets of $[n]$ that
include them both is at most $\binom{n-k-2}{k-2}$. Therefore, the number of
vertices of ${\cal F}$ that are not adjacent to $A$ nor to $B$ does not exceed
$k^{2}\cdot\binom{n-k-2}{k-2}$. This implies that the degrees of $A$ and $B$
in $K({\cal F})$ satisfy

$d(A)+d(B)\geq|{\cal F}|-k^{2}\cdot\binom{n-k-2}{k-2}.$

Let ${\cal E}$ denote the edge set of $K({\cal F})$. We combine the above
bound with the lower bound given in (2) on the size of the matching ${\cal
M}$, to obtain that

$\displaystyle 2\cdot|{\cal E}|=\sum_{F\in{\cal F}}{d(F)}$ $\displaystyle\geq$
$\displaystyle\sum_{\\{A,B\\}\in{\cal M}}{(d(A)+d(B))}\geq|{\cal
M}|\cdot\Biggr{(}|{\cal F}|-k^{2}\cdot\binom{n-k-2}{k-2}\Biggr{)}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\cdot\Biggr{(}(1-\gamma)\cdot|{\cal
F}|-k^{2}\cdot\binom{n-k-2}{k-2}\Biggr{)}\cdot\Biggr{(}|{\cal
F}|-k^{2}\cdot\binom{n-k-2}{k-2}\Biggr{)}.$

Finally, consider a pair of random vertices chosen uniformly and independently
from ${\cal F}$. The probability that they form an edge in $K({\cal F})$ is
twice the number of edges in $K({\cal F})$ divided by $|{\cal F}|^{2}$. Hence,
the above bound on $2\cdot|{\cal E}|$ completes the proof.

As a corollary of Lemma 3.6, we obtain the following.

######  Corollary 3.7.

For integers $k\geq 2$ and $n\geq 10k^{4}$, let ${\cal F}$ be a family of
stable $k$-subsets of $[n]$ of size $|{\cal
F}|\geq\frac{1}{2n}\cdot\big{|}\binom{[n]}{k}_{\mathrm{stab}}\big{|}$ and let
$\gamma\in(0,1]$. Suppose that every element of $[n]$ belongs to at most
$\gamma$ fraction of the sets of ${\cal F}$. Then, the probability that two
random sets chosen uniformly and independently from ${\cal F}$ are adjacent in
$K({\cal F})$ is at least $\frac{3}{8}\cdot(\frac{3}{4}-\gamma)$.

  * Proof:

The assumption $n\geq 10k^{4}$ clearly implies that $n\geq 10k$, hence using
Claim 3.2 and Remark 3.3, it follows that
$\big{|}\binom{[n]}{k}_{\mathrm{stab}}\big{|}\geq\frac{80}{81}\cdot\binom{n-k+1}{k}$.
It thus follows that the family ${\cal F}$ satisfies $|{\cal
F}|\geq\frac{1}{2n}\cdot\big{|}\binom{[n]}{k}_{\mathrm{stab}}\big{|}\geq\frac{40}{81n}\cdot\binom{n-k+1}{k}$.
This is used to obtain that

$\displaystyle\frac{k^{2}}{|{\cal F}|}\cdot\binom{n-k-2}{k-2}$
$\displaystyle\leq$
$\displaystyle\frac{81nk^{2}}{40}\cdot\frac{\binom{n-k-2}{k-2}}{\binom{n-k+1}{k}}=\frac{81nk^{2}}{40}\cdot\frac{k\cdot(k-1)\cdot(n-2k+1)}{(n-k+1)\cdot(n-k)\cdot(n-k-1)}$
$\displaystyle\leq$
$\displaystyle\frac{81nk^{2}}{40}\cdot\frac{k^{2}}{(n-k)^{2}}\leq\frac{5k^{4}}{2n}\leq\frac{1}{4},$

where for the second inequality we use the obvious fact that $n-2k+1\leq
n-k-1$, for the third inequality we use the fact that $n-k\geq 9n/10$, and for
the fourth we use the assumption $n\geq 10k^{4}$. Applying Lemma 3.6, we
obtain that the probability that two random sets chosen uniformly and
independently from ${\cal F}$ are adjacent in $K({\cal F})$ is at least
$\frac{1}{2}\cdot(1-\gamma-\frac{1}{4})\cdot(1-\frac{1}{4})=\frac{3}{8}\cdot(\frac{3}{4}-\gamma)$.

The following lemma shows that if a large collection of vertices of $S(n,k)$
has a quite popular element, then every $k$-subset of $[n]$ that does not
include this element is disjoint from many of the vertices in the collection.

######  Lemma 3.8.

For integers $k\geq 2$ and $n\geq 2k$, let $X\subseteq[n]$ be a set, let
${\cal F}\subseteq\binom{X}{k}_{\mathrm{stab}}$ be a family, and let
$\gamma\in(0,1]$. Let $j\in X$ be an element that belongs to at least $\gamma$
fraction of the sets of ${\cal F}$, and suppose that $A\in\binom{[n]}{k}$ is a
set satisfying $j\notin A$. Then, the probability that a random set chosen
uniformly from ${\cal F}$ is disjoint from $A$ is at least

$\gamma-\frac{k}{|{\cal F}|}\cdot\binom{|X|-k-2}{k-2}.$

  * Proof:

Let ${\cal F}\subseteq\binom{X}{k}_{\mathrm{stab}}$ be a family as in the
lemma, and put ${\cal F}^{\prime}=\\{F\in{\cal F}\mid j\in F\\}$. By
assumption, it holds that $|{\cal F}^{\prime}|\geq\gamma\cdot|{\cal F}|$.
Suppose that $A\in\binom{[n]}{k}$ is a set satisfying $j\notin A$. We claim
that for every $i\in A$, the number of sets $B\in\binom{X}{k}_{\mathrm{stab}}$
satisfying $\\{i,j\\}\subseteq B$ does not exceed $\binom{|X|-k-2}{k-2}$.
Indeed, if $i\notin X$ then there are no such sets, so the bound trivially
holds, and if $i\in X$, the bound follows from Claim 3.4, using the one-to-one
correspondence between $\binom{X}{k}_{\mathrm{stab}}$ and the vertex set of
$S(|X|,k)$. This implies that the number of sets
$B\in\binom{X}{k}_{\mathrm{stab}}$ with $j\in B$ that intersect $A$ does not
exceed $k\cdot\binom{|X|-k-2}{k-2}$. It thus follows that the number of sets
of ${\cal F}$ that are disjoint from $A$ is at least

$|{\cal F}^{\prime}|-k\cdot\binom{|X|-k-2}{k-2}\geq\gamma\cdot|{\cal
F}|-k\cdot\binom{|X|-k-2}{k-2}.$

Hence, a random set chosen uniformly from ${\cal F}$ is disjoint from $A$ with
the desired probability.

As a corollary of Lemma 3.8, we obtain the following.

######  Corollary 3.9.

For integers $k\geq 2$ and $n$, let $X\subseteq[n]$ be a set of size $|X|\geq
10k^{3}$, let ${\cal F}\subseteq\binom{X}{k}_{\mathrm{stab}}$ be a family of
size $|{\cal
F}|\geq\frac{1}{2|X|}\cdot\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}$, and let
$\gamma\in(0,1]$. Let $j\in X$ be an element that belongs to at least $\gamma$
fraction of the sets of ${\cal F}$, and suppose that $A\in\binom{[n]}{k}$ is a
set satisfying $j\notin A$. Then, the probability that a random set chosen
uniformly from ${\cal F}$ is disjoint from $A$ is at least
$\gamma-\frac{1}{4}$.

  * Proof:

Recall that there is a one-to-one correspondence between the collection
$\binom{X}{k}_{\mathrm{stab}}$ and the vertex set of $S(|X|,k)$. Further, the
assumption $|X|\geq 10k^{3}$ clearly implies that $|X|\geq 10k$. It thus
follows, as in the proof of Corollary 3.7, that $|{\cal
F}|\geq\frac{40}{81|X|}\cdot\binom{|X|-k+1}{k}$. Similarly to the proof of
Corollary 3.7, using the assumption $|X|\geq 10k^{3}$, this implies that

$\displaystyle\frac{k}{|{\cal F}|}\cdot\binom{|X|-k-2}{k-2}$
$\displaystyle\leq$
$\displaystyle\frac{81|X|k}{40}\cdot\frac{\binom{|X|-k-2}{k-2}}{\binom{|X|-k+1}{k}}=\frac{81|X|k}{40}\cdot\frac{k\cdot(k-1)\cdot(|X|-2k+1)}{(|X|-k+1)\cdot(|X|-k)\cdot(|X|-k-1)}$
$\displaystyle\leq$
$\displaystyle\frac{81|X|k}{40}\cdot\frac{k^{2}}{(|X|-k)^{2}}\leq\frac{5k^{3}}{2|X|}\leq\frac{1}{4}.$

Applying Lemma 3.8, we obtain that the probability that a random set chosen
uniformly from ${\cal F}$ is disjoint from $A$ is at least
$\gamma-\frac{1}{4}$.

##  4 A Fixed-Parameter Algorithm for the Schrijver Problem

In this section we provide our randomized fixed-parameter algorithm for the
Schrijver problem. We first describe the ‘element elimination’ algorithm and
then use it to present the final algorithm and to prove Theorem 1.1.

###  4.1 The Element Elimination Algorithm

The ‘element elimination’ algorithm, given by the following theorem, will be
used to repeatedly reduce the size of the ground set of a Schrijver graph
while looking for a monochromatic edge.

######  Theorem 4.1.

There exists a randomized algorithm that given integers $n$ and $k$, a set
$X\subseteq[n]$ of size $|X|\geq 10k^{4}$, a parameter $\varepsilon>0$, a set
of colors $C\subseteq[n-2k+1]$ of size $|C|=|X|-2k+1$, and an oracle access to
a coloring $c:\binom{X}{k}_{\mathrm{stab}}\rightarrow[n-2k+1]$ of the vertices
of $K(\binom{X}{k}_{\mathrm{stab}})$, runs in time
$\mathop{\mathrm{poly}}(n,\ln(1/\varepsilon))$ and returns, with probability
at least $1-\varepsilon$,

  1. (a).

a monochromatic edge of $K(\binom{X}{k}_{\mathrm{stab}})$, or

  2. (b).

a vertex $A\in\binom{X}{k}_{\mathrm{stab}}$ satisfying $c(A)\notin C$, or

  3. (c).

a color $i\in C$ and an element $j\in X$ such that for every
$A\in\binom{[n]}{k}_{\mathrm{stab}}$ with $j\notin A$, a random vertex $B$
chosen uniformly from $\binom{X}{k}_{\mathrm{stab}}$ satisfies $c(B)=i$ and
$A\cap B=\emptyset$ with probability at least $\frac{1}{9n}$.

  * Proof:

For integers $n$ and $k$, let $X\subseteq[n]$, $C\subseteq[n-2k+1]$, and
$c:\binom{X}{k}_{\mathrm{stab}}\rightarrow[n-2k+1]$ be an input satisfying
$|X|\geq 10k^{4}$ and $|C|=|X|-2k+1$ as in the statement of the theorem. It
can be assumed that $k\geq 2$. Indeed, Theorem 2.2 guarantees that the graph
$K(\binom{X}{k}_{\mathrm{stab}})$, which is isomorphic to $S(|X|,k)$, has
either a monochromatic edge or a vertex whose color does not belong to $C$.
Hence, for $k=1$, an output of type (a) or (b) can be found by querying the
oracle for the colors of all the vertices in time polynomial in $n$. For
$k\geq 2$, consider the algorithm that given an input as above acts as follows
(see Algorithm 1).

The algorithm first selects uniformly and independently $m$ random sets
$A_{1},\ldots,A_{m}\in\binom{X}{k}_{\mathrm{stab}}$ for $m=b\cdot
n^{2}\cdot\ln(n/\varepsilon)$, where $b$ is some fixed constant to be
determined later (see lines 1–2), and queries the oracle for their colors. If
the sampled sets include two vertices that form a monochromatic edge in
$K(\binom{X}{k}_{\mathrm{stab}})$, then the algorithm returns such an edge
(output of type (a); see line 5). If they include a vertex whose color does
not belong to $C$, then the algorithm returns it (output of type (b); see line
10). Otherwise, the algorithm defines $i^{*}\in C$ as a color that appears on
a largest number of sampled sets $A_{t}$ (see lines 13–16). It further defines
$j^{*}\in X$ as an element that belongs to a largest number of sampled sets
$A_{t}$ with $c(A_{t})=i^{*}$ (see lines 17–20). Then, the algorithm returns
the pair $(i^{*},j^{*})$ (output of type (c); see line 21).

Algorithm 1 Element Elimination Algorithm (Theorem 4.1)

Input: Integers $n$ and $k\geq 2$, a set $X\subseteq[n]$ of size $|X|\geq
10k^{4}$, a set of colors $C\subseteq[n-2k+1]$ of size $|C|=|X|-2k+1$, and an
oracle access to a coloring
$c:\binom{X}{k}_{\mathrm{stab}}\rightarrow[n-2k+1]$ of
$K(\binom{X}{k}_{\mathrm{stab}})$.
Output: (a) A monochromatic edge of $K(\binom{X}{k}_{\mathrm{stab}})$, or (b)
a vertex $A\in\binom{X}{k}_{\mathrm{stab}}$ satisfying $c(A)\notin C$, or (c)
a color $i\in C$ and an element $j\in X$ such that for every
$A\in\binom{[n]}{k}_{\mathrm{stab}}$ with $j\notin A$, a random vertex
$B\in\binom{X}{k}_{\mathrm{stab}}$ chosen uniformly satisfies $c(B)=i$ and
$A\cap B=\emptyset$ with probability at least $\frac{1}{9n}$.

1:$m\leftarrow b\cdot n^{2}\cdot\ln(n/\varepsilon)$ for a sufficiently large
constant $b$

2:pick uniformly and independently at random sets
$A_{1},\ldots,A_{m}\in\binom{X}{k}_{\mathrm{stab}}$

3:for all $t,t^{\prime}\in[m]$ do

4: if $c(A_{t})=c(A_{t^{\prime}})$ and $A_{t}\cap A_{t^{\prime}}=\emptyset$
then

5: return $\\{A_{t},A_{t^{\prime}}\\}$$\triangleright$ output of type (a)

6: end if

7:end for

8:for all $t\in[m]$ do

9: if $c(A_{t})\notin C$ then

10: return $A_{t}$$\triangleright$ output of type (b)

11: end if

12:end for

13:for all $i\in C$ do

14: $\widetilde{\alpha}_{i}\leftarrow\frac{1}{m}\cdot|\\{t\in[m]\mid
c(A_{t})=i\\}|$

15:end for

16:$i^{*}\leftarrow$ an $i\in C$ with largest value of
$\widetilde{\alpha}_{i}$

17:for all $j\in X$ do

18: $\widetilde{\gamma}_{i^{*},j}\leftarrow\frac{1}{m}\cdot|\\{t\in[m]\mid
c(A_{t})=i^{*}~{}\mbox{and}~{}j\in A_{t}\\}|$

19:end for

20:$j^{*}\leftarrow$ a $j\in X$ with largest value of
$\widetilde{\gamma}_{i^{*},j}$

21:return $(i^{*},j^{*})$$\triangleright$ output of type (c)

The running time of the algorithm is clearly polynomial in $n$ and in
$\ln(1/\varepsilon)$. We turn to prove that for every input, the algorithm
returns a valid output, of type (a), (b), or (c), with probability at least
$1-\varepsilon$. We start with the following lemma that shows that if the
input coloring has a large color class with no popular element, then the
algorithm returns a valid output of type (a) with the desired probability.

######  Lemma 4.2.

Suppose that the input coloring $c$ has a color class ${\cal
F}\subseteq\binom{X}{k}_{\mathrm{stab}}$ of size $|{\cal
F}|\geq\frac{1}{2|X|}\cdot\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}$ such
that every element of $X$ belongs to at most half of the sets of ${\cal F}$.
Then, Algorithm 1 returns a monochromatic edge with probability at least
$1-\varepsilon$.

  * Proof:

Let ${\cal F}$ be as in the lemma. Using the assumptions $k\geq 2$ and
$|X|\geq 10k^{4}$ and using the one-to-one correspondence between
$\binom{X}{k}_{\mathrm{stab}}$ and the vertex set of $S(|X|,k)$, we can apply
Corollary 3.7 with $\gamma=\frac{1}{2}$ to obtain that two random sets chosen
uniformly and independently from ${\cal F}$ are adjacent in $K({\cal F})$ with
probability at least $\frac{3}{8}\cdot(\frac{3}{4}-\gamma)=\frac{3}{32}$.
Further, since the family ${\cal F}$ satisfies $|{\cal
F}|\geq\frac{1}{2|X|}\cdot\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}$, a
random vertex chosen uniformly from $\binom{X}{k}_{\mathrm{stab}}$ belongs to
${\cal F}$ with probability at least $\frac{1}{2|X|}$. Hence, for two random
vertices chosen uniformly and independently from
$\binom{X}{k}_{\mathrm{stab}}$, the probability that they both belong to
${\cal F}$ is at least $(\frac{1}{2|X|})^{2}$, and conditioned on this event,
their probability to form an edge in $K({\cal F})$ is at least $\frac{3}{32}$.
This implies that the probability that two random vertices chosen uniformly
and independently from $\binom{X}{k}_{\mathrm{stab}}$ form a monochromatic
edge in $K(\binom{X}{k}_{\mathrm{stab}})$ is at least
$(\frac{1}{2|X|})^{2}\cdot\frac{3}{32}=\frac{3}{128|X|^{2}}$.

Now, by considering $\lfloor m/2\rfloor$ pairs of the random sets chosen by
Algorithm 1 (line 2), it follows that the probability that no pair forms a
monochromatic edge does not exceed

$\Big{(}1-\tfrac{3}{128|X|^{2}}\Big{)}^{\lfloor m/2\rfloor}\leq
e^{-3\cdot\lfloor m/2\rfloor/(128|X|^{2})}\leq\varepsilon,$

where the last inequality follows by $|X|\leq n$ and by the choice of $m$,
assuming that the constant $b$ is sufficiently large. It thus follows that
with probability at least $1-\varepsilon$, the algorithm returns a
monochromatic edge, as required.

We next handle the case in which every large color class of the input coloring
has a popular element. To do so, we first show that the samples of the
algorithm provide a good estimation for the fraction of vertices in each color
class as well as for the fraction of vertices that share any given element in
each color class. For every color $i\in C$, let $\alpha_{i}$ denote the
fraction of vertices of $K(\binom{X}{k}_{\mathrm{stab}})$ colored $i$, that
is,

$\alpha_{i}=\frac{|\\{A\in\binom{X}{k}_{\mathrm{stab}}\mid
c(A)=i\\}|}{\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}},$

and let $\widetilde{\alpha}_{i}$ denote the fraction of the vertices sampled
by the algorithm that are colored $i$ (see line 14). Similarly, for every
$i\in C$ and $j\in X$, let $\gamma_{i,j}$ denote the fraction of vertices of
$K(\binom{X}{k}_{\mathrm{stab}})$ colored $i$ that include $j$, that is,

$\gamma_{i,j}=\frac{|\\{A\in\binom{X}{k}_{\mathrm{stab}}\mid
c(A)=i~{}\mbox{and}~{}j\in
A\\}|}{\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}},$

and let $\widetilde{\gamma}_{i,j}$ denote the fraction of the vertices sampled
by the algorithm that are colored $i$ and include $j$. Let $E$ denote the
event that

$\displaystyle|\alpha_{i}-\widetilde{\alpha}_{i}|\leq\frac{1}{2|X|}~{}~{}\mbox{and}~{}~{}|\gamma_{i,j}-\widetilde{\gamma}_{i,j}|\leq\frac{1}{2|X|}~{}~{}\mbox{for
all}~{}i\in C,~{}j\in X.$ (3)

By a standard concentration argument, we obtain the following lemma.

######  Lemma 4.3.

The probability of the event $E$ is at least $1-\varepsilon$.

  * Proof:

By the Chernoff-Hoeffding bound (Theorem 2.4) applied with
$\mu=\frac{1}{2|X|}$, the probability that an inequality from (3) does not
hold is at most

$2\cdot e^{-2m/(4|X|^{2})}\leq\frac{\varepsilon}{n^{2}},$

where the inequality follows by $|X|\leq n$ and by the choice of $m$, assuming
that the constant $b$ is sufficiently large. By the union bound over all the
colors $i\in C$ and all the pairs $(i,j)\in C\times X$, that is, over
$|C|\cdot(1+|X|)\leq n^{2}$ events, we get that all the inequalities in (3)
hold with probability at least
$1-n^{2}\cdot\frac{\varepsilon}{n^{2}}=1-\varepsilon$, as required.

We now show that if every large color class of the input coloring has a
popular element and the event $E$ occurs, then the algorithm returns a valid
output.

######  Lemma 4.4.

Suppose that the coloring $c$ satisfies that for every color class ${\cal
F}\subseteq\binom{X}{k}_{\mathrm{stab}}$ whose size satisfies $|{\cal
F}|\geq\frac{1}{2|X|}\cdot\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}$ there
exists an element of $X$ that belongs to more than half of the sets of ${\cal
F}$. Then, if the event $E$ occurs, Algorithm 1 returns a valid output.

  * Proof:

Assume that the event $E$ occurs. If Algorithm 1 returns an output of type (a)
or (b), i.e., a monochromatic edge or a vertex whose color does not belong to
$C$, then the output is verified before it is returned and is thus valid. So
suppose that the algorithm returns a pair $(i^{*},j^{*})\in C\times X$. Recall
that the color $i^{*}$ is defined by Algorithm 1 as an $i\in C$ with largest
value of $\widetilde{\alpha}_{i}$ (see line 16). Since the colors of all the
sampled sets belong to $C$, it follows that $\sum_{i\in
C}{\widetilde{\alpha}_{i}}=1$, and thus

$\displaystyle\widetilde{\alpha}_{i^{*}}\geq\frac{1}{|C|}\geq\frac{1}{|X|},$
(4)

where the last inequality follows by $|C|=|X|-2k+1\leq|X|$.

Let ${\cal F}$ be the family of vertices of $K(\binom{X}{k}_{\mathrm{stab}})$
colored $i^{*}$, i.e., ${\cal F}=\\{A\in\binom{X}{k}_{\mathrm{stab}}\mid
c(A)=i^{*}\\}$. Since the event $E$ occurs (see (3)), it follows from (4) that

$|{\cal
F}|=\alpha_{i^{*}}\cdot\Big{|}\binom{X}{k}_{\mathrm{stab}}\Big{|}\geq\Big{(}\widetilde{\alpha}_{i^{*}}-\frac{1}{2|X|}\Big{)}\cdot\Big{|}\binom{X}{k}_{\mathrm{stab}}\Big{|}\geq\frac{1}{2|X|}\cdot\Big{|}\binom{X}{k}_{\mathrm{stab}}\Big{|}.$

Hence, by the assumption of the lemma, there exists an element $j\in X$ that
belongs to more than half of the sets of ${\cal F}$, that is,
$\gamma_{i^{*},j}>\frac{1}{2}$. Since the event $E$ occurs, it follows that
this $j$ satisfies $\widetilde{\gamma}_{i^{*},j}>\frac{1}{2}-\frac{1}{2|X|}$.
Recalling that the element $j^{*}$ is defined by Algorithm 1 as a $j\in X$
with largest value of $\widetilde{\gamma}_{i^{*},j}$ (see line 20), it must
satisfy $\widetilde{\gamma}_{i^{*},j^{*}}>\frac{1}{2}-\frac{1}{2|X|}$, and
using again the fact that the event $E$ occurs, we derive that
$\gamma_{i^{*},j^{*}}\geq\widetilde{\gamma}_{i^{*},j^{*}}-\frac{1}{2|X|}>\frac{1}{2}-\frac{1}{|X|}$.

By $k\geq 2$ and $|X|\geq 10k^{4}$, we can apply Corollary 3.9 with ${\cal
F}$, $j^{*}$, and $\gamma=\frac{1}{2}-\frac{1}{|X|}$ to obtain that for every
set $A\in\binom{[n]}{k}_{\mathrm{stab}}$ with $j^{*}\notin A$, the probability
that a random set chosen uniformly from ${\cal F}$ is disjoint from $A$ is at
least $\gamma-\frac{1}{4}$. Since the probability that a random set chosen
uniformly from $\binom{X}{k}_{\mathrm{stab}}$ belongs to ${\cal F}$ is at
least $\frac{1}{2|X|}$, it follows that the probability that a random set $B$
chosen uniformly from $\binom{X}{k}_{\mathrm{stab}}$ satisfies $c(B)=i^{*}$
and $A\cap B=\emptyset$ is at least

$\frac{1}{2|X|}\cdot\Big{(}\gamma-\frac{1}{4}\Big{)}=\frac{1}{2|X|}\cdot\Big{(}\frac{1}{4}-\frac{1}{|X|}\Big{)}\geq\frac{1}{9|X|}\geq\frac{1}{9n},$

where the first inequality holds because $k\geq 2$ and $|X|\geq 10k^{4}$. This
implies that $(i^{*},j^{*})$ is a valid output of type (c).

Equipped with Lemmas 4.2, 4.3, and 4.4, we are ready to derive the correctness
of Algorithm 1 and to complete the proof of Theorem 4.1. If the input coloring
$c$ has a color class ${\cal F}\subseteq\binom{X}{k}_{\mathrm{stab}}$ of size
$|{\cal F}|\geq\frac{1}{2|X|}\cdot\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}$
such that every element of $X$ belongs to at most half of the sets of ${\cal
F}$, then, by Lemma 4.2, the algorithm returns with probability at least
$1-\varepsilon$ a monochromatic edge, i.e., a valid output of type (a).
Otherwise, the input coloring $c$ satisfies that for every color class ${\cal
F}\subseteq\binom{X}{k}_{\mathrm{stab}}$ of size $|{\cal
F}|\geq\frac{1}{2|X|}\cdot\big{|}\binom{X}{k}_{\mathrm{stab}}\big{|}$ there
exists an element of $X$ that belongs to more than half of the sets of ${\cal
F}$. By Lemma 4.3, the event $E$ occurs with probability at least
$1-\varepsilon$, implying by Lemma 4.4 that with such probability, the
algorithm returns a valid output. It thus follows that for every input
coloring the algorithm returns a valid output with probability at least
$1-\varepsilon$, and we are done.

###  4.2 The Fixed-Parameter Algorithm for the Schrijver Problem

We turn to present our fixed-parameter algorithm for the Schrijver problem and
to complete the proof of Theorem 1.1.

  * Proof of Theorem 1.1:

Suppose that we are given, for integers $n$ and $k$ with $n\geq 2k$, an oracle
access to a coloring $c:\binom{[n]}{k}_{\mathrm{stab}}\rightarrow[n-2k+1]$ of
the vertices of the Schrijver graph $S(n,k)$. It suffices to present an
algorithm with success probability at least $1/2$, because the latter can be
easily amplified by repetitions. Our algorithm has two phases, as described
below (see Algorithm 2).

Algorithm 2 The Algorithm for the Schrijver Problem (Theorem 1.1)

Input: Integers $n,k$ with $n\geq 2k$ and an oracle access to a coloring
$c:\binom{[n]}{k}_{\mathrm{stab}}\rightarrow[n-2k+1]$.
Output: A monochromatic edge of $S(n,k)$.

1:$s\leftarrow\max(n-10k^{4},0)$, $X_{0}\leftarrow[n]$,
$C_{0}\leftarrow[n-2k+1]$$\triangleright$ $|C_{0}|=|X_{0}|-2k+1$

2:for all $l=0,1,\ldots,s-1$ do$\triangleright$ first phase

3: call Algorithm 1 with $n$, $k$, $X_{l}$, $C_{l}$,
$\varepsilon=\frac{1}{4n}$ and with the restriction of $c$ to
$\binom{X_{l}}{k}_{\mathrm{stab}}$

4: if Algorithm 1 returns an edge $\\{A,B\\}$ with $c(A)=c(B)$
then$\triangleright$ output of type (a)

5: return $\\{A,B\\}$

6: end if

7: if Algorithm 1 returns a vertex $A\in\binom{X_{l}}{k}_{\mathrm{stab}}$ with
$c(A)=i_{r}\notin C_{l}$ then$\triangleright$ output of type (b)

8: for all $t\in[18n]$ do

9: pick uniformly at random a set $B_{t}\in\binom{X_{r}}{k}_{\mathrm{stab}}$

10: if $c(B_{t})=i_{r}$ and $A\cap B_{t}=\emptyset$ then

11: return $\\{A,B_{t}\\}$

12: end if

13: end for

14: return ‘failure’

15: end if

16: if Algorithm 1 returns a pair $(i_{l},j_{l})\in C_{l}\times X_{l}$
then$\triangleright$ output of type (c)

17: $X_{l+1}\leftarrow X_{l}\setminus\\{j_{l}\\},~{}~{}C_{l+1}\leftarrow
C_{l}\setminus\\{i_{l}\\}$$\triangleright$ $|C_{l+1}|=|X_{l+1}|-2k+1$

18: end if

19:end for

20:query the oracle for the colors of all the vertices of
$K(\binom{X_{s}}{k}_{\mathrm{stab}})$$\triangleright$ second phase

21:if there exists a vertex $A\in\binom{X_{s}}{k}_{\mathrm{stab}}$ of color
$c(A)=i_{r}\notin C_{s}$ then

22: for all $t\in[18n]$ do

23: pick uniformly at random a set $B_{t}\in\binom{X_{r}}{k}_{\mathrm{stab}}$

24: if $c(B_{t})=i_{r}$ and $A\cap B_{t}=\emptyset$ then

25: return $\\{A,B_{t}\\}$

26: end if

27: end for

28: return ‘failure’

29:else

30: find $A,B\in\binom{X_{s}}{k}_{\mathrm{stab}}$ satisfying $c(A)=c(B)$ and
$A\cap B=\emptyset$$\triangleright$ exist by Theorem 2.2 [20]

31: return $\\{A,B\\}$

32:end if

In the first phase, the algorithm repeatedly applies the ‘element elimination’
algorithm given in Theorem 4.1 (Algorithm 1). Initially, we define

$s=\max(n-10k^{4},0),~{}~{}X_{0}=[n],~{}~{}\mbox{and}~{}~{}C_{0}=[n-2k+1].$

In the $l$th iteration, $0\leq l<s$, we call Algorithm 1 with $n$, $k$,
$X_{l}$, $C_{l}$, $\varepsilon=\frac{1}{4n}$ and with the restriction of the
given coloring $c$ to the vertices of $\binom{X_{l}}{k}_{\mathrm{stab}}$ to
obtain with probability at least $1-\varepsilon$,

  1. (a).

a monochromatic edge $\\{A,B\\}$ of $K(\binom{X_{l}}{k}_{\mathrm{stab}})$, or

  2. (b).

a vertex $A\in\binom{X_{l}}{k}_{\mathrm{stab}}$ satisfying $c(A)\notin C_{l}$,
or

  3. (c).

a color $i_{l}\in C_{l}$ and an element $j_{l}\in X_{l}$ such that for every
$A\in\binom{[n]}{k}_{\mathrm{stab}}$ with $j_{l}\notin A$, a random vertex $B$
chosen uniformly from $\binom{X_{l}}{k}_{\mathrm{stab}}$ satisfies
$c(B)=i_{l}$ and $A\cap B=\emptyset$ with probability at least $\frac{1}{9n}$.

As will be explained shortly, if the output of Algorithm 1 is of type (a) or
(b) then we either return a monochromatic edge or declare ‘failure’, and if
the output is a pair $(i_{l},j_{l})$ of type (c) then we define
$X_{l+1}=X_{l}\setminus\\{j_{l}\\}$ and $C_{l+1}=C_{l}\setminus\\{i_{l}\\}$
and, as long as $l<s$, proceed to the next call of Algorithm 1. Note that the
sizes of the sets $X_{l}$ and $C_{l}$ are reduced by $1$ in every iteration,
hence we maintain the equality $|C_{l}|=|X_{l}|-2k+1$ for all $l$. We now
describe how the algorithm acts in the $l$th iteration for each type of output
returned by Algorithm 1.

If the output is of type (a), then the returned monochromatic edge of
$K(\binom{X_{l}}{k}_{\mathrm{stab}})$ is also a monochromatic edge of
$S(n,k)$, so we return it (see lines 4–6).

If the output is of type (b), then we are given a vertex
$A\in\binom{X_{l}}{k}_{\mathrm{stab}}$ satisfying $c(A)=i_{r}\notin C_{l}$ for
some $r<l$. Since $i_{r}\notin C_{l}$, it follows that $j_{r}\notin X_{l}$,
and thus $j_{r}\notin A$. In this case, we pick uniformly and independently
$18n$ random sets from $\binom{X_{r}}{k}_{\mathrm{stab}}$ and query the oracle
for their colors. If we find a vertex $B$ that forms together with $A$ a
monochromatic edge in $S(n,k)$, we return the monochromatic edge $\\{A,B\\}$,
and otherwise we declare ‘failure’ (see lines 7–15).

If the output of Algorithm 1 is a pair $(i_{l},j_{l})$ of type (c), then we
define, as mentioned above, the sets $X_{l+1}=X_{l}\setminus\\{j_{l}\\}$ and
$C_{l+1}=C_{l}\setminus\\{i_{l}\\}$ (see lines 16–18). Observe that for $0\leq
l<s$, it holds that $|X_{l}|=n-l>n-s=10k^{4}$, allowing us, by Theorem 4.1, to
call Algorithm 1 in the $l$th iteration.

In case that all the $s$ calls to Algorithm 1 return an output of type (c), we
arrive to the second phase of the algorithm. Here, we are given the sets
$X_{s}$ and $C_{s}$ that satisfy $|X_{s}|=n-s\leq 10k^{4}$ and
$|C_{s}|=|X_{s}|-2k+1$, and we query the oracle for the colors of each and
every vertex of the graph $K(\binom{X_{s}}{k}_{\mathrm{stab}})$. If we find a
vertex $A\in\binom{X_{s}}{k}_{\mathrm{stab}}$ satisfying $c(A)=i_{r}\notin
C_{s}$ for some $r<s$, then, as before, we pick uniformly and independently
$18n$ random sets from $\binom{X_{r}}{k}_{\mathrm{stab}}$ and query the oracle
for their colors. If we find a vertex $B$ that forms together with $A$ a
monochromatic edge in $S(n,k)$, we return the monochromatic edge $\\{A,B\\}$,
and otherwise we declare ‘failure’ (see lines 21–28). Otherwise, all the
vertices of $K(\binom{X_{s}}{k}_{\mathrm{stab}})$ are colored by colors from
$C_{s}$. By Theorem 2.2, the chromatic number of the graph
$K(\binom{X_{s}}{k}_{\mathrm{stab}})$, which is isomorphic to $S(|X_{s}|,k)$,
is $|X_{s}|-2k+2>|C_{s}|$. Hence, there must exist a monochromatic edge in
$K(\binom{X_{s}}{k}_{\mathrm{stab}})$, and by checking all the pairs of its
vertices we find such an edge and return it (see lines 30–31).

We turn to analyze the probability that Algorithm 2 returns a monochromatic
edge. Note that whenever the algorithm returns an edge, it checks that it is
monochromatic and thus ensures that it forms a valid solution. Hence, it
suffices to show that the algorithm declares ‘failure’ with probability at
most $1/2$. To see this, recall that the algorithm calls Algorithm 1 at most
$s<n$ times, and that by Theorem 4.1 the probability that its output is not
valid is at most $\varepsilon=\frac{1}{4n}$. By the union bound, the
probability that any of the calls to Algorithm 1 returns an invalid output
does not exceed $1/4$. The only situation in which Algorithm 2 declares
‘failure’ is when it finds, for some $r<s$, a vertex
$A\in\binom{[n]}{k}_{\mathrm{stab}}$ with $c(A)=i_{r}$ and $j_{r}\notin A$,
and none of the $18n$ sampled sets $B\in\binom{X_{r}}{k}_{\mathrm{stab}}$
satisfies $c(B)=i_{r}$ and $A\cap B=\emptyset$ (see lines 7–15, 21–28).
However, assuming that all the calls to Algorithm 1 return valid outputs, the
$r$th run guarantees, by Theorem 4.1, that a random vertex $B$ uniformly
chosen from $\binom{X_{r}}{k}_{\mathrm{stab}}$ satisfies $c(B)=i_{r}$ and
$A\cap B=\emptyset$ for the given $A$ with probability at least
$\frac{1}{9n}$. Hence, the probability that the algorithm declares ‘failure’
does not exceed $(1-\frac{1}{9n})^{18n}\leq e^{-2}<\frac{1}{4}$. Using again
the union bound, it follows that the probability that Algorithm 2 either gets
an invalid output from Algorithm 1 or fails to find a vertex that forms a
monochromatic edge with a set $A$ as above is at most $1/2$. Therefore, the
probability that Algorithm 2 successfully finds a monochromatic edge is at
least $1/2$, as desired.

We finally analyze the running time of Algorithm 2. In its first phase, the
algorithm calls Algorithm 1 at most $s<n$ times, where the running time needed
for each call is, by Theorem 4.1 and by our choice of $\varepsilon$,
polynomial in $n$. It is clear that the other operations made throughout this
phase can also be implemented in time polynomial in $n$. In its second phase,
the algorithm enumerates all the vertices of
$K(\binom{X_{s}}{k}_{\mathrm{stab}})$. This phase can be implemented in
running time polynomial in $n$ and in the number of vertices of this graph.
The latter is
$\big{|}\binom{X_{s}}{k}_{\mathrm{stab}}\big{|}\leq|X_{s}|^{k}\leq(10k^{4})^{k}=k^{O(k)}$.
It thus follows that the total running time of Algorithm 2 is $n^{O(1)}\cdot
k^{O(k)}$, completing the proof.

## Acknowledgement

We thank Gabriel Istrate for clarifications on [18].

## References

  * [1] I. Bárány.  A short proof of Kneser’s conjecture.  J. Comb. Theory, Ser. A, 25(3):325–326, 1978.
  * [2] K. Borsuk.  Drei Sätze über die $n$-dimensionale euklidische Sphäre.  Fundamenta Mathematicae, 20(1):177–190, 1933.
  * [3] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [4] 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), 2022.
  * [5] X. Deng, Z. Feng, and R. Kulkarni.  Octahedral Tucker is PPA-complete.  Electronic Colloquium on Computational Complexity (ECCC), 24:118, 2017.
  * [6] P. Erdös, C. Ko, and R. Rado.  Intersection theorems for systems of finite sets.  Quart. J. Math., 12(1):313–320, 1961.
  * [7] 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.
  * [8] 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.
  * [9] 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.
  * [10] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.  Kernelization: Theory of Parameterized Preprocessing.  Cambridge University Press, 2019.
  * [11] P. Frankl and A. Kupavskii.  Maximal degrees in subgraphs of Kneser graphs.  arXiv, abs/2004.08718, 2020.
  * [12] D. Gale.  Neighboring vertices on a convex polyhedron.  In H. W. Kuhn and A. Tucker, editors, Linear Inequalities and Related Systems, volume 38 of Annals of Math. Studies, pages 255–263. 1956\.
  * [13] P. W. Goldberg, A. Hollender, A. Igarashi, P. Manurangsi, and W. Suksompong.  Consensus halving for sets of items.  In Proc. 16th Web and Internet Economics International Conference (WINE’20), pages 384–397, 2020.
  * [14] I. Haviv.  The complexity of finding fair independent sets in cycles.  In 12th Innovations in Theoretical Computer Science Conference (ITCS’21), pages 4:1–4:14, 2021.
  * [15] I. Haviv.  A fixed-parameter algorithm for the Kneser problem.  In 49th International Colloquium on Automata, Languages, and Programming (ICALP’22), pages 7:1–7:18, 2022.
  * [16] A. J. W. Hilton and E. C. Milner.  Some intersection theorems for systems of finite sets.  Quart. J. Math., 18(1):369–384, 1967.
  * [17] C. R. Hobby and J. R. Rice.  A moment problem in ${L}_{1}$ approximation.  Proc. Amer. Math. Soc., 16(4):665–670, 1965.
  * [18] G. Istrate, C. Bonchis, and A. Craciun.  Kernelization, proof complexity and social choice.  In 48th International Colloquium on Automata, Languages, and Programming (ICALP’21), pages 135:1–135:21, 2021.
  * [19] M. Kneser.  Aufgabe 360.  Jahresbericht der Deutschen Mathematiker-Vereinigung, 58(2):27, 1955\.
  * [20] L. Lovász.  Kneser’s conjecture, chromatic number, and homotopy.  J. Comb. Theory, Ser. A, 25(3):319–324, 1978.
  * [21] P. Manurangsi and W. Suksompong.  Computing a small agreeable set of indivisible items.  Artif. Intell., 268:96–114, 2019.  Preliminary versions in IJCAI’16 and IJCAI’17.
  * [22] J. Matoušek.  Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry.  Springer Publishing Company, Incorporated, 2007.
  * [23] C. McDiarmid.  Concentration.  In Probabilistic methods for algorithmic discrete mathematics, volume 16 of Algorithms Combin., pages 195–248. Springer, Berlin, 1998\.
  * [24] N. Megiddo and C. H. Papadimitriou.  On total functions, existence theorems and computational complexity.  Theor. Comput. Sci., 81(2):317–324, 1991.
  * [25] 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.
  * [26] A. Schrijver.  Vertex-critical subgraphs of Kneser graphs.  Nieuw Arch. Wiskd., 26(3):454–461, 1978.
  * [27] F. W. Simmons and F. E. Su.  Consensus-halving via theorems of Borsuk-Ulam and Tucker.  Math. Soc. Sci., 45(1):15–25, 2003.
  * [28] J. Talbot.  Intersecting families of separated sets.  J. London Math. Soc., 68(1):37–51, 2003.