No lectures on June 21.
Exercises Send answers/solutions to email@example.com. 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.
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 c1,...,cn such that the number of walks of length h from x to y equals Σ ci θih 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: R0: identity, R1: being adjacent in G, R2: being nonadjacent with the same color, R3: 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).
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).
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.