Advanced search
1 file | 1.22 MB

Unprovability and phase transitions in Ramsey theory

Michiel De Smet (UGent)
(2011)
Author
Promoter
(UGent) and Andrey Bovykin
Organization
Abstract
The first mathematically interesting, first-order arithmetical example of incompleteness was given in the late seventies and is know as the Paris-Harrington principle. It is a strengthened form of the finite Ramsey theorem which can not be proved, nor refuted in Peano Arithmetic. In this dissertation we investigate several other unprovable statements of Ramseyan nature and determine the threshold functions for the related phase transitions. Chapter 1 sketches out the historical development of unprovability and phase transitions, and offers a little information on Ramsey theory. In addition, it introduces the necessary mathematical background by giving definitions and some useful lemmas. Chapter 2 deals with the pigeonhole principle, presumably the most well-known, finite instance of the Ramsey theorem. Although straightforward in itself, the principle gives rise to unprovable statements. We investigate the related phase transitions and determine the threshold functions. Chapter 3 explores a phase transition related to the so-called infinite subsequence principle, which is another instance of Ramsey’s theorem. Chapter 4 considers the Ramsey theorem without restrictions on the dimensions and colours. First, generalisations of results on partitioning α-large sets are proved, as they are needed later. Second, we show that an iteration of a finite version of the Ramsey theorem leads to unprovability. Chapter 5 investigates the template “thin implies Ramsey”, of which one of the theorems of Nash-Williams is an example. After proving a more universal instance, we study the strength of the original Nash-Williams theorem. We conclude this chapter by presenting an unprovable statement related to Schreier families. Chapter 6 is intended as a vast introduction to the Atlas of prefixed polynomial equations. We begin with the necessary definitions, present some specific members of the Atlas, discuss several issues and give technical details.
Keywords
unprovability, phase transitions, Ramsey theory

Downloads

  • PhDthesis-MichielDeSmet.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 1.22 MB

Citation

Please use this url to cite or link to this publication:

Chicago
De Smet, Michiel. 2011. “Unprovability and Phase Transitions in Ramsey Theory”. Ghent, Belgium: Ghent University. Faculty of Sciences.
APA
De Smet, Michiel. (2011). Unprovability and phase transitions in Ramsey theory. Ghent University. Faculty of Sciences, Ghent, Belgium.
Vancouver
1.
De Smet M. Unprovability and phase transitions in Ramsey theory. [Ghent, Belgium]: Ghent University. Faculty of Sciences; 2011.
MLA
De Smet, Michiel. “Unprovability and Phase Transitions in Ramsey Theory.” 2011 : n. pag. Print.
@phdthesis{1230584,
  abstract     = {The first mathematically interesting, first-order arithmetical example of incompleteness was given in the late seventies and is know as the Paris-Harrington principle. It is a strengthened form of the finite Ramsey theorem which can not be proved, nor refuted in Peano Arithmetic. In this dissertation we investigate several other unprovable statements of Ramseyan nature and determine the threshold functions for the related phase transitions.
Chapter 1 sketches out the historical development of unprovability and phase transitions, and offers a little information on Ramsey theory. In addition, it introduces the necessary mathematical background by giving definitions and some useful lemmas.
Chapter 2 deals with the pigeonhole principle, presumably the most well-known, finite instance of the Ramsey theorem. Although straightforward in itself, the principle gives rise to unprovable statements. We investigate the related phase transitions and determine the threshold functions.
Chapter 3 explores a phase transition related to the so-called infinite subsequence principle, which is another instance of Ramsey{\textquoteright}s theorem.
Chapter 4 considers the Ramsey theorem without restrictions on the dimensions and colours. First, generalisations of results on partitioning \ensuremath{\alpha}-large sets are proved, as they are needed later. Second, we show that an iteration of a finite version of the Ramsey theorem leads to unprovability.
Chapter 5 investigates the template {\textquotedblleft}thin implies Ramsey{\textquotedblright}, of which one of the theorems of Nash-Williams is an example. After proving a more universal instance, we study the strength of the original Nash-Williams theorem. We conclude this chapter by presenting an unprovable statement related to Schreier families.
Chapter 6 is intended as a vast introduction to the Atlas of prefixed polynomial equations. We begin with the necessary definitions, present some specific members of the Atlas, discuss several issues and give technical details.},
  author       = {De Smet, Michiel},
  language     = {eng},
  pages        = {VIII, 177},
  publisher    = {Ghent University. Faculty of Sciences},
  school       = {Ghent University},
  title        = {Unprovability and phase transitions in Ramsey theory},
  year         = {2011},
}