COMPUTATIONAL MATERIAL FOR
"A Generalization of the Generating Graph"
Author: Andrea Lucchini

1. PURPOSE

This repository contains the GAP code, the Python cross-checks and the
recorded outputs supporting the computational results reported in the
paper: the examples of Sections 3-5 (including the exclusion at order 3^5
and the clique/chromatic number example) and the orbit counts for A_5
used in Section 8.

2. REQUIREMENTS

Verified environment:
  GAP 4.16.0 with packages SmallGrp 1.7.0, GAPDoc 1.6.11,
  PrimGrp 4.0.3, TransGrp 3.6.5.
  Python 3.12.14 (standard library only), for the optional independent
  cross-check.

The exact environment of the reference run is recorded in
reference_environment.txt, reference_operating_system.txt and
reference_python_version.txt.

3. HOW TO RUN

From the root of this repository:

  bash run_all.sh

If the executables are not in the path:

  GAP_BIN=/path/to/gap PYTHON_BIN=/path/to/python3 bash run_all.sh

New results are written to the folder "reproduced"; the reference outputs
supplied here are left untouched. The supplied certificate is verified
BEFORE a new certificate is generated. The script checks stderr and the
final messages of each program, and does not rely only on the GAP exit
code. A successful run ends with the message:

  ALL REPRODUCTION CHECKS PASSED

The Python check is optional; if no interpreter is found, the script
reports this explicitly.

4. CONTENTS

Top level
  run_all.sh                       full run with completion checks
  record_environment.g             GAP version and loaded packages
  reference_environment.txt        GAP environment of the reference run
  reference_operating_system.txt   operating system of the reference run
  reference_python_version.txt     Python interpreter of the reference run
  reference_run.txt                log of the final reference run
  MANIFEST_SHA256.txt              SHA-256 checksums of all files
                                   (except the manifest itself)

graphs/  (Sections 4 and 5: diameter, clique and chromatic number)
  reproduce_graphs.g               groups, overgroups, graph statistics and
                                   exact searches
  verify_certificate.g             independent verifier of the certificate
  *_graph.g                        ordered vertex labels and full adjacency
  colour_certificate.g             maximum clique, 6-colouring and exhaustive
                                   search tree (89 nodes)
  gap_graphs_output.txt            recorded GAP output
  gap_certificate_output.txt       recorded output of the verifier
  independent_check.py             independent reconstruction using
                                   multiplication tables
  *.json                           data produced by the Python check
  cross_check.py                   full comparison between GAP and Python
  *output.txt                      logs of the Python checks and comparison
  methods_graphs.txt               detailed description of the methods
  RUN.txt                          instructions for the individual programs

catalogue/  (Section 3 and orbit counts for Section 8)
  catalogue_and_overgroups.g       p = 2 example, order 729 example, and scan
                                   of the 67 groups of order 243 with all 97
                                   candidate classes H <= Frat(G) in the 29
                                   two-generated groups
  catalogue_and_overgroups.out     recorded output, including overgroups and
                                   witness pairs for each exclusion
  sample_p5.g, sample_p5.out       representative check for p = 5 via
                                   subgroups of the quotient G/H
  a5_orbits.g, a5_orbits.out       all generating pairs of A_5, orbits and
                                   representatives
  a5_independent.py,
  a5_independent.json              independent Python check of the orbit
                                   table
  methodology_notes.txt            notes on filters, conjugacy classes,
                                   overgroups and witnesses

5. MAIN RESULTS REPRODUCED

  Section 4.1:  13 non-isolated vertices, 51 edges, diameter 3.
  Section 4.2:  61 non-isolated vertices, 1203 edges, diameter 4.
  Section 5:    59 non-isolated vertices, 843 edges, diameter 3;
                clique number 5 and chromatic number 6; the impossibility
                of a 5-colouring is certified by an exhaustive search tree
                of 89 nodes with four conflict leaves.
  Order 243:    67 groups in total, 29 of rank two, 97 candidate classes of
                subgroups H <= Frat(G) isomorphic to C3 x C3, of which 29
                are central; none satisfies L_G(H) = {H, G}.
  A_5:          2280 ordered generating pairs, forming 19 Aut(A_5)-orbits
                of size 120; the orbit matrix (by orders of the two
                entries, rows and columns 2, 3, 5) is
                  [[0,1,2],[1,1,4],[2,4,4]],
                with row sums 3, 6, 10.

6. CHECKSUMS

MANIFEST_SHA256.txt lists the SHA-256 checksum of every file in this
repository (except the manifest itself). Checksums identify file content;
the computational claims are established by the executable checks and
their mathematical justification given in the paper.

7. LICENCE AND CITATION

Licence: [to be chosen, e.g. CC BY 4.0 for data, MIT for code]
How to cite: A. Lucchini, A generalization of the generating graph,
[journal, year]; and this repository, [DOI].