Course in algebraic combinatorics - 2007

Syllabus | Lecture notes Assignments (slo) | Projects (slo) | Literature | Library (slo)

Obvestila

Brouwer's tabele of strongly regular graphs on at most 1300 vertices.

11.jun. Take home exam for undergraduates (deadline June 15 2007).

8.jun. Student talks will be on June 17 at 15:00.

Lectures: Friday 12-14:00
Jadranska 21 (3.05).

Instructor: Aleksandar Jurišić
Office: Jadranska 21/0.05
Tel: 4778-638,
(home 28-32-895)
e-mail: ajurisic@valjhun.fmf.uni-lj.si,

Tutorials: Tuesday 10-12
Jadranska 21 (FRI).

TA: Matjaž Urlep
Office : Jadranska 21/0.06
Tel: 47-68-183
e-mail: matjaz.urlep@fri.uni-lj.si

Lectures, Winter/Spring Term '07:

February 16: Introduction, (I) CONSTRUCTIONS: incidence struktures, t-designs, a two-way counting, projective planes, projective spaces, examples.
February 23: PG(2,2), PG(2,3), PG(2,4), Fisher inequality, square designs, Orthogonal Arrays (OA), some constructions and bounds for OA.
March 2: (II) GRAPHS, EIGENVALUES AND REGULARITY: the number of distinct eigenvalues, review of some matrix theory, eigenvalues of components, regularity and bipartitness, eigenvalues of the complement with one example (application: the eigenvalues of complete and complete multipartite graphs), eigenvalues of the line graph, Gram matrix and its application (Peron-Frobenious theorem and eigenvalue interlacing).
March 9: (I) Hadamard matrices (as extreme matrices, definition, Hadamard matrix conjecture, small examples, recursive construcions, conference matrices and 2-desigs),
(III) STRONGLY-REGULAR GRAPHS (SRG): regularities, definitions, examples of SRG, trivial examples, connection between parameters, complement SRG, adjacency matrices and eigenvalues.
March 16: connected graphs with precisely three eigenvalues, a classification, Paley graphs, Krein condition, Smit graphs, the graphs of (negative) LS type (LS=Latin Squares), TD graphs, Steiner graphs, uniqueness of strongly regular graphs for some special cases of parameters and super-exponently many graphs in some other cases of very similar parameters; Neumaier theorem.
March 23: small feasible parameter sets, small examples (P(13), Tutte's 8-cage, Clebsch graph, Shrikhand graph, Schlaefly graph), Moore graphs, a famous open problem (3250).
(IV) PARTIAL GEOMETRIES: definition, classification, pseudo-geometic graphs, quadratic forms, isotropic spaces.
March 30: classical generalized quadrangles, small examples,
(V) ASSOCIATIVE SCHEMES: definition, Bose-Mesner algebra, the trivial scheme.
April 6: schemes with two classes, examples (Hamming scheme H(d,n), Billinear Forms Scheme BFS(d,m,q), Johnson scheme J(n,d), Grassman scheme J_q(n,d) and Cyclomatic scheme C(q,d)), axiom verification and symmetry, primitivity and imprimitivity, two bases and duality (minimal idempotents, eigenvalues and dual eigenvalues, Krein parameters.
April 13: expressions for Krein parameters, Krein bound, Absolute bound, metric and cometric associative schemes, vanishing of Krein parameters and strongly regular graphs.
(VI) EQUITABLE PARTITIONS: definition, orbits of group action, characteristic vectors and matrices, quotient, eigenvalues, covers, antipodal covers.
April 20: (VII) DISTANCE-REGULAR GRAPHS: definition, an example, distance-transitive graphs, intersection numbers and their properties, eigenvalues, imprimitive distance-regular graphs and Smith theorem, classification, classical families and parametrization with Gauss coefficients, antipodal distance-regular graphs, bipartite doubles.
Apr. 27 to be held on Juny 1
May 4: antipodal distance-regular graphs: Gardiner theorem, connections, tools, goals.
May 11: theorem about old and new eigenvalues, antipodal covers of small diameter: (d=3) Lemma about locally cyclic distance-regular graphs, Platonic solids with triangle faces (tetrahedron, cube, icosahedron) Klein graph and Mathon constructio; (d=4 and 5) intersection array and all intersection numbers, eigenvectors, multiplicities, Krein parametes and Q-polynomial property, list of feasible parameters.
May 18: (VIII) 1-HOMOGENEOUS GRAPHS: examples, locally disconnected 1-homogeneous graphs, locally strongly regular, local approach and the CAB property, classification of locally Moore 1-homogeneous graphs, classification of Terwilliger graphs with c₂ > 1.
May 25: cosinus sequence, moduls.
(IX) TIGHT GRAPHS: eigenvalues of a connected regular graph Terwilliger theorem about the bounds for the local eigenvalues, characterization of tight graphs with the 1-homogeous property a_d=0, with local eigenvalues,...
1. jun. parametrization with two cosine sequences, characterization of tight graphs with certain parametrization using d+1 parameters, AT4 family, Conjecture, Classification of AT4(sq,q,q), uniqueness of the Patterson graph,
June 17: presentations of projects and a short lecture on uniqueness of distance-regular graphs.

All postscript (ps) files see Ghostscript and GSview, that are available for most operating systems and browsers.

Course Syllabus

Course Outline: We will study an interplay between algebra and combinatorics that is known under the name algebraic combinatorics. This can be considered to be a part of discrete mathematics, where objects or structures have certain degree of regularity or symmetry. Some important applications of algebraic combinatorics are coding theory/error correction codes, theory of statistical design and (through finite geometries and finite fields) also cryptography. We will encounter several interesting (constructions of) combinatorial objects. One of the aims of this course is a general introduction to algebraic combinatorics and some illumination of important achivements in the last 50 years.

Topics covered will be drawn from the following partial list.

t-designs
Latin squares, transversal designs and orthogonal arrays,
Hadamard matrices and recursiv construcions (Reed-Muller codes of first order),
Conference matrices,
Paley matrices and graphs,
Strongly-regular graphs,
Partial geometries,
Associative schemes,
Equitable partitions,
Distance-regular graphs,
1-homogeneous graphs,
Tight graphs.

Literature (Textbooks):

L. M. Batten, Combinatorics of Finite Geometries, Cambridge University Press, 2. izdaja, 1997.
N.L. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 2nd edition, 1994.
N.L. Biggs in A. T. White, Permutation groups and combinatorial structures, Cambridge University Press, Cambridge, 1979.
P. J. Cameron, Projective and Polar Spaces, QMW Maths Notes, 1991.
P. J. Cameron in J. H. van Lint, Designs, Graphs, Codes and Their Links, London Math. Soc. Student Texts 22, Cambridge Univ. Press, Cambridge, 1991.
J.D. Dixon in B. Mortimer, Permutation groups, Springer, New York, 1996.
C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
C. D. Godsil in G. Royle, Algebraic Graph Theory Springer Verlag (New York), 2001.
J. H. Van Lint in R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2. izdaja, 2001.

Reference books:

A. E. Brouwer, A. M. Cohen in A. Neumaier, Distance-Regular Graphs, Springer, New York, 1989.
C. J. Colbourn in J. Dinitz (urednika), CRC Handbook of Combinatorial Designs, CRC-Press, 1996.
R. L. Graham, M. Groetschel, L. Lovasz (uredniki), Handbook of Combinatorics: 2-volume set, MIT Press, 1996.
F. Buekenhout (urednik), Handbook of Incidence Geometry: Buildings and Foundations, North-Holland, 1995.

Assignments:

I recommend to excercise your mind also within a team study (where each individual has an opportunity to test his/her proposals and questions) and extensive problem solving. At least 5 questions per week will be given in class (handed solutions will be graded).
A few sets of assignments will be handed and you are expected to do a shorter project.