  Garnero et al. [SIAM J. Discrete Math. 2015, 29(4):1864--1894] recently
introduced a framework based on dynamic programming to make applications of the
protrusion replacement technique constructive and to obtain explicit upper
bounds on the involved constants. They show that for several graph problems,
for every boundary size $t$ one can find an explicit set $\mathcal{R}_t$ of
representatives. Any subgraph $H$ with a boundary of size $t$ can be replaced
with a representative $H' \in \mathcal{R}_t$ such that the effect of this
replacement on the optimum can be deduced from $H$ and $H'$ alone. Their upper
bounds on the size of the graphs in $\mathcal{R}_t$ grow triple-exponentially
with $t$. In this paper we complement their results by lower bounds on the
sizes of representatives, in terms of the boundary size $t$. For example, we
show that each set of planar representatives $\mathcal{R}_t$ for Independent
Set or Dominating Set contains a graph with $\Omega(2^t / \sqrt{4t})$ vertices.
This lower bound even holds for sets that only represent the planar subgraphs
of bounded pathwidth. To obtain our results we provide a lower bound on the
number of equivalence classes of the canonical equivalence relation for
Independent Set on $t$-boundaried graphs. We also find an elegant
characterization of the number of equivalence classes in general graphs, in
terms of the number of monotone functions of a certain kind. Our results show
that the number of equivalence classes is at most $2^{2^t}$, improving on
earlier bounds of the form $(t+1)^{2^t}$.
