Axiomatic strengths of certain mathematical statements

• Main Author: Koh, Heer Tern
• Other Authors: Ng Keng Meng
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Science::Mathematics::Mathematical logic; Science::Mathematics::Discrete mathematics
• Online Access: https://hdl.handle.net/10356/144834
• Institution: Nanyang Technological University

Reverse mathematics is primarily interested in what set existence axioms are necessary in a proof of a theorem. Much work has been done in classifying graph colouring theorems, studying k-regular graphs, k-chromatic graphs and forests. This report takes inspiration from an old paper by Bean and studies graph colouring theorems restricted to planar graphs. The report shows that for any n, the n-colouring theorem of planar graphs is equivalent to wkl. Further analysis of related principles, obtained by restricting the planar graphs in question to be connected, or with computable planar drawings also yield similar results. However, many of the proofs of equivalence are non-uniform; utilising tools of Weihrauch reducibility, this report also proves that in many instances, such non-uniformity is necessary.