Tesi etd-03102025-191729 |
Link copiato negli appunti
Tipo di tesi
Tesi di dottorato di ricerca
Autore
RAGOSTA, MARIACLARA
URN
etd-03102025-191729
Titolo
Arithmetic Ramsey Theory and Combinatorics: some new results via ultrafilters and nonstandard methods
Settore scientifico disciplinare
MATH-01/A - Logica matematica
Corso di studi
MATEMATICA
Relatori
tutor Prof. Di Nasso, Mauro
Parole chiave
- combinatorics
- divisibility
- exponential patterns
- nonstandard analysis
- partition regularity
- Ramsey theory
- tensor pairs
- ultrafilters
Data inizio appello
24/03/2025
Consultabilità
Non consultabile
Data di rilascio
24/03/2028
Riassunto
The dissertation contains a number of new results on Arithmetic Ramsey Theory (ART for short) and combinatorics mainly obtained by means of ultrafilters and nonstandard methods.
ART studies partition regularity problems, i.e. properties that are “indestructible” under finite partitions of the naturals. More precisely, a property p is partition regular if, whenever N is finitely coloured, there is a colour satisfying p.
Ultrafilters are families of sets that are “large” with respect to some notion of largeness. What strictly relates these important objects to ART is the well-known fact that a property p is partition regular precisely when there is an ultrafilter consisting solely of sets satisfying p.
The set *N of hypernatural numbers is an elementary extension of the set N of natural numbers (i.e. it satisfies precisely the same first order properties). Roughly speaking, every hypernatural number can be seen as a generator of a specific ultrafilter. The properties of such a hypernatural number correspond to those of the sets belonging to the ultrafilter that it generates. This strict relation between ultrafilters and hypernatural numbers allows, among other things, the study of partition regularity problems from a different point of view.
The first chapter is devoted to describing the preliminaries for the rest of the work, namely a brief history of Arithmetic Ramsey Theory, a description of the family βN of ultrafilters and an introduction to hypernatural numbers and nonstandard methods in general.
A significant part of the dissertation aims to present a new relevant theorem on infinitary Ramsey Theory. A cornerstone in this field of research is Hindman's Theorem, which states that, whenever N is finitely coloured, there is an increasing infinite sequence such that all sums of finitely many elements from the sequence lie in a same colour. Hindman's original combinatorial proof was extremely complicated, but soon Galvin and Glazer managed to prove it in a much more elegant and short way, and ultrafilters were the main tool of their proof. This argument also led to a general version of the theorem for all associative operations on an infinite set. In our work, we proved a strong version of this important result for a precise class of operations that are not associative (nor commutative) and that generalise the exponentiation of natural numbers.
A crucial role in this work is played by a special type of ultrafilter, whose members are sets characterised by a particularly rich combinatorial structure.
One more work on infinitary Ramsey theory is developed in the third chapter. Ramsey Theorem states that, whenever N^2 is finitely coloured, there is an infinite set such that all ordered pairs of different elements of the set lie in a same colour. This statement leads to the existence of the so-called Ramsey witness ultrafilters and to the corresponding notion of Ramsey witness pair in non-standard analysis. By exploring the properties and special structure of these objects, we managed to show some relevant statements of infinitary Ramsey theory and to offer a new perspective to infinitary problems in this area. For instance, a result by Hindman shows the existence of a finite colouring such that no infinite sequence has both pairwise sums and products monochromatic.
This is an important theorem strictly related to one of the most significant open problems in ART, concerning the partition regularity of the property of containing a quadruple of the form a, b, a+b, ab. Ivan, Leader and Hindman recently proved this result by combinatorial means. We restated this result in terms of Ramsey witness ultrafilters and gave an alternative proof. We also used some very recent tools of nonstandard analysis to study these kinds of notions. We do believe that the mentioned methods could be extremely useful and promising to deeply understand these kinds of notions, and that this could give a significant contribution to the study of Ramsey-like infinitary partition regularity problems.
Ultrafilters are again the main characters of the fourth chapter of the dissertation, which aims to investigate divisibility in βN. Recently, Sobot introduced two different notions of congruence of ultrafilters and asked whether one of them is somehow well-behaved. We isolated the specific class of ultrafilters, and call them self-divisible, for which both relations are equivalence relations and verify the usual good properties of a congruence. We showed that self-divisible ultrafilters are precisely those for which the two notions coincide. We gave numerous different characterisations of these objects, also in terms of profinite groups.
The final topic of the dissertation has a different combinatorial flavour. We gave a precise description of a really fascinating problem: in an infinite maze where both the position of the treasure and of the walls are unknown, can an infinite sequence of instructions such as ``go left'', ``go right'', ``go down'' and ``go up'' lead to the treasure at some point? What if there are only finitely many alternatives for the position of the prize and for a winning path to it?
We analysed the problem, made some observations and gave some partial results.
In particular, we showed with a compactness argument that in the case of finitely many alternatives, if a winning sequence exists, then there must be a finite one.
ART studies partition regularity problems, i.e. properties that are “indestructible” under finite partitions of the naturals. More precisely, a property p is partition regular if, whenever N is finitely coloured, there is a colour satisfying p.
Ultrafilters are families of sets that are “large” with respect to some notion of largeness. What strictly relates these important objects to ART is the well-known fact that a property p is partition regular precisely when there is an ultrafilter consisting solely of sets satisfying p.
The set *N of hypernatural numbers is an elementary extension of the set N of natural numbers (i.e. it satisfies precisely the same first order properties). Roughly speaking, every hypernatural number can be seen as a generator of a specific ultrafilter. The properties of such a hypernatural number correspond to those of the sets belonging to the ultrafilter that it generates. This strict relation between ultrafilters and hypernatural numbers allows, among other things, the study of partition regularity problems from a different point of view.
The first chapter is devoted to describing the preliminaries for the rest of the work, namely a brief history of Arithmetic Ramsey Theory, a description of the family βN of ultrafilters and an introduction to hypernatural numbers and nonstandard methods in general.
A significant part of the dissertation aims to present a new relevant theorem on infinitary Ramsey Theory. A cornerstone in this field of research is Hindman's Theorem, which states that, whenever N is finitely coloured, there is an increasing infinite sequence such that all sums of finitely many elements from the sequence lie in a same colour. Hindman's original combinatorial proof was extremely complicated, but soon Galvin and Glazer managed to prove it in a much more elegant and short way, and ultrafilters were the main tool of their proof. This argument also led to a general version of the theorem for all associative operations on an infinite set. In our work, we proved a strong version of this important result for a precise class of operations that are not associative (nor commutative) and that generalise the exponentiation of natural numbers.
A crucial role in this work is played by a special type of ultrafilter, whose members are sets characterised by a particularly rich combinatorial structure.
One more work on infinitary Ramsey theory is developed in the third chapter. Ramsey Theorem states that, whenever N^2 is finitely coloured, there is an infinite set such that all ordered pairs of different elements of the set lie in a same colour. This statement leads to the existence of the so-called Ramsey witness ultrafilters and to the corresponding notion of Ramsey witness pair in non-standard analysis. By exploring the properties and special structure of these objects, we managed to show some relevant statements of infinitary Ramsey theory and to offer a new perspective to infinitary problems in this area. For instance, a result by Hindman shows the existence of a finite colouring such that no infinite sequence has both pairwise sums and products monochromatic.
This is an important theorem strictly related to one of the most significant open problems in ART, concerning the partition regularity of the property of containing a quadruple of the form a, b, a+b, ab. Ivan, Leader and Hindman recently proved this result by combinatorial means. We restated this result in terms of Ramsey witness ultrafilters and gave an alternative proof. We also used some very recent tools of nonstandard analysis to study these kinds of notions. We do believe that the mentioned methods could be extremely useful and promising to deeply understand these kinds of notions, and that this could give a significant contribution to the study of Ramsey-like infinitary partition regularity problems.
Ultrafilters are again the main characters of the fourth chapter of the dissertation, which aims to investigate divisibility in βN. Recently, Sobot introduced two different notions of congruence of ultrafilters and asked whether one of them is somehow well-behaved. We isolated the specific class of ultrafilters, and call them self-divisible, for which both relations are equivalence relations and verify the usual good properties of a congruence. We showed that self-divisible ultrafilters are precisely those for which the two notions coincide. We gave numerous different characterisations of these objects, also in terms of profinite groups.
The final topic of the dissertation has a different combinatorial flavour. We gave a precise description of a really fascinating problem: in an infinite maze where both the position of the treasure and of the walls are unknown, can an infinite sequence of instructions such as ``go left'', ``go right'', ``go down'' and ``go up'' lead to the treasure at some point? What if there are only finitely many alternatives for the position of the prize and for a winning path to it?
We analysed the problem, made some observations and gave some partial results.
In particular, we showed with a compactness argument that in the case of finitely many alternatives, if a winning sequence exists, then there must be a finite one.
File
Nome file | Dimensione |
---|---|
La tesi non è consultabile. |