generate.py

back to table · edit · history · where entries came from · files · download

4605 bytes, as of the version from 2026-10-27 11:53 (current). Recorded here, not run.

"""Algebraic connectivity of connected graphs -- numberdb.org/T547.

Run with SageMath 10.9 and the numberdb Python client:
    sage -pip install numberdb
    sage -python generate.py             # verify every stored entry
    sage -python generate.py --fill       # fill this draft with an API key

NUMBERDB_API_KEY authenticates private drafts. For the campaign wrapper,
NUMBERDB_KEY_FROM_STDIN=1 reads that key from stdin, and NUMBERDB_PUBLISH=1
requests a fill. Filling entries does not offer or publish the table.

The only free parameter is the connected simple graph isomorphism class.
All classes on 2 through 6 vertices are enumerated, with Sage canonical graph6
identifiers. See argument-selection.md for the finite-bound justification.
The combinatorial Laplacian is D-A; algebraic connectivity is its least
positive eigenvalue, selected exactly in AA. Its minimal polynomial decides
rationality. Irrational roots are converted to certified MPFI intervals at
numberdb.bits(digits, losing=80); the default is 413 bits. The checks measure
the widths and prove the printed intervals isolate the least positive root.
"""
import os
import sys
from functools import lru_cache
import numberdb.sage as numberdb
from sage.graphs.graph import Graph
from sage.graphs.graph_generators import graphs
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.qqbar import AA
from sage.rings.real_mpfi import RealIntervalField

MAX_ORDER = 6
WORKING_GUARD = 80


def canonical_key(graph):
    return graph.canonical_label(algorithm='sage').graph6_string()


@lru_cache(None)
def graph_keys(max_order=MAX_ORDER):
    return tuple(key for n in range(2, max_order + 1)
                 for key in sorted({canonical_key(g)
                     for g in graphs.nauty_geng(str(n) + ' -c')}))


@lru_cache(None)
def names():
    result = {}
    def add(graph, name):
        key = canonical_key(graph)
        result.setdefault(key, []).append(name)
    for n in range(2, MAX_ORDER + 1):
        add(graphs.CompleteGraph(n), 'the complete graph $K_%d$' % n)
        add(graphs.PathGraph(n), 'the path $P_%d$' % n)
        if n >= 3:
            add(graphs.CycleGraph(n), 'the cycle $C_%d$' % n)
        for a in range(1, n // 2 + 1):
            add(graphs.CompleteBipartiteGraph(a, n-a),
                'the complete bipartite graph $K_{%d,%d}$' % (a,n-a))
    return {key: 'This is ' + ', also '.join(labels) + '.'
            for key,labels in result.items()}


@lru_cache(None)
def algebraic_connectivity(key):
    graph = Graph(key, format='graph6')
    assert graph.order() >= 2 and graph.is_connected()
    polynomial = graph.laplacian_matrix().charpoly()
    roots = polynomial.roots(ring=AA)
    assert sum(mult for root,mult in roots) == graph.order()
    assert [(root,mult) for root,mult in roots if root == 0] == [(AA(0),1)]
    assert all(root >= 0 for root,mult in roots)
    return min(root for root,mult in roots if root > 0)


class AlgebraicConnectivity(numberdb.Generator):
    table = 'T547'
    parameters = ('g',)
    type = 'R'
    digits = 100
    rigour = 'proven'
    files = ('generate.py', 'checks.py', 'argument-selection.md')

    def enumerate(self, max_order=MAX_ORDER):
        for key in graph_keys(max_order):
            yield {'g': key}

    def value(self, params, digits):
        key = params['g']
        root = algebraic_connectivity(key)
        minimal = root.minpoly()
        if minimal.degree() == 1:
            value = -QQ(minimal[0]) / QQ(minimal[1])
            assert value.denominator() == 1
            value = ZZ(value)
        else:
            field = RealIntervalField(numberdb.bits(digits, losing=WORKING_GUARD))
            value = field(root)
            assert value.lower() > 0
            assert value.absolute_diameter() < QQ(1)/ZZ(10)**(digits+10)
        record = {'number': value}
        if key in names():
            record['comment'] = names()[key]
        return record


if __name__ == '__main__':
    if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
        token = sys.stdin.read().strip()
        if '=' in token and token.split('=',1)[0].isidentifier():
            token = token.split('=',1)[1].strip().strip('\"\'')
        numberdb.configure(api_key=token)
    generator = AlgebraicConnectivity()
    if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
        print(generator.publish(message='Fill all 142 connected graphs of orders two through six'))
    else:
        report = generator.verify(sample=None)
        print(report)
        sys.exit(0 if report.ok else 1)