𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Reverse mathematics and infinite traceable graphs

✍ Scribed by Peter Cholak; David Galvin; Reed Solomon

Publisher
John Wiley and Sons
Year
2012
Tongue
English
Weight
173 KB
Volume
58
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We analyze three applications of Ramsey’s Theorem for 4‐tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA~0~.

πŸ“œ SIMILAR VOLUMES

Reverse Mathematics and Grundy colorings
Reverse Mathematics and Grundy colorings of graphs
✍ James H. Schmerl πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 137 KB

The relationship of Grundy and chromatic numbers of graphs in the context of Reverse Mathematics is investigated.

Derived sequences and reverse mathematic
Derived sequences and reverse mathematics
✍ Jeffry L. Hirst πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 412 KB

## Abstract One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR~0~. This existence theorem is an intermediate step in a proof that a statement concern

Reverse Mathematics and Ordinal Multipli
Reverse Mathematics and Ordinal Multiplication
✍ Jeffry L. Hirst πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 352 KB

This paper uses the framework of reverse mathematics to analyze the proof theoretic content of several statements concerning multiplication of countable well-orderings. In particular, a division algorithm for ordinal arithmetic is shown t o be equivalent t o the subsystem ATRo.

Infinite median graphs, (0, 2)-graphs, a
Infinite median graphs, (0, 2)-graphs, and hypercubes
✍ Hans-J. Bandelt; Henry Martyn Mulder πŸ“‚ Article πŸ“… 1983 πŸ› John Wiley and Sons 🌐 English βš– 450 KB

Hypercubes are characterized among connected bipartite graphs by interval conditions in several ways. These results are based on the following two facts: (i) connected bipartite graphs are median provided that all their intervals induce median graphs, and (ii) median (0, 2)graphs are hypercubes. No