1

Let $G=(V,E)$ be a random undirected, unweighted graph where each vertex $v\in V$ has degree $n>1.$ Let the $k$-sphere $S(v_0,k)=\{\,v\mid v\in V,\;d(v,v_0)=k\,\}$ of $v_0$ be the set of vertices at distance $k$ from $v_0$.

How can we estimate the sphere size as $k$ grows? Initially, $|S(v_0,k)|\approx n(n-1)^{k-1}\ll|V|$ as the neighbors of each vertex in the sphere, except for the one that leads back to $v_0$ are unlikely to be part of $S(v_0,0)\cup S(v_0,1)\cup\cdots\cup S(v_0,k-1)$. But as $k$ grows, this probability becomes higher and it's hard for me to estimate how this continues.

I am interested in this problem as a part of studying the distribution of vertices in the search spaces of combinatorial puzzles, such as sliding-tile puzzles or the Rubik's Cube.

FUZxxl
  • 9,307
  • 1
    There are probably some results on diameter in random regular graphs that would imply a bound here - I think the reality is that your estimate of $|S(v_0,k)|$ is nearly correct almost the whole way up until we've seen almost all $|V|$ vertices, dropping off randomly for the last few stragglers. But this is unlikely to describe what happens for combinatorial puzzles! – Misha Lavrov Jan 17 '24 at 15:35
  • @MishaLavrov Observations on combinatorial search spaces suggest that $\log S(v_0, k)$ follows sort of a parabola shape. The exponential approximation only really works as long as $S(v_0, k)\ll|V|$. – FUZxxl Jan 17 '24 at 15:50
  • 1
    That makes a lot of sense; random regular graphs have very few short cycles, and Rubik's cubes have plenty (for instance, twist a face, twist the opposite face, and undo both; in general; any puzzle where operations sometimes commute will have many short cycles). – Misha Lavrov Jan 17 '24 at 15:53
  • @MishaLavrov That's certainly a point, but on the other hand, the number of cycles grows much slower than $(n-1)^k$. We account for it in this model by computing a branching factor $b$ and using it in place of $(n-1)$ to give $|S(v_0,k)|\approx nb^{k-1}$. – FUZxxl Jan 18 '24 at 10:24

0 Answers0