Package for the girth and eigenvalue of Cayley graphs

Package to compute the girth and the 2nd largest eigenvalue of Cayley graphs based on octonions and quaternions. (Download HERE)

Back

There are four files in the package that the user can interact with:

quick_girth.mgm

quick_eig.mgm

test_eig.mgm

test_girth.mgm

Here is a short description. For more details, see the reference [1] below.

GIRTH

test_girth.mgm --> compute shortest cycles with the following possible options

define boolean isOct

true: graphs are based on octonions.
false: graphs are based on quaterions -> vertex-transitive, only cycle at the identity vertex is necessary

// IMPORTANT: load "quat.mgm" if isOct is false load "octo.mgm" if isOct is true

define prime p (in the Cayley graphs X_{p,q}: valency p+1 if isOct is false, and is p^3+1 else.)
define list of primes QQ

(this list contains the q for which the program will compute shortest cycles on graphs X_{p,q}) --> if only one graph is considered, then simply input QQ:=[value])

degr (only if isOct is false: choose p+1 in most cases)
define integer size_ech (only useful for octonion graphs, that is when isOct is true)

=0: compute a shortest cycle at a all vertices
= 1 : at the identity vertex only
N > 1: is the size of a sample of randomly chosen vertices for which the program will look for a shortest cycle
=-1 : manually load a list of vertices: format is a list of octonions in "normal form")
-100< N <-1 : gives a percentage N% of vertices (randomly chosen) for which the program will look for a shortest cycle

define do_r (bool saying to compute the distribution at each cycle in the sample -- only useful for octonion based graphs)

if false then: at each vertex, find a new shortest cycle of length lower than the shortest one found until now. This is useful to get an upper bound on the girth of large non-vertx transitive graph.
if true: then compute the shortest length at each vertex. This is useful to have the distribution of lengths.

define cyc_length (int): look only for cycle of of length <= cyc_length (will stop the search if no larger cycle than cyc_length is found, o if a cycle of length < cyc_length is found)

quick_girth.mgm --> interactive file. Parameter values are entered after questions are asked. May be easier and more comfortable to begin with

EIGENVALUE

test_eig.mgm --> computation of the 2nd eigenvalue

isOct (boolean)

// IMPORTANT: load "quat.mgm" if isOct is false load "octo.mgm" if isOct is true

p (prime)
QQ (list of primes)
nb_of_iter (positive integer)
interv (integer smaller than nb_of_iter)
degr (only if isOct is false: choose p+1 in most cases)
methode (0 or 1)

quick_eig_output.mgm ---> interactive file where paremeters are input following questions. might be easier

If any questions, comments, please send me an e-mail : xdahan@gmail.com

Bibliography

[1] X. Dahan, Tillich. "On the computation of the girth and of the 2nd largest eigenvalue of Cayley graphs based on quaternions and octonions".
[2] Davidoff, Sarnak, Valette: "Elementary Number theory, Group theory, Ramanujan graphs". LMS Students texts 55. Camb. U. Press
[3] X. Dahan. "Regular graphs of large girth and arbitrary degree". Combinatorica, 2014.
[4] Lubotkzy-Philips-Sarnak "Ramanujan Graphs", Combinatorica.