Extremal Combinatorics in Finite Geometries : The Independence Number of Kneser Graphs on Flags of Projective Spaces, Implications for the Chromatic Number and a Theorem on Small Tight Sets of Polar Spaces

Abstract

In 1961 the authors Paul Erdős, Richard Rado and Chao Ko published a paper titled “Intersection theorems for systems of finite sets”, which initiated years of mathematical research in the field of combinatorics, including this thesis. In said paper the authors considered a collection C of mutually intersecting k-subsets of a given n-set and determined, how large C can be, as well as the structure of C in the extremal case. In this thesis mainly generalizations of this problem were studied, namely for flags of subspaces of projective spaces. In particular, the case of plane-solid flags in PG(6,q) and the case of line-solid flags in PG(5,q) were considered and examples of maximal size were determined. Furthermore, the first of these two results was used to determine the chromatic number of the kneser graph on flags of type (2,3) in PG(6,q) and, assuming that a similar result as the one on plane-solid flags exists in the general case as well, also of type (d-1,d) in PG(2d,q). Finally, a theorem on small tight sets in H(2d,q^2) was proven in the last part of the thesis.