[FOM] 274:Subcubic Graph Numbers

Sat Apr 1 11:23:41 EST 2006

We now discuss numbers associated with the graph minor theorem applied to
finite simple subcubic graphs.

A simple graph is an undirected graph without loops and without multiple
edges. Subcubic means that every vertex has valence at most 3.

Robertson and Seymour remarked in paper [1] that they could use subcubic
graphs in their derivation of my EKT, and even require that the graphs be
planar and trivalent (every vertex has valence exactly 3) - they can also
make them simple. 

THEOREM 1. "The finite simple subcubic graphs are wqo under homeomorphic
embeddability" cannot be proved in Pi11-CA0. This is true even if we require
that the graphs be planar.

[1] H. Friedman, N. Robertson and P. Seymour, The Metamathematics of the
Graph Minor Theorem, Logic and Combinatorics, ed. S. Simpson,
AMS Contemporary Mathematics Series, vol. 65, 1987, 229-261.

In this reference, see page 231, the paragraph beginning with "Robertson and
Seymour...".

We now want to extract a gigantic number out of this situation, as we have
previously with Kruskal's theorem with our TREE[3].
http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html

Accordingly, let SSCG(k) be the longest sequence of simple subcubic graphs
G1,...,Gn such that each Gi has at most i+k vertices and for no i < j is Gi
homeomorphically embeddable into Gj. (Here SSCG stands for simple subcubic
graphs). 

THEOREM 2. SSCG(13) is larger than the halting time of any Turing machine at
the blank tape, that can be proved to halt in at most 2^[2000] symbols in
Pi11-CA0. In particular, every proof of "SSCG(13) exists" in Pi11-CA0 has
more than 2^[1000] symbols.

The idea is to get going with a very long sequence of simple subcubic
graphs, whose length is into Ackermann numbers, so that the adaptation of
[1] can then take over. This follows the same pattern as in
http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html

Recall that K3,3 is the six vertex bipartite graph, 3 against 3, which is
trivalent. It is important to note that this graph is nonplanar.

We start with G1, with 3 connected components. The first two are both K3,3,
and the third is the graph with 2 vertices and 1 edge. Thus G1 has 14
vertices.

G2 is obtained by deleting the edge in the third component. G3 is obtained
by deleting a vertex in the third component. G4 is obtained by deleting the
final vertex in the third component.

G5 is allowed to have 18 vertices. It will consist of two connected
components, the first being K3,3, and the second being a 12 gon - i.e., a
circuit of length 12, TOGETHER with some additional edges. After all, in a
12 gon, all vertices are of valence 2. Let w1,...,w12 be the vertices of the
12 gon. We connect w1,w3;w2,w4;w5,w7;w6,w8;w9,w11;w10,w12, for a total of 6
new edges in the second component of G5.

We define G6,...,G11 by deleting one new edge at a time from this second
component of G5, resulting at the end in just the 12 gon.

For G12, we replace the 12 gon by an 11 gon TOGETHER with some additional
edges. We can have five new edges.

We can remove the new edges as before, so that G17 will just have the 11 gon
as its second connected component.

We now replace the 11 gon with a 10 gon, with 5 additional edges. This is
G18. Then remove the additional edges one at a time, resulting in G23, with
K3,3 plus a 10 gon.

G24 is allowed to have 37 vertices. We won't need quite that many. It will
have two connected components. The first component is K3,3. The second
component is the subcubic graph G* described below.

Start by drawing vertices v1,v2, in a column. Connected to the right of v1
will be a root of a tree with 5 vertices. Connected to the right of v2 will
be a root of a tree with 5 vertices.

Connected below v1 will be a vertex of a triangle.

Connected above v2 will be a vertex of a 9 gon.

The two trees take up 10 vertices. The triangle and the 9 gon take up 12
vertices. v1,v2 make a total of 24 vertices for G*.

Thus G24 has 30 vertices, which is allowed.

The number of binary trees with 5 vertices, up to isomorphism, is 6. So we
can think of (the second component of) G24 as starting a long finite
sequence for n(6) in the same way that we used n(4) in posting #273. (Of
course n(4) would do here, or even probably n(3)).

As in http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html the problem
is that at each stage the number of vertices jumps by 5, instead of by 1.
This is why we used a 9 gon at the top. We spend the required four pausing
steps simply replacing the 9 gon with an 8,7,6,5 gon. We want to use an at
least 5 gon here (at least 4 will do) in order to tell the difference
between the top and the bottom (which has a 3 gon), to exploit n(6).

So we now have a an appropriate sequence of finite simple subcubic graphs of
length at least n(6), all of which are NONPLANAR - because they contain the
connected component K3,3.

We are then free to do the adaptation of [1], for simple planar subcubics,
dropping the K3,3. 

It is easily seen that TREE[3] is completely UNNOTICEABLE in comparison to
SSCG(13). 

*************************************

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 274th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected from
the original.

250. Extreme Cardinals/Pi01  7/31/05  8:34PM
251. Embedding Axioms  8/1/05  10:40AM
252. Pi01 Revisited  10/25/05  10:35PM
253. Pi01 Progress  10/26/05  6:32AM
254. Pi01 Progress/more  11/10/05  4:37AM
255. Controlling Pi01  11/12  5:10PM
256. NAME:finite inclusion theory  11/21/05  2:34AM
257. FIT/more  11/22/05  5:34AM
258. Pi01/Simplification/Restatement  11/27/05  2:12AM
259. Pi01 pointer  11/30/05  10:36AM
260. Pi01/simplification  12/3/05  3:11PM
261. Pi01/nicer  12/5/05  2:26AM
262. Correction/Restatement  12/9/05  10:13AM
263. Pi01/digraphs 1  1/13/06  1:11AM
264. Pi01/digraphs 2  1/27/06  11:34AM
265. Pi01/digraphs 2/more  1/28/06  2:46PM
266. Pi01/digraphs/unifying 2/4/06  5:27AM
267. Pi01/digraphs/progress  2/8/06  2:44AM
268. Finite to Infinite 1  2/22/06  9:01AM
269. Pi01,Pi00/digraphs  2/25/06  3:09AM
270. Finite to Infinite/Restatement  2/25/06  8:25PM
271. Clarification of Smith Article  3/22/06  5:58PM
272. Sigma01/optimal  3/24/06  1:45PM
273: Sigma01/optimal/size  3/28/06  12:57PM

Harvey Friedman