Finite form of the graph minor theorem
Statement
Friedman, Robertson & Seymour (1987) showed that the following theorem exhibits the independence phenomenon by being unprovable in various formal systems that are much stronger than Peano arithmetic, yet being provable in systems much weaker than ZFC:
(Here, the size of a graph is the total number of its vertices and edges, and ≤ denotes the minor ordering.)
Friedman uses this result on simple subcubic graphs to construct the fast-growing function, SSCG.
Further reading
- Wikipedia, page 351769, revision 1361823548, Robertson–Seymour theorem, section Finite form of the graph minor theorem. adopted
About this page
| Tag | WXNTPQGJ38 |
|---|---|
| URI | m2://WXNTPQGJ38 |
| Kind | statement, theorem |
| Writing | W0 stub |
| Status | This copy of the site has no build data. Run m2 status WXNTPQGJ38. |
| Changed | 4 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- edge uses out: each definition that the statement needs (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.