  Local certification is a distributed mechanism enabling the nodes of a
network to check the correctness of the current configuration, thanks to small
pieces of information called certificates. For many classic global properties,
like checking the acyclicity of the network, the optimal size of the
certificates depends on the size of the network, $n$. In this paper, we focus
on properties for which the size of the certificates does not depend on $n$ but
on other parameters. We focus on three such important properties and prove
tight bounds for all of them. Namely, we prove that the optimal certification
size is: $\Theta(\log k)$ for $k$-colorability (and even exactly $\lceil \log k
\rceil$ bits in the anonymous model while previous works had only proved a
$2$-bit lower bound); $(1/2)\log t+o(\log t)$ for dominating sets at distance
$t$ (an unexpected and tighter-than-usual bound) ; and $\Theta(\log \Delta)$
for perfect matching in graphs of maximum degree $\Delta$ (the first
non-trivial bound parameterized by $\Delta$). We also prove some surprising
upper bounds, for example, certifying the existence of a perfect matching in a
planar graph can be done with only two bits. In addition, we explore various
specific cases for these properties, in particular improving our understanding
of the trade-off between locality of the verification and certificate size.
