MIT Combinatorics Seminar

Subsets with minimal width and dual width in Q-polynomial distance-regular graphs

Hajime Tanaka  (Worcester Polytechnic Institute, visiting MIT)

Wednesday, April 18, 2007    4:15 pm    Room 2-136


The study of Q-polynomial distance-regular graphs is an active area of research. Many important examples arise on the top fibres of certain meet semilattices, such as truncated Boolean semilattices and direct products of "claw semilattices".

In 2003, Brouwer, Godsil, Koolen and Martin introduced the width w and the dual width w* of a subset in a Q-polynomial distance-regular graph. They showed that w+w* is at least the diameter D of the graph, and that if equality holds then the subset has a lot of strong regularities. For graphs associated with nice semilattices, those subsets satisfying w+w*=D arise quite naturally within the semilattice structures, and they are expected to play a role in the classification of Q-polynomial distance-regular graphs.

On the other hand, recently it is turning out that the subsets with w+w*=D also play a fundamental role in e.g., coding theory. In this talk, I will briefly discuss some of the applications of the theory of these subsets. Topics include the Erdos-Ko-Rado theorem in extremal set theory, the Assmus-Mattson theorem in coding and design theory, and orthogonal polynomials from the Askey scheme.