Algebra and Geometry

What used to be 2WF02 is now 2WF05. Old: trimester course - New: semester course

No lectures on June 21.

Exercises Send answers/solutions to aeb@cwi.nl. Results.

Submit solutions to the final problem (well) before Sept 1. Give correct proofs, not just statements or final answers. Pick one problem from the list (that is still almost empty today) and claim it for yourself. The weekly problems were submitted by groups. Do the final problem on your own.

Problems

1. (Taken) Let H be any fixed finite graph. Show that H is an induced subgraph of the Paley graph of order q when q is sufficiently large.

2. Let G be a graph with eigenvalues θ_i (i=1,...,n). Show that for any two vertices x and y of G there are constants c₁,...,c_n such that the number of walks of length h from x to y equals Σ c_i θ_i^h for all h.

3. (Taken) Show that the character table of a finite group G is the suitably scaled P matrix for a (not necessarily symmetric) association scheme.

4. (Taken) Consider the graph on the set of flags (incident point-line pairs) of the projective plane PG(2,4), where (p,L) and (q,M) are adjacent when p,q,L,M are distinct and either p lies on M or q lies on L. Show that this graph is strongly regular with parameters (v,k,λ,μ) = (105,32,4,12). What can be said about maximal cliques and maximal cocliques in this graph?

5. (Taken) Fix a Steiner system S(3,6,22) on a 22-set X. Consider the graph that has as vertices the pairs of symbols from X, where two pairs are adjacent when they are disjoint and their union is contained in a block of the Steiner system. Show that this graph is strongly regular with parameters (v,k,λ,μ) = (231,30,9,3). What can be said about maximal cliques and maximal cocliques in this graph?

6. (Taken) Let G be a strongly regular graph with parameters (v,k,0,μ), and let x be a vertex. Let H be the induced subgraph of G on the vertices other than x and nonadjacent to x. Compute the spectrum of H. When is H itself strongly regular? Determine all possible G when f = k, where f is the multiplicity of the positive eigenvalue other than k.

7. (Taken) Show that a set of points in Euclidean n-space such that the distance between any two of them takes only 2 values, has size at most (n+1)(n+2)/2. Can equality hold?

8. (Taken) Consider a primitive strongly regular graph G on v vertices with eigenvalues k,r,s with respective multiplicities 1,f,g (with k > r > 0 > s). Assume that G has a proper vertex coloring with 1-k/s colours. (Proper: the vertices are colored such that adjacent vertices have different colors.) Consider the four relations on the vertex set X of G: R₀: identity, R₁: being adjacent in G, R₂: being nonadjacent with the same color, R₃: being nonadjacent with different colors. Prove that these relations define an association scheme on the vertex set of G, and determine the matrices P and Q.

9. (Taken) Determine the spectrum of the graph obtained from a strongly regular graph by deleting one or two vertices.

10. (Taken) Show that a connected regular graph with d+1 distinct eigenvalues and girth at least 2d-1 is distance-regular.

11. Compute the character table of the alternating group Alt(6) (of order 6!/2 = 360).

...

Some notes: Lattices (dvi, pdf), Spectra of some small graphs (dvi, pdf). Spectra of graphs (pdf).

Old Notes: Golay (dvi, pdf), Much more detail on Witt designs, Golay codes, Mathieu groups (dvi, pdf), Leech (dvi, pdf), Graph spectra and Perron-Frobenius theorem (html). Much more detail on graph spectra (pdf). Chevalley-Warning, quadrics (dvi, pdf), Ovals and conics (dvi, pdf), Generalized quadrangles (dvi, pdf), Representations of finite groups (dvi, pdf). Coherent configurations (dvi, pdf), Groups and graphs (dvi, pdf), Buekenhout-Tits geometries (dvi, pdf).

Very old notes: Gröbner bases (dvi, pdf), p-adic numbers (dvi, pdf), Nullstellensatz (dvi, pdf), Bezout's theorem (dvi, pdf), Resultant, discriminant (dvi, pdf), Varieties (first definitions) (dvi, pdf), Dimension (definition) dvi, pdf), Hilbert function (dvi, pdf), Zeta function (dvi, pdf), Blowup (dvi, pdf), Elliptic functions (dvi, pdf), Mordell (dvi, pdf). Genus of a plane curve (dvi, pdf), Regular differential forms (dvi, pdf), Riemann-Roch (dvi, pdf).

Topics:
- Spectrum of graphs. Adjacency, Laplace, Seidel matrix.
- Friendship theorem. Spectrum of strongly regular graphs.
- Paley graphs.
- Perron-Frobenius theorem.
- Classification of graphs with largest eigenvalue at most 2.
- Interlacing.
- Very first intro to lattices and modular forms.
- Steiner triple systems and Latin squares.
- Steiner systems, Golay codes, Leech lattice, sporadic simple groups.
- Classification of root lattices.
- Chevalley-Warning.
- Projective geometry. Polar spaces. Generalized quadrangles.
- (Hyper)ovals in a projective plane, number of absolute points of a polarity
- Quadratic forms, Witt index.
- Intro symplectic, orthogonal and unitary geometry.
- Association schemes. Delsarte LP.
- Bounds on the size of (co)cliques and chromatic number.
- Krein parameters and absolute bound for association schemes.
- Restrictions on automorphisms of association schemes.
- Sign patterns in the eigenmatrices of a P- or Q-polynomial association scheme.
- Linear representations of finite groups.
- Buekenhout-Tits geometries.
- Two-weight codes, projective two-intersection sets, and strongly regular graphs.
- Equiangular lines.
- Majorization order, theorems of Schur, Courant-Weil, Ky Fan, Gale-Ryser.
- Grone-Merris conjecture, Hua Bai theorem.

Literature

A.E. Brouwer, A.M. Cohen & A. Neumaier, Distance-regular graphs, Springer, 1989.

J.H. Conway & N.J.A. Sloane, Sphere Packings, Lattices and Groups, Springer, 1988.

Jean-Pierre Serre, A Course in Arithmetic, Springer, 1973.

A.E. Brouwer & W.H. Haemers, Spectra of Graphs, Springer, 2012.