  An adjacency sketching or implicit labeling scheme for a family $\cal F$ of
graphs is a method that defines for any $n$ vertex $G \in \cal F$ an assignment
of labels to each vertex in $G$, so that the labels of two vertices tell you
whether or not they are adjacent. The goal is to come up with labeling schemes
that use as few bits as possible to represent the labels. By using randomness
when assigning labels, it is sometimes possible to produce adjacency sketches
with much smaller label sizes, but this comes at the cost of introducing some
probability of error. Both deterministic and randomized labeling schemes have
been extensively studied, as they have applications for distributed data
structures and deeper connections to universal graphs and communication
complexity. The main question of interest is which graph families have schemes
using short labels, usually $O(\log n)$ in the deterministic case or constant
for randomized sketches.
  In this work we consider the resilience of probabilistic adjacency sketches
against an adversary making adaptive queries to the labels. This differs from
the previously analyzed probabilistic setting which is ``one shot". We show
that in the adaptive adversarial case the size of the labels is tightly related
to the maximal degree of the graphs in $\cal F$. This results in a stronger
characterization compared to what is known in the non-adversarial setting. In
more detail, we construct sketches that fail with probability $\varepsilon$ for
graphs with maximal degree $d$ using $2d\log (1/\varepsilon)$ bit labels and
show that this is roughly the best that can be done for any specific graph of
maximal degree $d$, e.g.\ a $d$-ary tree.
