Gauvain Devillez: Computer-assisted research in extremal graph theory

Date of publication: 6. 11. 2023
Mathematics and theoretical computing seminar
10:15 - 12:00
Jadranska 21, predavalnica 3.07

Speaker: Gauvain Devillez (KU Leuven)

Joint work with Hadrien Mélot, Pierre Hauweele, and Sébastien Bonte.

Abstract: Extremal graph theory is the study of bounds on graph invariants. They are usually obtained by identifying a class of graphs, called extremal graphs, that are maximum (or minimum) for the studied invariant, given some constraints. These constraints can vary from fixing the value of another invariant to restricting the graphs to a specific class.

One of the earliest extremal graph theory result is due to Turán and states that the graph with the least edges on $n$ vertices that does not contain an independent set of size $r$ is the Turán graph $T(n,r)$.

To obtain such results one must first identify these extremal graphs and then prove their extremality. However, both steps are made complex by the number of possible graphs that grows exponentially.

This triggered the development of multiple systems to assist in conjecturing for extremal graph theory problem. Among those, GraPHedron, developped by Hadrien Mélot, led to more than 300 additions to the House of Graphs, a popular database of interesting graphs. This discovery system is based on a large database of small graphs, invariant values and graph transformation effects. It uses a geometric approach to discover inequalities between graph invariants.

However, conjectures need proofs. A common type of proof is the proof by transformation. Such proofs function by proving that any non-extremal graph concerned by the conjecture can be transformed into a new graph whose value for the studied invariant is strictly closer to the conjectured bound.

To help with proofs by transformation as well as further study these transformations, we are developing the system TransProof. This system computes a metagraph of transformation. That is, a directed graph with graphs as its vertices and transformations as its arcs.

In this talk, we present a new web interface that allows graph theorists to query PHOEG and manipulate and visualize the outputs, without the need for programming. We then present TransProof and explain the difficulties encountered when building and exploiting the metagraph and the ideas used to handle them.