6
$\begingroup$

Let $X=(V,E)$ be a finite, connected graph on $n$ vertices, endowed with its graph metric $d$. The average squared distance of $X$ is $avg(d^2)=\frac{1}{n(n-1)}\sum_{x,y\in V,x\neq y} d(x,y)^2$; it satisfies the obvious bound $avg(d^2)\leq diam(X)^2$, where $diam(X)$ is the diameter of $X$.

Now assume that $X$ is vertex-transitive. My intuition is that, in this case, for ``many'' pairs of vertices, the distance is much smaller than the diameter, which should entail an inequality $avg(d^2)\leq \lambda(diam(X))^2$, where $\lambda<1$ is some constant, maybe depending only on the common degree of the vertices. Is this intuition correct? If yes, can $\lambda$ be estimated?

EDIT: Thanks to all for your input. The example of the complete graph is somewhat embarrassing, meaning that the OP was poorly formulated. As Aaron sort of guessed, I'm interested in families of $k$-regular graphs ($k$ fixed) with number of vertices increasing to infinity. So the new question would be: does a bound $avg(d^2)\leq \lambda(diam(X))^2$ hold for $|V|$ large enough? Observe that, for vertex-transitive graphs, the lower bound $avg(d^2)\geq\frac{(diam X)^2}{8}$ holds: see proposition 3.4 in http://toctest.cs.uchicago.edu/articles/v005a006/v005a006.pdf

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ There's no such $\lambda<1$. In a hypercube graph on $2^m$ vertices, the diameter is $\lfloor m/2 \rfloor$, and all but $o(m)$ pairs of vertices are at distance $(m/2) - O(m^{\frac12+\epsilon})$, so $\lambda$ must be $1 - O(m^{\frac12-\epsilon})$ which gets arbitrarily close to 1 as $m \rightarrow\infty$. Simpler yet, on the complete graph the average and maximal $d^2$ are both equal 1. $\endgroup$
    – Noam D. Elkies
    Commented Jun 15, 2011 at 6:05
  • $\begingroup$ The answer has already been shown to be no if the common degree can be large, even if the diameter too is large. Is there a simple example where the degree is bounded? The De Bruijn graph has average distance roughly equal to the diameter, but is not quite vertex transitive. I guess the $n$ by $n$ by $n$ Rubik's cube does it, but it's a bit difficult to analyze. $\endgroup$
    – Johan Wästlund
    Commented Jun 15, 2011 at 8:30
  • 1
    $\begingroup$ @Noam - isn't the diameter of the hypercube equal to m? $\endgroup$
    – Gordon Royle
    Commented Jun 15, 2011 at 8:47
  • $\begingroup$ @Gordon-Royle: You are right. I was thinking of the quotient of the hypercube by the antipodal involution. I'd edit the comment to correct this but there doesn't seem to be a way to do that here... $\endgroup$
    – Noam D. Elkies
    Commented Jun 15, 2011 at 14:17

3 Answers 3

Reset to default
3
$\begingroup$

For Random 3-regular graphs \lambda is asymptotically 1. I suspect that for Ramanujan graphs it will be 1 as well?

Regarding random graphs papers to look are papers citing Bollobas and de la Vega, Combinatorica 2 (1982), 125-134. http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf which does not contain it but a related result.

A reference which contains the claim is Remco van der Hofsted's book: see Theorem 10.15 and Theorm 10.16 (in the latest version on his webpage).

Improve this answer
$\endgroup$
3
  • $\begingroup$ That is interesting! Do you have a reference? $\endgroup$
    – Aaron Meyerowitz
    Commented Jun 16, 2011 at 18:39
  • $\begingroup$ I can only repeat Aaron's question... $\endgroup$
    – Alain Valette
    Commented Jun 19, 2011 at 5:28
  • $\begingroup$ In trying to track this down a bit I noticed an article sciencedirect.com/science/article/pii/S0095895684710549 mentioning constructions of Ramanujan graphs given as Cayley graphs of PGL$_2$ or PSL$_2$ over finite fields, with respect to very simple generators. This makes me think that it is related to what I mentioned. $\endgroup$
    – Aaron Meyerowitz
    Commented Jun 19, 2011 at 15:45
3
$\begingroup$

Perhaps I am missing something, but it seems to me that we can do the hypercube calculations exactly.

In the hypercube of valency $m$, pick an arbitrary vertex. Then there are ${m}\choose{1}$ vertices at distance 1, ${m}\choose{2}$ at distance 2, etc and so the total of the distances squared is $$ \sum_{i=1}^{i=m} {m \choose i} i^2 = 2^{m-2} m(m+1) $$ The average distance squared is then this value divided by $2^m-1$, while the diameter squared is $m^2$ and so the ratio is $$ \lambda_m = \frac{ (m+1) 2^{m-2} }{ m (2^m - 1) } $$ and as $m$ tends to infinity this ratio tends to $1/4$ (which is exactly the value you get by assuming that "most" vertices are at distance $m/2$ from each other).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Right, this is not a counterexample. I meant the degree-$m$ graph on $2^{m/2}$ obtained from the hypercube by identifying antipodal vertices. The resulting sum might not have a "closed-form" answer, but $\lambda$ will be $1 - O(m^{-\frac12}) \rightarrow 1$. [I wrote $1 - O(m^{-\frac12+\epsilon})$ earlier because that's easier to show but in fact the $\epsilon$ is not necessary.] $\endgroup$
    – Noam D. Elkies
    Commented Jun 15, 2011 at 15:16
  • $\begingroup$ Ah, yes... the OP was asking for a universal constant which as you show does not exist. It might be interesting to compute the values for various families of distance-transitive graphs and see which do admit such a constant and which don't. $\endgroup$
    – Gordon Royle
    Commented Jun 15, 2011 at 17:03
2
$\begingroup$

revised

It is not always (perhaps not even "usually") the case that "most" pairs of vertices are "much" less than the diameter apart. Based on meager experience (see below), it seems common that "most" pairs are "almost" the diameter apart, but relatively few are exactly that far apart. Asking that the average distance (ad) or square root of the average squared distance (rasd) are very close to the diameter (either with difference less than 1 or ratio going to 1$ is a much stronger condition.

A small experiment I tried (for degree 3 or 4) was: choose two permutations of $t$ objects, then look at the group and Cayley graph determined by these two (and their inverses.) For my choices (all with $t \le 9$) the group was usually $A_t$ or $S_t.$ The ratio of the ad and rasd to the diameter seemed (in the best cases) to increase with $t.$ Three examples:

  1. The permutations $(1 2)(3 4) (5 6)$ and $(1 7 8 5 3 4 6 9 2)$ generate $S_9$ creating a graph of degree $3$ with $9!=362880$ vertices and diameter $22.$ The distribution of distances is $$3, 6, 12, 24, 46, 90, 176, 344, 672, 1310, 2531, 4867, 9270, 17201, 30867, 51354$$ $$ 75493, 86173, 61359, 19347, 1699, 35$$ leading to $17.03$ and $ 17.14$ for the ad and rasd (this was the best of 5 trials)

  2. The permutations $(1 2 3 4 5 6 7 8)$ and $( 1 6 7 2 3 5 8 4)$ generate $S_8$ creating a graph of degree $4$ with $8!=40320$ vertices and diameter $13.$ The distribution of distances is $$4, 12, 34, 94, 250, 648, 1642, 3939, 8275, 12468, 9843, 2998, 112$$ leading to $9.76$ and $ 9.86$ for the ad and rasd (this was the best of 15 trials)

  3. Two random 7-cycles will usually generate $A_7$ (2520 vertices, degree 4). Out of 100 trials, 6 came out with diameter $9$ and distance distribution $4, 12, 34, 92, 252, 573, 936, 582, 34$ giving ad and rasd of $6.6336$ and $ 6.7456.$ (and none were better.) Perhaps someone can figure out (rather than observe from random trials) what optimum choices are for two $t$-cycles or a $t$-cycle and an involution.

Following a suggestion by @Gerhard: A Rubik's cube (with unmarked center faces) is known to have $n=43,252,003,274,489,856,000$ positions. There are $18$ basic moves (counting a half turn as a single move). This defines a vertex transitive graph of degree 18. It was long suspected, and now is known, that this graph has diameter 20. The team which proved this released numbers showing approximately how many nodes are at distance $d$ from a given one. The numbers, (being approximate) do not add exactly to the correct value of $n$ although they come close. After $1,18$ each number is roughly $13$ times the previous until the last few where the ratios are about $12,2.5,0.05$ and finally $2\cdot10^{-10}$ Using the given numbers, the ad and rasd are both about $17.$

Here are some final comments on fixed degree: Fix a degree $k$ and suppose only that a graph is regular of degree $k$, $x$ be a particular vertex and all vertices are within $m$ of $x.$ The number at distance $d$ is at most $k(k-1)^{d-1}.$ It seems to clear that we want to maximize the number of vertices in the graph to have a relatively large average (squared) distance from $x$. If this count was exact for all $d \le m$ then the proportion at maximal distance would be close to $1-\frac1k.$ Then, for fixed $k$, the average distance and average squared distance would exceed $(1-\epsilon)m$ and $(1-\epsilon)m^2$ for large enough $m$. However, the diameter of the entire graph might be as large as $2m.$ Diameter of $m$ can only happen in a very few cases and not much is known about how close one can come to this in general. This paper about the degree diameter problem mentions a lower bound of $(\frac{k}{1.57})^m$ for the number of vertices. However I don't know the number of vertices at maximal distance.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This sounds similar to a question asked recently. My memory says that the accepted answer was along the lines of "The beahviour of the distribution of distances in the examples noted are for Coxeter type graphs; they should not be considered representative of the graphs under consideration". If I remember more I will search for the question and link to it. Gerhard "Does Not Remember The Territory" Paseman, 2011.06.15 $\endgroup$
    – Gerhard Paseman
    Commented Jun 15, 2011 at 21:18
  • $\begingroup$ 61443 Is the question number, and it mentions the 20 move solutions to the Rubik's Cube. It talks about average distance vs diameter in Cayley graphs. Perhaps someone not using a phone can provide a link. Gerhard "Can Sometimes Search The Territory" Paseman, 2011.06.15 $\endgroup$
    – Gerhard Paseman
    Commented Jun 16, 2011 at 0:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .