کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662069 1633501 2010 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Unprovability threshold for the planar graph minor theorem
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Unprovability threshold for the planar graph minor theorem
چکیده انگلیسی

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 (27.2269≤γ<30.061). Let P(c) 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|

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 162, Issue 3, December 2010, Pages 175-181