Finite Form of The Graph Minor Theorem
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:
- Theorem: For every positive integer n, there is an integer m so large that if G1, ..., Gm is a sequence of finite undirected graphs,
- where each Gi has size at most n+i, then Gj ≤ Gk for some j < k.
(Here, the size of a graph is the total number of its nodes and edges, and ≤ denotes the minor ordering.)
Read more about this topic: Robertson–Seymour Theorem
Famous quotes containing the words finite, form, graph, minor and/or theorem:
“The finite is annihilated in the presence of the infinite, and becomes a pure nothing. So our spirit before God, so our justice before divine justice.”
—Blaise Pascal (1623–1662)
“Average American’s simplest and commonest form of breakfast consists of coffee and beefsteak.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)
“For a country to have a great writer ... is like having another government. That’s why no régime has ever loved great writers, only minor ones.”
—Alexander Solzhenitsyn (b. 1918)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)