Friedman's SSCG function
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a simple subcubic graph (SSCG) is a finite simple
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
in which each
vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...
has
degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...
at most three. Suppose we have a sequence of simple subcubic graphs ''G''1, ''G''2, ... such that each graph ''G''''i'' has at most ''i'' + ''k'' vertices (for some integer ''k'') and for no ''i'' < ''j'' is ''G''''i'' homeomorphically embeddable into (i.e. is a
graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
of) ''G''''j''. The
Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is cl ...
proves that subcubic graphs (simple or not) are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. So, for each value of ''k'', there is a sequence with maximal length. The function SSCG(''k'') denotes that length for simple subcubic graphs. The function SCG(''k'') denotes that length for (general) subcubic graphs. The ''SCG'' sequence begins SCG(0) = 6, but then explodes to a value equivalent to fε2*2 in the
fast-growing hierarchy In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy) is an ordinal-indexed family of rapidly increasing functions ''f''α: N → N (where N is the set of ...
. The ''SSCG'' sequence begins SSCG(0) = 2, SSCG(1) = 5, but then grows rapidly. SSCG(2) = 3 × 2(3 × 295) − 8 ≈ 3.241704 × 1035775080127201286522908640066 and its decimal expansion ends in ...11352349133049430008. SSCG(3) is much larger than both
TREE(3) In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding. History The theorem was conjectured by Andrew Vázsonyi and proved b ...
and TREETREE(3)(3). Adam P. Goucher claims there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It's clear that SCG(''n'') ≥ SSCG(''n''), but I can also prove SSCG(4''n'' + 3) ≥ SCG(''n'')."TREE(3) and impartial games , Complex Projective 4-Space
/ref>


See also

*
Goodstein's theorem In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every ''Goodstein sequence'' eventually terminates at 0. Kirby and Paris showed that it is unprovable in Pea ...
*
Paris–Harrington theorem In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic. This has been described by some (suc ...
*
Kanamori–McAloon theorem In mathematical logic, the Kanamori–McAloon theorem, due to , gives an example of an incompleteness in Peano arithmetic, similar to that of the Paris–Harrington theorem. They showed that a certain finitistic theorem in Ramsey theory is not prova ...


Notes


References

{{DEFAULTSORT:Friedman's SSCG function Mathematical logic Theorems in discrete mathematics Order theory Wellfoundedness Graph theory