Uniformly Random High-Degree Regular Graphs are Asymptotically Almost Surely Link-Irregular

In a recent blog post, David Eppstein proves the existence of regular link-irregular graphs. Those are graphs where all vertices have the same degree and where the subgraphs induced by vertex neighborhoods, called links, are all non-isomorphic. With this, he shows that a conjecture by Akbar Ali, Gary Chartrand and Ping Zhang is false (Conjecture 2.1 of [1] or Conjecture 2.9. of [2]).

David Eppstein prefaces the description of his construction with:

I’m pretty sure sufficiently large and high-degree uniformly random regular graphs provide counterexamples but those are difficult to prove things about. Instead I have the following more complicated construction […]

I was pretty sure of this as well, so I decided to give it a try and ultimately managed to prove the following variant:

For a fixed $r \ge 3$, a uniformly random $(n - 1 - r)$-regular graph $G$ is asymptotically almost surely (a.a.s.) link-irregular.

I think this is a stronger notion of being high-degree than necessary for this to hold, but it is what I could prove without getting too deep into the weeds of uniformly random regular graphs.

I’ll denote the link for $v$ in $G$, defined to be $G[N(v)]$, by $L_G(v)$, or $L(v)$. I’ll also introduce a complementary notion of an unlink that removes a target vertex along with its neighborhood, i.e. $G - N[v]$, denoted by $U_G(v)$ or $U(v)$.

The complemented links of a graph correspond to the unlinks of its complement, as we have $\overline{L_G(v)} = U_{\cG}(v)$. Thus, a graph $G$ is link-irregular if and only if $\overline G$ is unlink-irregular.

Instead of directly working with a high-degree $G$, this allows us to work with its complement $\overline G$, which is a uniformly random $r$-regular graph. To avoid littering everything with overlines, let’s restate what we want to prove in terms of $r$-regular graphs directly:

For a fixed $r \ge 3$, a uniformly random r-regular graph $G$ is a.a.s. unlink-irregular.

Here we’re going to use a result by Béla Bollobás [3], who showed that $G$’s vertices are a.a.s. uniquely identified by their distance seqeuences $(d_i(v))_{i\ge 2}$ where $d_i(v)$ is the number of vertices at a distance $i$ from $v$ in $G$. (We can start at distance $2$, since $d_1(v) = \deg v = r$ for all $v$)

We can partition the vertices of a $r$-regular graph by their distance from $v$ by first removing $v$ and then iteratively removing all vertices with a degree less than $r$. The vertices removed in each iteration are exactly the remaining vertices adjacent to the vertices previously removed. Hence the first iteration removes $v$’s neighbors, the second iteration all distance-$2$ vertices, then the distance-$3$ vertices, etc.

We can write this as the following recurrence: $$\begin{align*} H_0(v) &= G \\ D_0(v) &= \{v\} \\ H_i(v) &= H_{i-1} - D_{i-1}(v) \\ D_i(v) &= \{\, w \in V_{H_i(v)} \mid \deg_{H_i(v)}(w) < r \,\} \end{align*}$$

From this, we obtain the distance sequence for $v$ as $d_i(v) = |D_i(v)|$.

Next, observe that $H_2(v)$ removes $v$ and its neighbors, i.e. $H_2(v) = G - N[v]$, so it is the same as $v$’s unlink $U(v)$. Also note that given any $H_i(v)$ we can compute $D_j(v)$ and $H_j(v)$ for all $j \ge i$. Thus, we can compute $(d_i(v))_{i \ge 2}$ given only $U(v)$. Since we can a.a.s. distinguish all vertices $v$ by their distance sequence $(d_i(v))_{i \ge 2}$ and since we can compute this given only their unlinks $U(v)$, all of G’s unlinks must be a.a.s. non-isomorphic.

References