Aron Benedicto: Linjära invarianter i ramseyteori

Abstract.

Large Ramsey numbers are notoriously difficult to compute. In order to compute lower Ramsey numbers we have to investigate relatively few cases. Usually we can compute them by applying the pigeonhole principle iteratively. However for larger Ramsey numbers this method is ineffective since there are too many cases we need to investigate. So in order to rule out cases we use methods such as algorithms, probabilistics or linear invariants. This thesis will investigate how we can use linear invariants in Ramsey theory. By reformulating the problem in terms of complete subgraphs and independence number allows us to experiment with the relation between the graphs number of nodes, number of edges and independence number. It turns out that there are linear combinations of these three variables that exhibits interesting properties for triangle-free graphs. We will use monoid theory to show why we can create these linear invariants. We will then prove that two different linear invariants will always give us a positive value if the graph is triangle-free. Using these and some other linear invariants we will compute upper limits for different \(R(3,k)\).