[Turkmath:7406] Koc Universitesi Matematik Semineri

[Kazim Buyukboduk]

MATHEMATICS SEMINAR

Date     : 30th December, Thursday*
Time     : 16:00
Place    : ENG B42**, Faculty of Engineering, Koc University RF Campus

Refreshments will be served at 15:45


*Note the unusual day
**Note the unusual location


Çiçek Güven
Technische Universiteit Eindhoven
Mathematics

“Cocliques in the Kneser graph on the point-hyperplane flags of a
projective space”

ABSTRACT

The point-hyperplane Kneser graph is defined on the point-hyperplane
flags (P;H) where the point P is in the hyperplane H of n-dimensional
vector space V over F(q). Two flags (P;H), and (P0;H0) are adjacent
if P is not in H0 and P0 is not in H. The problem is to find the maximal
cocliques in this graph, so it is analogous to the Erdös-Ko-Rado
theorem describing the maximal cocliques in the classical Kneser graph
K(n; k).

This problem is solved in a recent paper with Aart Blokhuis and
Andries E. Brouwer. The size of maximal colciques is proved to be
1+2q+3q2+:::+(n¡1)q(n¡2). The maximal number of points involved
in a maximal coclique is proved to be 1 + q + q2 + ::: + q(n¡2), which is
the number of points in a hyperplane in an n-dimensional vector space.
Since the problem is self dual, this is also the number of hyperplanes
invloved in a maximal coclique. For the number of points involved, the
characterization of the maximal cocliques where this bound is attained
is also done. In this talk, I will describe the proof of the results of this
work.