  In the multicoloring problem, also known as ($a$:$b$)-coloring or $b$-fold
coloring, we are given a graph G and a set of $a$ colors, and the task is to
assign a subset of $b$ colors to each vertex of G so that adjacent vertices
receive disjoint color subsets. This natural generalization of the classic
coloring problem (the $b=1$ case) is equivalent to finding a homomorphism to
the Kneser graph $KG_{a,b}$, and gives relaxations approaching the fractional
chromatic number.
  We study the complexity of determining whether a graph has an
($a$:$b$)-coloring. Our main result is that this problem does not admit an
algorithm with running time $f(b)\cdot 2^{o(\log b)\cdot n}$, for any
computable $f(b)$, unless the Exponential Time Hypothesis (ETH) fails. A
$(b+1)^n\cdot \text{poly}(n)$-time algorithm due to Nederlof [2008] shows that
this is tight. A direct corollary of our result is that the graph homomorphism
problem does not admit a $2^{O(n+h)}$ algorithm unless ETH fails, even if the
target graph is required to be a Kneser graph. This refines the understanding
given by the recent lower bound of Cygan et al. [SODA 2016].
  The crucial ingredient in our hardness reduction is the usage of detecting
matrices of Lindstr\"om [Canad. Math. Bull., 1965], which is a combinatorial
tool that, to the best of our knowledge, has not yet been used for proving
complexity lower bounds. As a side result, we prove that the running time of
the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et al. [ESA 2015] for
the r-monomial detection problem are optimal under ETH.
