19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

On the chromatic number of $q$-Kneser graphs

Presented by Prof. Tamas SZONYI
Type: Oral presentation
Track: Keynote lecture


The $q$-analogue of questions about sets and subsets are questions about vector spaces and subspaces. For a prime power $q$, and an $n$-dimensional vector space $V$ over $GF(q)$, let ${V\brack k}$ denote the family of $k$-subspaces of $V$. The vertex set of the $q$-Kneser graph $qK_{n:k}$ is ${V\brack k}$, where $V$ is an $n$-dimensional vector space over $GF(q)$. Two vertices of $qK_{n:k}$ are adjacent if and only if the corresponding $k$-subspaces are disjoint (i.e., meet in 0). We first prove the $q$-analogue of the theorem of Hilton-Milner \cite{HM}, then apply it to determine the chromatic number of $q$-Kneser graphs. Theorem (\cite{BBCFPMS}, \cite{CGR} for $k=2$). If $k \geq 3$ and $q\geq 3$, $n \geq 2k+1$ or $q=2$, $n \geq 2k+2$, then for the chromatic number of the $q$-Kneser graph we have $\chi(qK_{n:k}) = {n-k+1\brack 1}$. Moreover, each colour class of a minimum colouring is a point-pencil and the points determining a color are the points of an $(n-k+1)$-dimensional subspace.} The case $n=2k$ is more interesting (and seems to be more difficult). In this case Godsil and Newman \cite{GN} characterized the largest cocliques and we could show that the second largest coclique must be essentially smaller if $q>q_k$ is large enough. We conjecture that the chromatic number of $qK_{2k:k}$ equals $q^k+q^{k-1}$, for all $q$ and $k$, unfortunately we were only be able to prove this when $q$ is large enough compared to $k$, see \cite{BBS}. The case $n=4$, $k=2$ was done earlier by Eisfeld, Storme, Sziklai \cite{ESS01} and Chowdhury, Godsil, and Royle \cite{CGR}. Fpr $k=3,n=6$ we could completely describe the cocliques that are larger than $3q^4+3q^3+2q^2+q$, see \cite{BBS}. This is joint work with Aart Blokhuis, Andries Brouwer and other colleagues. Bibliography: \bibitem{BBS} \textsc{A.~Blokhuis, A.~E.~Brouwer, T.~Sz\H{o}nyi}, {\em On the chromatic number of $q$-Kneser graphs}, Designs, Codes, and Cryptography, to appear \bibitem{BBCFPMS} \textsc{A.~Blokhuis, A.~E.~Brouwer, A.~Chowdhury, P.~Frankl, B.~Patk\'os, T.~Mussche, T.~Sz\H{o}nyi}, {\em A Hilton-Milner theorem for vector spaces}, Electr. J. of Combinatorics {\bf 17} (2010) R71. \bibitem{CGR} \textsc{A.~Chowdhury, C.~Godsil, G.~Royle}, {\it Colouring lines in a projective space}, J. Combin. Theory Ser. A {\bf 113} (2006) 228--236. \bibitem{ESS01} \textsc{J. Eisfeld, L. Storme, P. Sziklai}, {\it Minimal covers of the Klein quadric}, J. Combin. Theory Ser. A {\bf 95} (2001) 145--157. \bibitem{FW} \textsc{P.~Frankl, R.~M.~Wilson}, {\it The Erd\H{o}s-Ko-Rado theorem for vector spaces}, J. Combin. Theory Ser. A {\bf 43} (1986) 228--236. \bibitem{GN} \textsc{C. D.~Godsil, M. W.~Newman}, {\it Independent sets in association schemes}, Combinatorica {\bf 26} (2006) 431--443. \bibitem{HM} \textsc{A. J. W.~Hilton, E. C.~Milner}, {\it Some intersection theorems for systems of finite sets}, Quart. J. Math. Oxford Ser. (2) {\bf 18} (1967) 369--384. \bibitem{H} \textsc{W. N.~Hsieh}, {\it Intersection theorems for systems of finite vector spaces}, Discrete Math. {\bf 12} (1975) 1--16.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors