Colouring Lines in Projective Space

Details Colouring Lines in Projective Space Colouring Lines in Projective Space

2005-07-15

arxiv.org/abs/math/0507319v1

Mathematics

Combinatorics

19 pages; to appear in J. Combinatorial Theory, Series A

Scientific paper

Let $V$ be a vector space of dimension $v$ over a field of order $q$. The $q$-Kneser graph has the $k$-dimensional subspaces of $V$ as its vertices, where two subspaces $\alpha$ and $\beta$ are adjacent if and only if $\alpha\cap\beta$ is the zero subspace. This paper is motivated by the problem of determining the chromatic numbers of these graphs. This problem is trivial when $k=1$ (and the graphs are complete) or when $v<2k$ (and the graphs are empty). We establish some basic theory in the general case. Then specializing to the case $k=2$, we show that the chromatic number is $q^2+q$ when $v=4$ and $(q^{v-1}-1)/(q-1)$ when $v > 4$. In both cases we characterise the minimal colourings.

Affiliated with

Also associated with

No associations

Rating

Colouring Lines in Projective Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Colouring Lines in Projective Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Colouring Lines in Projective Space will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-411701