Abstract

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture : ‘there is a number a>0 such that for all k≥3, and all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant . Let P be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G1,G2,…,GN are unlabelled planar graphs with Gi

Cite Plain text    BibTeX    Formatted text Zotero EndNote Reference Manager RefWorks

Options Mark as duplicate Find it on Scholar Request removal from index Revision history

Edit