The Erdös-Ko-Rado theorem in graph theory

Abstract

Das Erdös-Ko-Rado Theorem ist ein bekannter Satz in der Kombinatorik. Es wurde erstmals in den 1960ern entdeckt und besonders in den 1970ern bis 1980ern wurden einige Verallgemeinerungen bewiesen. Im wesentlichen garantiert es eine obere Schranke für die Mächtigkeit schneidender Teilfamilien der Potenzmenge von n Elementen. Da Mengen ein sehr allgemeines Konstrukt sind, das in praktisch allen mathematischen Teilgebieten verwendet wird, ist es keine Überraschung, dass das Erdös-Ko-Rado Theorem viele Anwendungen auch außerhalb der Mengentheorie hat. Das Ziel dieser Arbeit ist die Auswirkungen und Anwendungen auf die Graphentheorie zu untersuchen.Im ersten Kapitel führen wir die moderne Version des Erdös-Ko-Rado Theorems ein und beweisen es mittels eines kurzen Beweises, dank Gyula O. H. Katona. Wir berufen uns außerdem auf Deza and Frankl, die weitere Verallgemeinerungen gesammelt haben. Danach wiederholen wir grundlegende Definitionen und Sätze der Graphentheorie. Da ein großer Teil dieser Arbeit Algebraische Graphentheorie benutzt, definieren wir außerdem algebraische Konstrukte wie Gruppen und Homomorphismen und deren Anwendungen in der Graphentheorie.Das Ziel des zweiten Kapitels ist Kneser Graphen zu definieren und einen zweiten Beweis des Erdös-Ko-Rado Theorems auszuarbeiten. Dafür betrachten wir unabhängige Mengen in Kneser Graphen und beweisen, dass die Unabhängigkeitszahl von Kneser Graphen durch dieselbe obere Schranke beschränkt ist, die im Erdös-Ko-Rado Theorem vorkommt. Der Beweis ist allerdings signifikant aufwändiger und benutzt viele Konzepte aus der Algebraischen Graphentheorie.Kapitel 3 handelt von Spektraler Graphentheorie. Dieses Gebiet erforscht des Spektrum von Graphen und kann als die Vereinigung von Graphentheorie und linearer Algebra gesehen werden. Wir definieren Eigenwerte von Graphen und charakterisieren das Spektrum von Kneser Graphen. In diesem Gebiet gibt es noch viele Forschungsmöglichkeiten, jedoch können einige Graph-Invarianten schon durch Eigenwerte beschränkt werden.In Kapitel 4 betrachten wir eine andere Anwendung des Erdös-Ko-Rado Theorems, indem wir EKR Graphen definieren. Diese Graphen erfüllen eine Ungleichungen, die als eine Art Verallgemeinerung des Erdös-Ko-Rado Theorems für komplexere Strukturen gesehen werden kann. Wir beweisen die EKR Eigenschaft für einige Teilfamilien von Bäumen und zeigen Abgeschlossenheit bezüglich des lexikographischen Products mit vollständigen Graphen. Wir enden mit einer Vermutung von Holroyd und Talbot, die die EKR Eigenschaft für eine große Klasse an Graphen zeigen würde. Beweis oder Widerlegung stehen noch aus. Schließlich verweisen wir auf laufende Forschung, die die Vermutung schon für einige Klassen von Graphen beweisen konnte.

The Erdös-Ko-Rado theorem is a well known theorem in the field of combinatorics.It was discovered in the 1960s and from the 1970s to the 1980s many generalizations have been proven. In essence it provides an upper bound for the size of intersecting subfamilies of the power set of n elements. Since sets are a very general construct, thatare used by all mathematical fields, it is no surprise that the Erdös-Ko-Rado theorem has applications outside of the field it was discovered in. This thesis aims to investigate its consequences in graph theory.In the first chapter we introduce the modern version of the Erdös-Ko-Rado theorem and provide a short proof, due to Gyula O. H. Katona. We also refer to Deza andFrank, who gathered further generalizations. Afterwards we recap basic definitions and theorems for graph theory. Since a big part of this work uses algebraic graph theory,we define algebraic constructs like groups and homomorphisms and their applications ingraph theory.The goal of the second chapter is to define Kneser graphs and provide an additional proof for the Erdös-Ko-Radu theorem. This is done by considering independent sets on Kneser graphs and subsequently prove that the independence number of Kneser graphs is bounded by the same bound as the Erdös-Ko-Rado theorem. The proof however is far more involved and makes use of multiple algebraic graph theoretic concepts.Chapter 3 is about spectral graph theory.This mathematical field studies the spectrum of graphs and can be described as the union of graph theory and linear algebra. In particular we want to define eigenvalues for graphs and also characterize the spectrum of Kneser graphs. There is still a lot of discovery to be made in this field, however some graph invariants can already be bound by eigenvalues.In chapter 4 we explore a different application of the Erdös-Ko-Rado theorem, by defining EKR graphs. These types of graphs obey a bound that can be thought of as a generalization of the Erdös-Ko-Rado theorem for more complicated structures. We prove the EKR property for some subfamilies of trees and show closure under lexicographic products with complete graphs. We end on a conjecture by Holroyd and Talbot that ensures EKR properties for a big class of graphs, which still has to be proven or disproven. We also point towards further research that managed to prove the conjecture for certain graph classes.