University of Cambridge > > Formalisation of mathematics with interactive theorem provers  > Formalising Turán's Graph Theorem in Isabelle/HOL

Formalising Turán's Graph Theorem in Isabelle/HOL

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Angeliki Koutsoukou-Argyraki.

Hybrid talk (please see abstract for link)

In 1941, Paul Turán discovered that any undirected, simple graph with n vertices that does not contain a p-clique, contains at most (1-1/(p-1))n^2/2 edges. Turán’s graph theorem is considered to be a fundamental result in graph theory and the origin of the field of extremal graph theory. In my formalisation of Turán’s graph theorem in Isabelle/HOL, I have first directly adapted Turán’s original proof. Then, I discovered a seemingly small change to the textbook proof on paper which significantly decreases the size of the formalisation and leads to an arguably more beautiful proof.

WATCH ONLINE HERE : Meeting ID: 379 992 884 209 Passcode: TYR8 Sh

This talk is part of the Formalisation of mathematics with interactive theorem provers series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity