Back to search

University of Waterloo

Colouring Subspaces

Abstract

dc:description.abstract

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 <em>q</em>-Kneser graph are the <em>k</em>-dimensional subspaces of a vector space of dimension <em>v</em> over F<sub><em>q</em></sub>, and two <em>k</em>-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve colouring the <em>q</em>-Kneser graph when <em>k</em>=2. There are two cases. When <em>k</em>=2 and <em>v</em>=4, the chromatic number is <em>q</em><sup>2</sup>+<em>q</em>. If <em>k</em>=2 and <em>v</em>>4, the chromatic number is (<em>q</em><sup>(v-1)</sup>-1)/(<em>q</em>-1). In both cases, we characterise the minimal colourings. We develop some theory for colouring the <em>q</em>-Kneser graph in general.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chowdhury, Ameerah

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Copyright: 2005, Chowdhury, Ameerah. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1026

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chowdhury, Ameerah. Colouring Subspaces. University of Waterloo, 2005. http://hdl.handle.net/10012/1026