CLAUDE RIVELINE

Published by

  • redaction
  • mémoire
CLAUDE RIVELINE Préface du Grand Rabbin Gilles Bernheim Association Consistoriale Israélite de Paris Département Torah et Société
  • langue unique des origines
  • histoire de l'arche de noé et de la colombe au rameau d'olivier ¶
  • juif de jérusalem
  • multiplicité des langues
  • tradition juive
  • noé
  • génération
  • générations
  • société ¶
  • société de ¶
  • sociétés ¶
Published : Monday, March 26, 2012
Reading/s : 24
Origin : riveline.net
Number of pages: 13
See more See less

REVERSE MATHEMATICS AND
RECURSIVE GRAPH THEORY
William Gasarch
University of Maryland
Jeffry L. Hirst
Appalachian State University
October 30, 1994
Abstract. We examine a number of results of in nite combinatorics using the techniques
of reverse mathematics. Our results are inspired by similar results in recursive combina-
torics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and
Hamilton paths.
Reverse mathematics provides powerful techniques for analyzing the logical content of
theorems. By contrast, recursive mathematics analyzes the e ective content of theorems.
Theorems and techniques of recursive mathematics can often inspire related results in
reverse mathematics, as demonstrated by the research presented here. Sections 1 and
2 analyze theorems on graph colorings. Section 3 considers graphs with Euler paths.
Stronger axiom systems are introduced and applied to the study of Hamilton paths in
Section4. Weassumefamiliaritywiththemethodsofreversemathematics, asdescribedin
[15]. Additional information, including techniques for encoding mathematical statements
in second-order arithmetic, can be found in [4] and [16].
1. Graph Colorings.
1991 Mathematics Subject Classi cation . 03F35, 03D45.
Key words and phrases. recursion theory, proof theory, graph theory.
Gasarch’s research was partially supported by NSF grant CCR9020079.
Typeset byA S-T XM E
16
In this section we will consider theorems on node colorings of countable graphs. A
2(countable) graph G consists of a set of vertices V N and a set of edges E [N] . We
will abuse notation by denoting an edge by (x,y) rather than {x,y}. For k ∈N, we say
that : V → k is a k-coloring of G if always assigns di erent colors to neighboring
vertices. That is, is a k-coloring if : V → k and (x,y)∈ E implies (x) = (y). If G
has a k-coloring, we say that G is k-chromatic. Using an appropriate axiom system, it is
possible to prove that a graph is k-chromatic if it satis es the following local condition.
De nition 1 (RCA ). A graph G is locally k-chromatic if every nite subgraph of G is0
k-chromatic.
The following theorem is a reverse mathematics analog of Theorem 1 of Bean [2]. To
prove that (1) implies (2), a tree is constructed in which every in nite path encodes a
k-coloring. The proof of the reversal uses a graph whose k-colorings encode separating
sets for a pair of injections. This implies (1) by a result of Simpson [14]. For a detailed
proof, see Theorem 3.4 in [9].
Theorem 2 (RCA ). For every k 2, the following are equivalent:0
(1) WKL .0
(2) If G is locally k-chromatic, then G is k-chromatic.
In [2], Bean proved that there is a recursive 3-chromatic graph with no recursive col-
oring, regardless of the number of colors allowed. We now present a related theorem of
reverse mathematics.
Theorem 3 (RCA ). For each k 2, the following are equivalent:0
(1) WKL .0
(2) If G is locally k-chromatic, then G is (2k 1)-chromatic.
Proof. Whenever k 2, we have that 2k 1 > k, so every k-coloring is automatically a
(2k 1)-coloring. Consequently, (1) implies (2) follows immediately from Theorem 2.
26
6
6
6
6
We will now prove that (2) implies (1) whenk = 2, and then indicate how the argument
can be generalized to any k ∈N. By a result of Simpson [14], WKL can be proved by0
showing that the ranges of an arbitrary pair of disjoint injections can be separated. Let
f :N→N and g :N→N be injections such that for all m,n∈N, f(n) = g(m). We will
construct a 2-chromatic graph with the property that any 3-coloring of G encodes a set S
such that y∈Range(f) implies y∈S, and y∈S implies y∈/ Range(g).
The graph G contains an in nite complete bipartite subgraph consisting of upper ver-
u l u ltices{b :n∈N}, lower vertices{b :n∈N}, and connecting edges{(b ,b ) :n,m∈N}.n n n m
u lAlso, G contains an in nite collection of pairs of vertices, denoted by n and n for n∈N.
u lEach such pair is connected, so the edges{(n ,n ) :n∈N} are included in G. Additional
u lconnections depend on the injections f and g. If f(i) = n, add the edges (b ,n ) andm
l u u u l l(b ,n ) for all m i. If g(i) = n, add the edges (b ,n ) and (b ,n ) for all m i.m m m
u lNaively, if n is in the range of f or g, then the pair (n ,n ) is connected to the complete
bipartite subgraph. If n is in the range of G, the pair is “ ipped” before it is connected.
0The reader can verify that G is de nable in f and g, and thus exists by the recur-1
sive comprehension axiom. Every nite subgraph of G is clearly bipartite, so G is locally
2-chromatic. Thus, by (2), G has a 3-coloring; denote it by :G→ 3.
If is a 2-coloring, we can dene the separating set, S, by
u u l lS ={y∈N :(y ) =(b )∨(y ) =(b )}.0 0
When uses all 3 colors, we must modify the construction of S. In particular, we must
nd a j ∈N such that
u u l l(a) ∀y(∃n(nj∧f(n) =y)→ ((y ) =(b )∨(y ) =(b ))), andj j
l l u u(b) ∀y(∃n(nj∧g(n) =y)→ ((y ) =(b )∧(y ) =(b ))).j j
Suppose, by way of contradiction, that no such j exists. The for some m and y, either
u u l l l l u uf(m) =y∧(y ) =(b )∧(y ) =(b ) or g(m) =y∧((y ) =(b )∨(y ) =(b )).0 0 0 0
u l l uIf f(m) = y, since is a 3-coloring, either (y ) = (b ) or (y ) = (b ). By the0 0
36
6
6
6
u u l lconstruction of G, for every n > m, (b ) = (b ) and (b ) = (b ). Similarly, them n m n
case g(m) = y also yields a point beyond which the complete bipartite subgraph of G is
02-colored. By the negation of (a) and (b), there is an m >m and a z ∈N such that either
0 u u l l 0 l l u uf(m ) =z∧(z ) =(b )∧(z ) =(b )org(m ) =z∧((z ) =(b )∨(z ) =(b )).m m m m
0 u l l uIf f(m ) = z, then since is a 3-coloring, either (z ) = (b ) or (z ) = (b ). Sincem m
0 l l u u l u u lm >m, (b ) =(b ) and (b ) =(b ), so either (z ) =(b ) or (z ) =(b ).0 0 0 0m m m m m m
l u u l 0But (z ,b ) and (z ,b ) are edges of G, so is not a 3-coloring. Assuming g(m ) = z0 0m m
yields a similar contradiction. Thus, a j satisfying (a) and (b) exists.
Given an integer j satisfying (a) and (b), the separating set S may be de ned as the
union of {y∈N :∃n<jf(n) =y} and
u u l l{y∈N : (∀n<jg(n) =y)∧((y ) =(b )∨(y ) =(b ))}j j
0S is de nable in and j, so the recursive comprehension axiom assures the existence1
of S. If f(n) = y and n < j, then y ∈ S. If f(n) = y and n j, then by (a) and the fact
that f and g have disjoint ranges, y ∈ S. Thus Range(f) S. If g(n) = y, and n < j,
then since the ranges of f and g are disjoint we have y∈/ S. If g(n) =y and nj, by (b)
y∈/ S. Thus S is the desired separating set. This completes the proof for k = 2.
For k > 2, the preceding proof requires the following modi cations. Replace the com-
pplete bipartite subgraph of G by a complete k-partite subgraph with vertices {b : p <m
u l pk∧m∈N}. Eachpair(n ,n )isreplacedbyacompletegraphonthevertices{n :p<k}.
0p p 0If f(i) = n, add the edges (b ,n ) for all m i and all p = p less than k. If g(i) = n,m
0p ptwist the subgraph before attaching it. That is, add the edges (b ,n ) for all m i andm
0 0all p and p less than k such that p6 p +1 (mod k). The argument locating the integer
0j is similar, except that m and m must be replaced by a sequence m ,...,m . Beyond1 k
the point m , the complete k-partite subgraph of G is k-colored by . The de nitionk 1
of S is very similar, except that a bounded quanti er should be used to avoid the k-fold
conjunction.
4BecauseBean[2]constructedarecursivegraphwithnorecursivecoloring,thefollowing
conjecture seems reasonable. Unfortunately, even the case wherek = 2 andm = 4 remains
open.
Conjecture 4 (RCA ). For each k 2 and each mk the following are equivalent:0
(1) WKL .0
(2) If G is locally k-chromatic, then G is m-chromatic.
2. Bounded graphs and sequences of graphs.
Asnotedabove,alocallyk-chromaticrecursivegraphmaynothavearecursivecoloring,
regardless of the number of colors used. By contrast, highly recursive graphs always have
recursive colorings. A proof theoretic analog of a highly recursive graph is a bounded
graph.
De nition 5 (RCA ). A graph G =hV,Ei is bounded if there is a function h : V →N0
such that for all x,y∈V, (x,y)∈E implies h(x)y.
Schmerl[11]provedthateveryhighlyrecursivek-chromaticgraphhasarecursive(2k
1)-coloring. (This result was independently rediscovered byCarstens andPappinghaus
[3].) Formalizing Schmerl’s proof in RCA yields the following result.0
Theorem 6 (RCA ). For k∈N, if G is a bounded locally k-chromatic graph, then G is0
(2k 1)-chromatic.
In[11],Schmerlalsoshowedthatforeachk 2,thereisahighlyrecursivek-chromatic
graph which has no recursive 2k 2 coloring. Using the constructions from his proof, one
can easily prove the following theorem.
Theorem 7 (RCA ). For every k 2, the following are equivalent:0
(1) WKL .0
(2) If G is a bounded locally k-chromatic graph, then G is (2k 2)-chromatic.
56
Proof. Whenver k 2, we have 2k 2k, so every k-coloring is automatically a (2k 2)-
coloring. Consequently,(1)implies(2)followsimmediatelyfromTheorem2. Toprovethat
(2) implies (1), we imitate Schmerl’s [11] construction of a bounded locally k-chromatic
graph for which any (2k 2)-coloring separates the ranges of a pair of disjoint injections.
An application of a theorem of Simpson [14] yields WKL . 0
We will close this section with a theorem concerning sequences of graphs and its recur-
sion theoretic corollary. We say that a graph G is colorable if there exists an integer k such
that G is k-chromatic.
Theorem 8 (RCA ). The following are equivalent:0
(1) ACA .0
(2) Given a countable sequence of graphs, hG : i ∈Ni, there is a function f :N → 2i
such that f(i) = 1 if G is colorable and f(i) = 0 otherwise.i
Proof. To prove that (1) implies (2), assume ACA and let hG : i ∈ Ni be a sequence0 i
of graphs. De ne f : N → N by setting f(i) = 1 if there exists a k ∈ N such that G isi
locally k-chromatic, and setting f(i) = 0 otherwise. Since “G is locally k-chromatic” isi
an arithmetical sentence with parameter G , f exists by the arithmetical comprehensioni
axiom. Since ACA implies WKL , we may apply Theorem 2 to show that f(i) = 1 if0 0
and only if G is colorable.i
To prove the converse, assumeRCA and (2). To proveACA it suces to show that0 0
for every injection g, Range(g) exists [14]. De ne the sequence of graphs hG : i ∈Ni asi
follows. Let {v : j ∈N} be the vertices of G . If j < k and ∀m k(g(m) = i), add thej i
edge (v ,v ) to G . RCA can prove that hG : i ∈Ni exists, and G is colorable if andj k i 0 i i
only if i ∈ Range(g). Thus, the function f supplied by (2) is the characteristic function
for Range(g). By the recursive comprehension axiom, Range(g) exists.
0Corollary 9. There is a recursive sequence of recursive graphs hG : i ∈Ni such that 0i
is recursive in {i∈N :G is colorable}.i
60Proof. In the proof of the reversal for Theorem 8, let g be a recursive function such that 0
is recursive in Range(g). The sequence of graphs constructed in the proof has the desired
properties.
3. Euler paths.
Now, we will turn to the study of Euler paths. A path in a graph G is a sequence of
vertices v ,v ,v ,... such that for every i∈N, (v ,v ) is an edge of G. A path is called0 1 2 i i+1
an Euler path if it uses every edge of G exactly once.
The following terminology is useful in determining when a graph has an Euler path. A
graph G =hV,Ei is locally nite if for each vertex v, the set {u∈V : (v,u)∈E} is nite.
IfH isasubgraphofG, G H denotesthegraphobtainedbydeletingtheedgesofH from
G. Using this terminology, we can describe a condition which, from a naive viewpoint, is
su cient for the existence of an Euler path.
De nition 10 (RCA ). A graph G is pre-Eulerian if it is0
(1) connected,
(2) has at most one vertex of odd degree,
(3) if it has no vertices of odd degree, then it has at least one vertex of in nite degree,
and
(4) if H is any nite subgraph of G then G H has exactly one in nite connected
component.
Notethattheformula“Gispre-Eulerian”isarithmeticalinthesetparameterG. RCA0
su ces to prove that every graph with an Euler path is pre-Eulerian. However, RCA0
can only prove that bounded pre-Eulerian graphs have Euler paths. (Bounded graphs are
de ned in Section 3.) This result is just a formalization of Bean’s [1] proof that every
highly recursive pre-Eulerian graph has a recursive Euler path.
Theorem 11 (RCA ). If G is a bounded pre-Eulerian graph, then G has an Euler path.0
7If G is not bounded, additional axiomatic strength is required to prove the existence of
an Euler path.
Theorem 12 (RCA ). The following are equivalent:0
(1) ACA .0
(2) If G is a pre-Eulerian graph, then G has an Euler path.
(3) If G is a locally nite pre-Eulerian graph, then G has an Euler path.
Proof. To prove that (1) implies (2), assume ACA and let G be a pre-Eulerian graph.0
Let hE : i ∈Ni be an enumeration of the edges of G. Let v be the vertex of G of oddi 0
degree,oravertexofin nitedegreeifnooddvertexexists. ImitatingtheproofofTheorem
3.2.1 of Ore [10], there is a nite path P containing the edge E such that0
P starts at v ,0
G P is connected, and
P ends at the odd vertex of G P, or at an in nite vertex of G P if no odd
vertex exists.
Furthermore, sincethenitepathsofGcanbeencodedbyintegers, wecanpicktheunique
path P satisfying the conditions above and having the least code. Similarly, any path P0 i
satisfying the three conditions can be extended to a unique path P which contains thei+1
edgeE , satis es the three conditions, and has the least code among all paths with thesei+1
properties. Note the P extends P by including P as an initial segment. The readeri+1 i i
may verify that the sequence of paths hP : i ∈ Ni is arithmetically de nable in G, andi
thso exists by arithmetical comprehension. Let v denote the i vertex of P . Then thei i
sequence hv : i∈Ni exists by recursive comprehension and includes each P as an initiali i
segment. Consequently, hv :i∈Ni de nes an Euler path through G.i
Since (3) is a special case of (2), showing that (3) implies (1) will complete the proof of
the theorem. Assume RCA and

Be the first to leave a comment!!

12/1000 maximum characters.