Colouring Subspaces

Mathematics;Kneser graph;projective geometry;colouring

Chowdhury, Ameerah

University of Waterloo

关键词: Mathematics;    Kneser graph;    projective geometry;    colouring;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/1026/1/anchowdh2005.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

This thesis was originally motivated by considering vector space analogues of problems in extremal set theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. The vertices of the q-Kneser graph are the k-dimensional subspaces of a vector space of dimension v over F_q, and two k-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve colouring the q-Kneser graph when k=2. There are two cases. When k=2 and v=4, the chromatic number is q²+q. If k=2 and v>4, the chromatic number is (q^(v-1)-1)/(q-1). In both cases, we characterise the minimal colourings. We develop some theory for colouring the q-Kneser graph in general.