  Until recently, techniques for obtaining lower bounds for kernelization were
one of the most sought after tools in the field of parameterized complexity.
Now, after a strong influx of techniques, we are in the fortunate situation of
having tools available that are even stronger than what has been required in
their applications so far. Based on a result of Fortnow and Santhanam (JCSS
2011), Bodlaender et al. (JCSS 2009) showed that, unless NP \subseteq
coNP/poly, the existence of a deterministic polynomial-time composition
algorithm, i.e., an algorithm which outputs an instance of bounded parameter
value which is yes if and only if one of t input instances is yes, rules out
the existence of polynomial kernels for a problem. Dell and van Melkebeek (STOC
2010) continued this line of research and, amongst others, were able to rule
out kernels of size O(k^d-eps) for certain problems, assuming NP !\subseteq
coNP/poly. Their work implies that even the existence of a co-nondeterministic
composition rules out polynomial kernels.
  In this work we present the first example of how co-nondeterminism can help
to make a composition algorithm. We study a Ramsey-type problem: Given a graph
G and an integer k, the question is whether G contains an independent set or a
clique of size at least k. It was asked by Rod Downey whether this problem
admits a polynomial kernelization. We provide a co-nondeterministic composition
based on embedding t instances into a single host graph H. The crux is that the
host graph H needs to observe a bound of L \in O(log t) on both its maximum
independent set and maximum clique size, while also having a cover of its
vertex set by independent sets and cliques all of size L; the
co-nondeterministic composition is build around the search for such graphs.
Thus we show that, unless NP \subseteq coNP/poly, the problem does not admit a
kernelization with polynomial size guarantee.
