19-25 June 2011

Bled, Slovenia

Europe/Ljubljana timezone

# On the chromatic number of $q$-Kneser graphs

Presented by Prof. Tamas SZONYI

Type: Oral presentation

Track: Keynote lecture

## Content

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.

## Place

Location: Bled, Slovenia

Address: Best Western Hotel Kompas Bled

## Primary authors

- Prof. Tamas SZONYI Eotvos Lorand University and Computer and Automation Institute HAS