Ramsey numbers
Ermakovich, Elizaveta (2024)
2024
Bachelor's Programme in Science and Engineering
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2024-04-24
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202404234256
https://urn.fi/URN:NBN:fi:tuni-202404234256
Tiivistelmä
It is always guaranteed to find some order in chaos -- we just need to take a large enough chaos. To explain why, we use the tools from the area of mathematics known as Ramsey theory.
Ramsey theory is a relatively new discipline that lies between the fields of combinatorics and graph theory. It deals with conditions under which some properties are guaranteed for large-scale systems. The measure of how large those systems need to be is characterized by Ramsey numbers. Almost a hundred years ago British mathematician Frank Ramsey proved that if we know the size of the structure that we are looking for, a large enough graph that guarantees the appearance of that structure in it always exists.
Today, we only know the first nine Ramsey numbers. The calculation of higher values remains an open challenge in mathematics. As the numbers increase, so does the uncertainty surrounding their exact values. For most of the Ramsey numbers, we only know the intervals for search, and the larger the numbers get, the wider those intervals are.
One extension of Ramsey theory is the induced Ramsey theory. Instead of looking for a complete subgraph, as in the classical Ramsey theory, induced Ramsey theory seeks to find an arbitrary subgraph in a larger graph. It is an even more complicated task, since we not only have to present a graph of a certain size but also of a certain structure.
In this thesis, we present a general overview of Ramsey theory. We define graph theoretical concepts related to Ramsey numbers. Then we prove the finiteness of Ramsey numbers and show some bounds for them. Lastly, we discuss a recent result in Ramsey theory and introduce induced Ramsey theory.
Ramsey theory is a relatively new discipline that lies between the fields of combinatorics and graph theory. It deals with conditions under which some properties are guaranteed for large-scale systems. The measure of how large those systems need to be is characterized by Ramsey numbers. Almost a hundred years ago British mathematician Frank Ramsey proved that if we know the size of the structure that we are looking for, a large enough graph that guarantees the appearance of that structure in it always exists.
Today, we only know the first nine Ramsey numbers. The calculation of higher values remains an open challenge in mathematics. As the numbers increase, so does the uncertainty surrounding their exact values. For most of the Ramsey numbers, we only know the intervals for search, and the larger the numbers get, the wider those intervals are.
One extension of Ramsey theory is the induced Ramsey theory. Instead of looking for a complete subgraph, as in the classical Ramsey theory, induced Ramsey theory seeks to find an arbitrary subgraph in a larger graph. It is an even more complicated task, since we not only have to present a graph of a certain size but also of a certain structure.
In this thesis, we present a general overview of Ramsey theory. We define graph theoretical concepts related to Ramsey numbers. Then we prove the finiteness of Ramsey numbers and show some bounds for them. Lastly, we discuss a recent result in Ramsey theory and introduce induced Ramsey theory.
Kokoelmat
- Kandidaatintutkielmat [10830]