Colouring Subspaces

[摘要] 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.

[发布机构] University of Waterloo

[效力级别] Kneser graph

[关键词] Mathematics;Kneser graph;projective geometry;colouring