# Generation algorithms for solving mathematical and chemical problems

## Event details

### When

Apr 09, 2019
from 03:00 PM to 04:00 PM

### Where

Room M2.5, Department of Physics, Informatics and Mathematics, University of Modena and Reggio Emilia

## Dr. Jan Goedgebeur - University of Ghent (Belgium)

Computers are often used in combinatorics to determine if combinatorial objects with given structural or extremal properties exist as these existence problems are often too complex to solve by hand. This is done by designing and implementing generation algorithms which construct combinatorial objects from a given class (typically avoiding the generation of isomorphic copies) and analysing the resulting graphs.
In this talk we will give a short introduction to the exhaustive isomorphism-free generation and large-scale analysis of graphs. We will also give concrete examples of how this has helpedto gain new insights and solve problems in mathematics and chemistry.
Applications in mathematics include the generation of cubic graphs and snarks. We will present a new algorithm for the efficient generation of all non-isomorphic cubic graphs and show how this algorithm can be extended to generate snarks efficiently. A snark is a cyclically $$4$$-edge-connected cubic graph with chromatic index $$4$$ (i.e. the edges cannot be coloured with3 colours). Snarks are of interest since for a lot of conjectures it can be proven that if the conjecture is false, the smallest possible counterexamples will be snarks. Our algorithm enabled us to generate all snarks up to $$36$$ vertices, which was impossible with previous methods. This new list of snarks allowed us to find counterexamples to several published open conjectures.

An application of graph enumeration in chemistry is the generation of the Nobel Prize winning fullerenes (cubic plane graphs where all faces are pentagons or hexagons). We will sketch a new algorithm for the generation of all non-isomorphic fullerenes. Our implementation of this algorithm allowed us to generate all fullerenes up to $$400$$ vertices (there are over $$2.6\times 10^{12}$$ such graphs). This enabled us to prove that the smallest counterexample to the spiral conjecture has $$380$$ vertices.

This talk is based on joint work with Gunnar Brinkmann and Brendan McKay.

Document Actions

Combinatorics 2018 slides