1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338

% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w
\def\title{GIRTH}
\let\==\equiv % congruence sign
\prerequisite{GB\_\,RAMAN}
@* Introduction. This demonstration program uses graphs
constructed by the raman procedure in the {\sc GB\_\,RAMAN} module to produce
an interactive program called \.{girth}, which computes the girth and
diameter of a class of Ramanujan graphs.
The girth of a graph is the length of its shortest cycle; the diameter
is the maximum length of a shortest path between two vertices.
A Ramanujan graph is a connected, undirected graph in which every vertex
@^Ramanujan graphs@>
has degree~p+1, with the property that every eigenvalue of its adjacency
matrix is either $\pm(p+1)$ or has absolute value $\le2\sqrt{\mathstrut p}$.
Exact values for the girth are of interest because the bipartite graphs
produced by raman apparently have larger girth than any other known
family of regular graphs, even if we consider graphs whose existence
is known only by nonconstructive methods, except for the cubic ``sextet''
graphs of Biggs, Hoare, and Weiss [{\sl Combinatorica\/ \bf3} (1983),
@^Biggs, Norman L.@>
@^Hoare, M. J.@>
@^Weiss, Alfred@>
153165; {\bf4} (1984), 241245].
Exact values for the diameter are of interest because the diameter of
any Ramanujan graph is at most twice the minimum possible diameter
of any regular graph.
The program will prompt you for two numbers, p and q. These should
be distinct prime numbers, not too large, with q>2. A graph is
constructed in which each vertex has degree~p+1. The number of
vertices is $(q^3q)/2$ if p is a quadratic residue modulo~q, or
$q^3q$ if p is not a quadratic residue. In the latter case, the
graph is bipartite and it is known to have rather large girth.
If p=2, the value of q is further restricted to be of the form
$104k+(1,3,9,17,25,27,35,43,49,\allowbreak51,75,81)$. This means that the only
feasible values of q to go with p=2 are probably 3, 17, and 43;
the next case, q=107, would generate a bipartite graph with
1,224,936 vertices and 3,674,808 arcs, thus requiring approximately
113 megabytes of memory (not to mention a nontrivial amount of
computer time). If you want to compute the girth and diameter
of Ramanujan graphs for large p and/or~q, much better methods are
available based on number theory; the present program is merely a
demonstration of how to interface with the output of raman.
Incidentally, the graph for p=2 and q=43 turns
out to have 79464 vertices, girth 20, and diameter~22.
The program will examine the graph and compute its girth and its diameter,
then will prompt you for another choice of p and q.
@ Here is the general layout of this program, as seen by the \CEE/ compiler:
@p
#include "gb_graph.h" /* the standard GraphBase data structures */
#include "gb_raman.h" /* Ramanujan graph generator */
@h@#
@<Global variables@>@;
main()
{
printf(
"This program explores the girth and diameter of Ramanujan graphs.\n");
printf("The bipartite graphs have q^3q vertices, and the nonbipartite\n");
printf("graphs have half that number. Each vertex has degree p+1.\n");
printf("Both p and q should be odd prime numbers;\n");
printf(" or you can try p = 2 with q = 17 or 43.\n");
while (1) {
@<Prompt the user for p and q; break if unsuccessful@>;
g=raman(p,q,0L,0L);
if (g==NULL) @<Explain that the graph could not be constructed@>@;
else {
@<Print the theoretical bounds on girth and diameter of g@>;
@<Compute and print the true girth and diameter of g@>;
gb_recycle(g);
}
}
return 0; /* normal exit */
}
@ @<Global...@>=
Graph *g; /* the current Ramanujan graph */
long p; /* the branching factor (degree minus one) */
long q; /* cube root of the graph size */
char buffer[16]; /* place to collect what the user types */
@ @d prompt(s)
{@+printf(s);@+fflush(stdout); /* make sure the user sees the prompt */
if (fgets(buffer,15,stdin)==NULL) break;@+}
@<Prompt...@>=
prompt("\nChoose a branching factor, p: ");
if (sscanf(buffer,"%ld",&p)!=1) break;
prompt("OK, now choose the cube root of graph size, q: ");
if (sscanf(buffer,"%ld",&q)!=1) break;
@ @<Explain that the graph could not be constructed@>=
printf(" Sorry, I couldn't make that graph (%s).\n",@
panic_code==very_bad_specs? "q is out of range":@
panic_code==very_bad_specs+1? "p is out of range":@
panic_code==bad_specs+5? "q is too big":@
panic_code==bad_specs+6? "p is too big":@
panic_code==bad_specs+1? "q isn't prime":@
panic_code==bad_specs+7? "p isn't prime":@
panic_code==bad_specs+3? "p is a multiple of q":@
panic_code==bad_specs+2? "q isn't compatible with p=2":@
"not enough memory");
@* Bounds. The theory of Ramanujan graphs allows us to predict the
girth and diameter to within a factor of 2~or~so.
In the first place, we can easily derive an upper bound on the girth
and a lower bound on the diameter, valid for any $n$vertex regular graph
of degree~$p+1$. Such a graph has at most $(p+1)p^{k1}$ points at
distance~$k$ from any given vertex; this implies a lower bound
on the diameter~$d$:
$$1+(p+1)+(p+1)p+(p+1)p^2+\cdots+(p+1)p^{d1}\;\ge\;n.$$
Similarly, if the girth $g$ is odd, say $g=2k+1$, the points at
distance~$\le k$ from any vertex must be distinct, so we have
$$1+(p+1)+(p+1)p+(p+1)p^2+\cdots+(p+1)p^{k1}\;\le\;n;$$
and if $g=2k+2$, at least $p^k$ further points must exist at distance
$k+1$, because the $(p+1)p^k$ paths of length $k+1$ can end at
a particular vertex at most $p+1$ times. Thus
$$1+(p+1)+(p+1)p+(p+1)p^2+\cdots+(p+1)p^{k1}+p^k\;\le\;n$$
when the girth is even.
In the following code we let $pp=p^{dl}$ and
$s=1+(p+1)+\cdots+(p+1)p^{dl}$.
@<Compute the ``trivial'' bounds gu and dl on girth and diameter@>=
s=p+2;@+dl=1;@+pp=p;@+gu=3;
while (s<n) {
s+=pp;
if (s<=n) gu++;
dl++;
pp*=p;
s+=pp;
if (s<=n) gu++;
}
@ When p>2, we can use the theory of integral quaternions to derive a lower
bound on the girth of the graphs produced by raman. A path of length~$g$
from a vertex to itself exists if and only if there is an integral
quaternion $\alpha=a_0+a_1i+a_2j+a_3k$ of norm $p^g$ such that
the $a$'s are not all multiples of~$p$, while
$a_1$, $a_2$, and $a_3$ are multiples of~$q$ and $a_0\not\=a_1\=a_2\=a_3$
(mod~2). This means we have integers $(a_0,a_1,a_2,a_3)$ with
$$a_0^2+a_1^2+a_2^2+a_3^2=p^{\,g},$$ satisfying the stated properties
mod~$q$ and mod~2.
If $a_1$, $a_2$, and $a_3$ are even, they cannot all be zero so
we must have $p^{\,g}\ge1+4q^2$; if they are odd, we must have
$p^{\,g}\ge4+3q^2$. (The latter is possible only when $g$ is odd and
$p\bmod4=3$.) Since $n$ is roughly proportional to~$q^3$, this means
$g$ must be at least about ${2\over3}\log_p n$. Thus $g$~isn't
too much less than the maximum girth possible in any regular graph,
which we have shown is at most about $2\log_p n$.
When the graph is bipartite we can, in fact, prove that $g$ is
approximately ${4\over3}\log_p n$. The bipartite case occurs if and
only if $p$ is not a quadratic residue modulo~q; hence the
number~$g$ in the previous paragraph must be even, say $g=2r$. Then
$p^{\,g}\bmod4=1$, and $a_0$ must be odd. The congruence $a_0^2\=p^{2r}$
(mod~$q^2$) implies that $a_0\=\pm p^r$, because all numbers
relatively prime to $q^2$ are powers of a primitive root. We can
assume without loss of generality that $a_0=p^r2mq^2$, where
$0<m<p^r/q^2$; it follows in particular that $p^r>q^2$. Conversely,
if $p^rq^2$ can be written as a sum of three squares
$b_1^2+b_2^2+b_3^2$, then
$p^{2r}=(p^r2q^2)^2+(2b_1q)^2+(2b_2q)^2+(2b_3q)^2$ is a
representation of the required type. If $p^rq^2$ is a positive
integer that cannot be represented as a sum of three squares, a
wellknown theorem of Legendre tells us that $p^rq^2=4^ts$, where
$s\=7$ (mod~8). Since $p$ and $q$ are odd, we have $t\ge1$; hence
$p^r2q^2$ is odd. If $p^r2q^2$ is a positive odd integer, Legendre's
theorem tells us that we can write $2p^r4q^2=b_1^2+b_2^2+b_3^2$;
hence $p^{2r}=(p^r4q^2)^2+ (2b_1q)^2+(2b_2q)^2+(2b_3q)^2$. We
conclude that the girth is either $2\lceil\log_pq^2\rceil$ or
$2\lceil\log_p2q^2\rceil$. (This explicit calculation, which makes our
program for calculating the girth unnecessary or at best redundant in
the bipartite case, is due to G. A. Margulis and, independently, to
@^Margulis, Grigori{\u\i} Aleksandrovich@>
@^Biggs, Norman L.@>
@^Boshier, A. G.@>
Biggs and Boshier [{\sl Journal of Combinatorial Theory\/ \bf B49}
(1990), 190194].)
A girth of 1 or 2 can occur, since these graphs might have selfloops
or multiple edges if p is sufficiently large.
@<Compute a lower bound gl on the girth@>=
if (bipartite) {@+long b=q*q;
for (gl=1,pp=p;pp<=b;gl++,pp*=p) ; /* iterate until $p^{\,g}>q^2$ */
gl+=gl;
}@+else {@+long b1=1+4*q*q, b2=4+3*q*q; /* bounds on $p^{\,g}$ */
for (gl=1,pp=p;pp<b1;gl++,pp*=p) {
if (pp>=b2 && (gl&1) && (p&2)) break;
}
}
@ Upper bounds on the diameter of any Ramanujan graph can be derived
as shown in the paper by Lubotzky, Phillips, and Sarnak in
@^Lubotzky, Alexander@>
@^Phillips, Ralph Saul@>
@^Sarnak, Peter@>
{\sl Combinatorica \bf8} (1988), page~275. (However, a slight correction
to their proof is necessarytheir parameter~$l$ should be~odd
when $x$ and~$y$ lie in different parts of a bipartite graph.)
Their argument demonstrates that $p^{(d1)/2}<2n$ in the
nonbipartite case and $p^{(d2)/2}<n$ in the bipartite case; therefore
we obtain the upper bound $d\le 2\log_p n+O(1)$, which is about twice the lower
bound that holds in an arbitrary regular graph.
@<Compute an upper bound du on the diameter@>=
{@+long nn=(bipartite? n: 2*n);
for (du=0,pp=1; pp<nn; du+=2,pp*=p) ;
@<Decrease du by 1, if $pp/nn\ge\sqrt p$@>;
if (bipartite) du++;
}
@ Floating point arithmetic might not be accurate enough for the test
required in this section. We avoid it by using an allinteger method
analogous to Euclid's algorithm, based on the continued fraction for
$\sqrt p$ [{\sl Seminumerical Algorithms}, exercise 4.5.312]. In the
loop here we want to compare nn/pp to $(\sqrt p+a)/b$, where $\sqrt p+a
>b>0$ and $pa^2$ is a multiple of~$b$.
@<Decrease du...@>=
{@+long qq=pp/nn;
if (qq*qq>p) du;
else if ((qq+1)*(qq+1)>p) { /* $qq=\lfloor\sqrt p\,\rfloor$ */
long aa=qq, bb=paa*aa, parity=0;
pp=qq*nn;
while (1) {
long x=(aa+qq)/bb, y=nnx*pp;
if (y<=0) break;
aa=bb*xaa; /* now $0<aa<\sqrt p$ */
bb=(paa*aa)/bb;
nn=pp;@+pp=y;
parity^=1;
}
if (!parity) du;
}
}
@ @<Print the theoretical bounds on girth and diameter of g@>=
n=g>n;
if (n==(q+1)*q*(q1)) bipartite=1;
else bipartite=0;
printf(
"The graph has %ld vertices, each of degree %ld, and it is %sbipartite.\n",
n,p+1,bipartite? "": "not ");
@<Compute the ``trivial'' bounds gu and dl on girth and diameter@>;
printf("Any such graph must have diameter >= %ld and girth <= %ld;\n",
dl,gu);
@<Compute an upper bound du on the diameter@>;
printf("theoretical considerations tell us that this one's diameter is <= %ld",
du);
if (p==2) printf(".\n");
else {
@<Compute a lower bound gl on the girth@>;
printf(",\nand its girth is >= %ld.\n",gl);
}
@ We had better declare all the variables we've been using so freely.
@<Global...@>=
long gl,gu,dl,du; /* theoretical bounds */
long pp; /* power of $p$ */
long s; /* accumulated sum */
long n; /* number of vertices */
char bipartite; /* is the graph bipartite? */
@*Breadthfirst search. The graphs produced by raman are symmetrical, in
the sense that there is an automorphism taking any vertex into any
other. Each vertex $V$ and each edge $P$ corresponds to a $2\times2$
matrix, and the path $P_1P_2\ldots P_k$ leading from vertex~$V$ to
vertex $VP_1P_2\ldots P_k$ has the same properties as the path leading
from vertex~$U$ to vertex $UP_1P_2\ldots P_k$. Therefore we can find
the girth and the diameter by starting at any vertex $v_0$.
We compute the number of points at distance $k$ from $v_0$ for
all $k$, by explicitly forming a linked list of all such points.
Utility field link is used for the links. The lists
terminate with a nonnull sentinel value, so that we can also
use the condition link==NULL to tell if a vertex has been
encountered before. Another utility field, dist, contains the
distance from the starting point, and back points to a
vertex one step closer.
@d link w.V /* the field where we store links, initially NULL */
@d dist v.I /* the field where we store distances, initially 0 */
@d back u.V /* the field where we store backpointers, initially NULL */
@<Compute and print the true girth and diameter of g@>=
printf("Starting at any given vertex, there are\n");
{@+long k; /* current distance being generated */
long c; /* how many we've seen so far at this distance */
register Vertex *v; /* current vertex in list at distance $k1$ */
register Vertex *u; /* head of list for distance $k$ */
Vertex *sentinel=g>vertices+n; /* nonzero link at end of lists */
long girth=999; /* length of smallest cycle found, initially infinite */
k=0;
u=g>vertices;
u>link=sentinel;
c=1;
while (c) {
for (v=u,u=sentinel,c=0,k++;v!=sentinel;v=v>link)
@<Place all vertices adjacent to v onto list u, unless they've
been encountered before, increasing c whenever the list grows@>;
printf("%8ld vertices at distance %ld%s\n", c, k, c>0? ",": ".");
}
printf("So the diameter is %ld, and the girth is %ld.\n",k1,girth);
}
@ @<Place all...@>=
{@+register Arc *a;
for (a=v>arcs;a;a=a>next) {@+register Vertex *w;
/* vertex adjacent to v */
w=a>tip;
if (w>link==NULL) {
w>link=u;
w>dist=k;
w>back=v;
u=w;
c++;
}@+else if (w>dist+k<girth && w!=v>back)
girth=w>dist+k;
}
}
@* Index. Finally, here's a list that shows where the identifiers of this
program are defined and used.
