# CLAUDE RIVELINE

### udwoo

- redaction
- mémoire

- 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 ¶

##### Redaction

-##### Mémoire

-##### Bernheim

-##### Agence juive

-##### Mines ParisTech

-##### Jean-Paul Sartre

-##### École polytechnique

-##### École

-##### Egypt

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

You may also like

### CLAUDE RIVELINE

from udwoo

### Evaluation des coûts

from presses-des-mines

### Évaluation des coûts

from presses-des-mines-via-openedition

### Numerology Chart Analysis

from udwoo