back to table · edit · history · where entries came from · files · download
5101 bytes, as of the version from 2026-10-29 12:06 (current). Recorded here, not run.
"""Reciprocal Ihara zeta polynomials of connected graphs -- numberdb.org/T608.
Run with SageMath (including nauty) and the numberdb package:
sage -pip install numberdb
sage -python generate.py # verify every stored entry
sage -python checks.py # independent offline checks
sage -python dry_run.py generate.py # exactness and size checks
Writing entries to the existing draft, without making it public:
NUMBERDB_API_KEY=... sage -python generate.py --fill
Default enumeration is every simple connected graph of minimum degree two
on three through six vertices. See argument-selection.md for the discrete
family, noncanonical extent, and archived skill manifest. The named Sage
canonical labeller is fixed to match T237 and T238. Graph generation uses
nauty; polynomial computation uses a Leibniz determinant over ZZ[u].
There is no division, floating point arithmetic, or precision parameter.
"""
import os
import sys
from functools import lru_cache
from itertools import permutations
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.graphs.graph import Graph
from sage.graphs.graph_generators import graphs
R = PolynomialRing(ZZ, 'u')
u = R.gen()
def graph_key(graph):
return graph.canonical_label(algorithm='sage').graph6_string()
@lru_cache(maxsize=None)
def selected_keys(max_vertices=6):
"""Order all eligible isomorphism classes by n, m, graph6 bytes."""
rows = []
for n in range(3, max_vertices + 1):
for graph in graphs.nauty_geng('%d -c -d2' % n):
rows.append((n, graph.size(), graph_key(graph)))
rows.sort()
keys = tuple(row[2] for row in rows)
assert len(keys) == len(set(keys))
return keys
def bass_polynomial(graph):
"""Expand (1-u^2)^(m-n) det(I-uA+u^2(D-I)) exactly."""
vertices = sorted(graph.vertices(sort=False))
n, m = graph.order(), graph.size()
assert n >= 3 and graph.is_connected() and min(graph.degree()) >= 2
matrix_rows = [
[1 + (graph.degree(v)-1)*u**2 if v == w
else -u if graph.has_edge(v, w) else R.zero()
for w in vertices] for v in vertices]
determinant = R.zero()
for perm in permutations(range(n)):
inversions = sum(perm[i] > perm[j]
for i in range(n) for j in range(i+1, n))
term = R(-1 if inversions % 2 else 1)
for i, j in enumerate(perm):
term *= matrix_rows[i][j]
if not term:
break
determinant += term
return (1-u**2)**(m-n) * determinant
@lru_cache(maxsize=1)
def familiar_names():
names = {}
def add(graph, label):
key = graph_key(graph)
names[key] = names[key] + ' ' + label if key in names else label
for n in range(3, 7):
add(graphs.CycleGraph(n), 'The cycle graph $C_%d$.' % n)
add(graphs.CompleteGraph(n), 'The complete graph $K_%d$.' % n)
for a, b in ((2, 3), (2, 4), (3, 3)):
add(graphs.CompleteBipartiteGraph(a, b),
'The complete bipartite graph $K_{%d,%d}$.' % (a, b))
add(Graph([(0,1),(0,2),(0,3),(1,2),(2,3)]),
'The diamond graph, obtained by deleting one edge from $K_4$.')
add(Graph([(0,1),(1,2),(2,0),(0,3),(3,4),(4,0)]),
'The bowtie graph, consisting of two triangles sharing one vertex.')
add(Graph([(0,1),(1,2),(2,0),(3,4),(4,5),(5,3),(0,3)]),
'The barbell graph consisting of two triangles joined by a bridge.')
add(Graph([(0,1),(1,2),(2,0),(3,4),(4,5),(5,3),(0,3),(1,4),(2,5)]),
'The triangular prism graph.')
add(graphs.CompleteMultipartiteGraph([2,2,2]), 'The octahedral graph.')
return names
class ReciprocalIhara(numberdb.Generator):
table = 'T608'
parameters = ('g',)
type = 'Z[]'
rigour = 'exact'
files = ('generate.py', 'checks.py', 'check.py', 'dry_run.py',
'argument-selection.md', 'numerical-evidence.json',
'skill-evidence.json', 'neighbor-keys.json', 'sources.md')
def enumerate(self, max_vertices=6):
for key in selected_keys(max_vertices):
yield {'g': key}
def value(self, params, digits):
key = params['g']
value = bass_polynomial(Graph(key))
comment = familiar_names().get(key)
return {'number': value, 'comment': comment} if comment else value
def configure_stdin():
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
key = sys.stdin.read().strip()
if '=' in key and key.split('=', 1)[0].isupper():
key = key.split('=', 1)[1].strip().strip('\"\'')
numberdb.configure(api_key=key)
if __name__ == '__main__':
configure_stdin()
generator = ReciprocalIhara()
if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(generator.publish(message='Compute exact Ihara reciprocals for all 76 eligible small graphs'))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)