What even is a vertex Lipschitz condition?

Question

I am re-reading parts of the probabilistic method by Alon and Spencer. On page 100 it says

A graph theoretic function $f$ satisfies the vertex Lipschitz condition if whenever $H$ and $H'$ differ at only one vertex, $|f(H)-f(H')|\leq 1$.

I cannot seem to wrap my head around how two graphs are supposed to differ at only one vertex. The only scenario I can imagine is when $H'$ is obtained from $H$ by simply adding an isolated vertex or vice-versa. But this surely is not the only implied meaning. It seems to me that if two graphs on the same vertex set differ in one vertex then they need to differ in at least one other vertex as well, right? What graph exists for instance that differs at only one vertex from a cycle? Or a complete graph?

Answer 1

Short answer: graphs $H, H'$ on the same vertex set "differ only at vertex $v$" if $H-v$ is the same graph as $H'-v$. Another way to say this is that we can obtain $H'$ from $H$ by adding or removing edges incident on $v$.

For example, a graph differs only at one vertex from $K_n$ if it has a clique of size $n-1$ (but the $n^{\text{th}}$ vertex can do anything).

---

Long answer: we need to look at the general Lipschitz condition for exposure martingales. (This is all from section 7.4 of Alon & Spencer.) Here, we consider the set $A^B$ of all functions $g: B \to A$, with a gradation $\varnothing = B_0 \subset B_1 \subset \dots \subset B_m = B$. A functional $L : A^B \to \mathbb R$ satisfies the Lipschitz condition if, whenever $h, h' \in A^B$ differ only in their values on $B_{i+1} - B_i$, we have $|L(h) - L(h')| \le 1$.

To put the vertex exposure martingale in this setting, we make the following definitions:

• We work with graphs whose vertex set is $[n]$.
• $B$ is the set of all pairs of vertices, and $A$ is the set $\{\text{edge}, \text{no edge}\}$, so that $A^B$ corresponds to the set of all graphs with vertex set $[n]$.
• $B_i$ is the set of pairs of vertices from $[i]$.

In particular, $B_{i+1} - B_i$ is the set of all edges with one endpoint $i+1$ and the other endpoint between $1$ and $i$. Two graphs $H, H'$ differ "only in their values on $B_{i+1} - B_i$" if they agree on all edges except this set of edges.

The resulting Lipschitz condition is actually not entirely the vertex Lipschitz condition; it's a weaker, asymmetric version. Here's the weird part:

1. If we obtain $H'$ from $H$ by adding or removing some of the edges $\{1,n\}, \{2,n\}, \dots, \{n-1,n\}$, then $H$ and $H'$ differ only in their values on $B_n - B_{n-1}$, so a Lipschitz graph functional $L$ must satisfy $|L(H) - L(H')| \le 1$.
2. However, $H$ and $H'$ differ only in their values on $B_2 - B_1$ if they agree on everything except possibly the edge $\{1,2\}$. A Lipschitz graph functional, by this definition, could give very different values to graphs that differ only in the edges $\{1,2\}, \{2,3\}, \{2,4\}, \dots, \{2,n\}$.

If we assume that our graph functional is a truly graph-theoretic invariant like chromatic number, and doesn't care which vertices are which, then this extra amount of freedom isn't going to help us. We might as well require that it changes by at most $1$ if we toggle all the edges out of any vertex - since this is true for vertex $n$.

This gives us the condition described in the "short answer" above.