Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
let d be the degree of each vertex (necessarily all the same)
Find the eigenvalues lambda_1,...,lambda_n
Compute X = max (abs(lambda_1)..abs(lambda_n)) #max of absolute values of all eigenvalues
Return true if X <= 2*sqrt(d-1).
Test to make sure the function works as expected. It should be true for Paley graphs. Add some examples to the docstring.
Add this property to the efficient_properties list.
See:
Lubotzky, Alexander, Ralph Phillips, and Peter Sarnak. "Ramanujan graphs." Combinatorica 8, no. 3 (1988): 261-277.
DOES THE WIKIPEDIA definition differ from the Sarnak definition????!?!?!?!?!?
No, they are the same. 10/11/2021
def is_ramanujan(g):
if not g.is_regular():
return False
d = g.degree()[0]
A = g.adjacency_matrix()
evals = A.eigenvalues()
evals.sort(reverse=True)
X = max(abs(evals[1]),abs(evals[-1]))
See: https://en.wikipedia.org/wiki/Ramanujan_graph
def is_ramanujan(g):
Test to make sure the function works as expected. It should be true for Paley graphs. Add some examples to the docstring.
Add this property to the efficient_properties list.
See: Lubotzky, Alexander, Ralph Phillips, and Peter Sarnak. "Ramanujan graphs." Combinatorica 8, no. 3 (1988): 261-277.
DOES THE WIKIPEDIA definition differ from the Sarnak definition????!?!?!?!?!?
No, they are the same. 10/11/2021
def is_ramanujan(g): if not g.is_regular(): return False d = g.degree()[0] A = g.adjacency_matrix() evals = A.eigenvalues() evals.sort(reverse=True) X = max(abs(evals[1]),abs(evals[-1]))