# Syllabus
The content below will be expanded in detail as the course progresses. It is important that there is sufficient detail in order for John B. being clear about what needs to be done each week in MATH4033.
:::warning
It is currently Week 10
:::
## Goals
:::info
- An introduction to algebraic graph theory and association schemes.
- Formal duality of the sphere-packing bound for codes and Fisher's inequality for designs.
- To understand the rank bound (for $T$-codes of association schemes) and apply it to something.
:::
## Week 1
### Content
- Graphs, paths, connected components, walk, isomorphism
- adjacency matrix, eigenvalues and eigenvectors, isomorphism revisited (permutation matrices), complete graph spectrum
- linear algebra: characteristic poly, diagonalisation, symmetric matrices (real eigenvalues)
- complement graph and spectrum
### Reading
- Read 8.1, 8.4, 8.5 of Godsil and Royle.
- Read 1.1 (mostly just need adjacency matrix), 1.2, 1.3 (Prove Proposition 1.3.1) of Brouwer and Haemers.
### Tasks
1. Do the following example in GAP:
```gap
LoadPackage("grape");
subsets := Combinations([1..5], 2);
adjacency := {x,y} -> IsEmpty(Intersection(x,y));
graph := Graph(Group(()), subsets, OnSets, adjacency);
VertexDegrees(graph);
A := CollapsedAdjacencyMat(Group(()),graph);
Display(A);
Eigenvalues(Rationals, A);
espaces := Eigenspaces(Rationals, A);
List(espaces, Dimension);
graph2 := ComplementGraph( JohnsonGraph(5,2) );
IsIsomorphicGraph(graph, graph2);
G := AutomorphismGroup(graph);
IsTransitive(G);
```
2. Make a derangement graph and compute its spectrum. In particular, take the elements of a primitive group $G$ and construct the _derangement graph_ of it. So $x$ and $y$ are adjacent if $xy^{-1}$ is fixed-point-free.
3. Prove (or lookup a proof) that every eigenvalue of a graph is at most the maximum degree of the graph. Make sure this is in the mathematical journal and all prerequisite material.
## Week 2
### Content
- What does $A^2$ tell us?
- Walks and closed walks, algebraically
- "Good Will Hunting" example.
- The Perron-Frobenius Theorem (a simplified version).
- Connectedness, bipartite graphs.
### Reading
- Section 1.3.3 of _Spectra of graphs_.
- Section 2.2 of _Spectra of graphs_.
- Section 3.4 of _Spectra of graphs_
Section 8.8 of Godsil and Royle is also useful.
### Tasks
1. Do the following example in GAP (click on "Details").
:::spoiler
```gap
LoadPackage("grape");
G := TransitiveGroup(30,264);
StructureDescription(G);
gens := [ (1,8)(2,5,11,12)(3,7,4,9)(10,14,13,15)(16,21,26,25)(17,29,19,23)(18,20)(22,
30,28,27), (1,11,5)(2,12,8)(3,10)(4,7,15,13,14,9)(16,25,29,28,30,23)(17,
22,21,19,26,27)(18,20,24) ];;
H := Group(gens);
cosets := AsList(RightCosets(G,H));;
dcs := DoubleCosets(G,H,H);;
D := First(dcs, t -> Size(t) = 144);;
graph := Graph(G, cosets, OnRight,
{x,y} -> x<>y and Representative(x) / Representative(y) in D);;
IsBipartite(graph);;
# This is the strange way GAP computes an adjacency matrix
A := CollapsedAdjacencyMat(Group(()), graph);;
List(A, Sum);
VertexDegrees(graph);
# To see the matrix in a nice compressed way ...
Display( A * Z(2) );
evalues := Eigenvalues(Rationals, A);
# Now let's look at walks
Asq := A^2;;
Display( Asq * Z(2) );
List(Asq, Sum);
# There are no m-cycles for m < 8. In particular, no triangles.
Girth(graph);
Acube := A^3;;
Display( Acube * Z(2) );
TraceMat(Acube);
```
:::
2. Update the mathematical journal.
3. Solve "Good Will Hunting" puzzle (Q1 and Q2).
## Week 3
### Content
- strongly regular graphs (e.g., line graph of $K_n$, Latin square graphs)
- __Theorem:__ 3 distinct eigenvalues and connected $\iff$ strongly regular
- conditions on the existence of srg: complement is an srg, double-count on parameters.
- Bose-Mesner algebra of srg, idempotents, Krein conditions, Schur product theorem
- Ratio bound for cocliques
- Ratio bound for cliques
- Clique-Coclique Theorem for srg's
### Reading
- Skim read the beginning of 9.1 (up to 9.1.5) of _Spectra of graphs_ (esp. Theorem 9.1.2, Theorem 9.1.3)
- Intro to Chapter 10 of Godsil & Royle (esp. 10.1, 10.2).
- Skim read Chapter 21 of van Lint & Wilson (up to Theorem 21.3).
- Theorem 3.5.2 of _Spectra of graphs_.
### Tasks
- Update mathematical journal.
- Construct a 5x5 Latin square, and compute
- the parameters of the corresponding strongly regular graph
- find the eigenvalues of the strongly regular graph and their multiplicities.
## Week 4
### Content
- Designs
- Incidence matrices
- Fisher's Inequality
- Quasisymmetric designs
### Reading
- Chapter 19 of van Lint & Wilson. In particular ...
- Theorem 19.1 (Fisher's Inequality for linear spaces)
- Equations 19.3 and 19.4.
- The incidence matrix of a design and Equation 19.7.
- Theorem 19.6 (Fisher's Inequality for $2$-designs)
- Part of Chapter 21 of van Lint & Wilson and quasisymmetric designs.
- Theorem 21.2.
### Tasks
- What is a design, and what is $t-(v,k,\lambda)$ design?
- Understand the proof of Fisher's Inequality thoroughly.
- Show that every $2-(v,k,1)$ design is quasisymmetric.
## Week 5
### Content
- Codes, linear codes, parameters
- Distance between codewords (pre-metric), sphere of radius $r$.
- Minimum distance.
- The Sphere-packing bound.
### Reading
- Chapter 20 of van Lint & Wilson:
- Read all of pages 244 -- 246.
- Theorem 20.1 is the _Sphere packing bound_.
- Jump ahead to Theorem 20.4. There is a very long proof here! It does not need to go in the journal, but you could point to it still.
### Tasks
- What is a code? What is a linear code? What is the _length_, _alphabet_, _codewords_ of the code? What is the dimension of a linear code?
- What has mininum distance got to do with the error correcting properties of a code? You might need to find another resource that fills this gap.
- Understand Example 20.4, including knowing what each object means (e.g., $R(1,3)$).
- Do the following in GAP:
```gap
LoadPackage("guava");
C := NordstromRobinsonCode();
codewords := AsList(C);
MinimumDistance(C);
WordLength(C);
```
## Week 6
### Content
- Intro to association schemes, via relations and matrices, examples.
- Srgs as association schemes, Hamming and Johnson schemes, Grassmann scheme.
- Generously transitive groups.
- Bose-Mesner algebra, intersection matrices and intersection algebra.
- _Theorem:_ The Bose-Mesner Algebra of an association scheme is isomorphic to its intersection algebra.
### Reading
- Chapter 30 of van Lint & Wilson
- Read up to (and including) p368.
- Chapter 11 of _Spectra of Graphs_ (Brouwer and Haemers)
- 11.1 and the first paragraph of 11.2.
- In particular, they give the intersection matrices of a strongly regular graph on p166.
- Section 3.2 of Peter Cameron's "Permutation groups".
_Recommended:_ Section II.2 of Bannai and Ito's "Algebraic Combinatorics I: Association schemes". In particular, Theorem 2.3.
:::info
An _association scheme_ in this unit will be a symmetric coherent configuraiton. The definition is not consistent in the literature. Bannai and Ito have "association scheme=homogeneous CC", and Delsarte has "association scheme=commutative CC". It turns out that
symmetric implies commutative implies homogeneous. So we are adopting the strongest definition (and so do van Lint & Wilson, and Brouwer & Haemers).
:::
### Tasks
- Download `AssociationSchemes` package from [here](https://www.jesselansdown.com/AssociationSchemes/).
- Find out what _generously transitive_ means.
- Take the adjacency matrix $A$ for the Petersen graph, and do the following in GAP:
```code=gap
LoadPackage("assoc");
rel_matrix := 2 - A - 2 * One(A);
Display(rel_matrix);
scheme := AssociationScheme(rel_matrix);
P := MatrixOfEigenvalues(scheme);
Display(P);
G := AutomorphismGroup(scheme);
StructureDescription(G);
IsGenerouslyTransitive(G);
BMalgebra := BoseMesnerAlgebra(scheme);
intalgebra := IntersectionAlgebraOfHomogeneousCoherentConfiguration(scheme);
lambda := IntersectionNumber(scheme, 1, 1, 1);
mu := IntersectionNumber(scheme, 2, 1, 1);
```
---
Mid-semester break
---
## Week 7
### Content
- Simultaneous diagonalisation, spectral theorem, projections and idempotents
- Minimal idempotents
- Matrix of eigenvalues (character table)
- Matrix of dual eigenvalues, change of basis
- Orthogonality relations
### Reading
- [Godsil's notes](https://www.math.uwaterloo.ca/~cgodsil/pdfs/assoc2.pdf), Sections 1.4 and 1.5.
- van Lint & Wilson, pages 410 -- 413 (skip over Examples 30.6, 30.7)
- Brouwer & Haemers (_Spectra of graphs_), 11.2
- The "formal duality" chart can be found in [Seidel's notes](https://www.emis.de/journals/SLC/opapers/s26seidel.html).
### Tasks
- Update mathematical journal.
- Continue the last example of GAP code:
:::spoiler
```code=gap
Q := MatrixOfDualEigenvalues(scheme);
Display(Q);
Display(P*Q);
idems := MinimalIdempotents(scheme);
List(idems, RankMat);
List(idems, TraceMat);
Q[1];
espaces := Eigenspaces(Rationals, A);
List(espaces, Dimension);
Display(idems[2]);
Display(idems[2]^2);
Display(idems[2]*idems[3]);
# look at the second column of P
Display(P);
matrix := 3*idems[1] + 1*idems[2] - 2*idems[3];
matrix = A;
# look at the third column of P
matrix := 6*idems[1] - 2*idems[2] + 1*idems[3];
# J - A - I
matrix = 1 - A - One(A);
# look at the second column of Q
Display(Q);
adjs := AdjacencyMatrices(scheme);;
matrix := (5 * adjs[1] + 5/3 * adjs[2] - 5/3 * adjs[3]) / 10;
matrix = idems[2];
```
:::
## Week 8
### Content
- Krein parameters
- _Theorem:_ The Krein parameters are non-negative real numbers.
- Distance regular graphs and intersection numbers
- P-polynomial association schemes
- Q-polynomial association schemes
### Reading
- van Lint & Wilson (for this material, they are not very comprehensive):
- p.379 (Krein parameters ...)
- p.366 (Distance regular graphs and metric association schemes)
- p.381 (P-polynomial, Q-polynomial)
- Brouwer and Haemers:
- 11.4 (Krein parameters, esp. Theorem 11.4.2)
- Chapter 12 (All about Distance regular graphs)
- Read 12.1, 12.2
- Skim read 12.4
- 12.5: It's worth knowing the Bannai-Ito Conjecture, just for context.
- 11.6 (P-polynomial if and only if metric. Q-polynomial schemes)
### Tasks
- Update mathematical journal.
- Have a look at [this paper](https://www.sciencedirect.com/science/article/pii/S0097316507001495). Some of it you will understand. What are _triple intersection numbers_ and how do they relate to Krein parameters?
## Week 9
### Content
- Inner distribution
- Degree and dual degree
- T-codes
- T-codes of Hamming scheme are codes
- MacWilliams transform
- Delsarte's LP-bound
- T-designs
- T-designs of Johnson scheme are t-designs
- Sphere-packing bound and Fisher's inequality revisited
### Reading
- van Lint & Wilson: pp.375--380
- Brouwer & Haemers: Section 11.3 (skip 11.3.1)
### Tasks
- Update mathematical journal.
- Just like the "Example" in Brouwer and Haemers (p.168), show that the maximum number of 3-dimensional subspaces of $\mathbb{F}_2^7$ that pairwise intersect in a subspace of dimension 0 or 1, is no more than 381. (Hint: You should use a Grassmann Scheme. The number of 3-spaces that intersect a given one in a 2-space is 210).
## Week 10
### Content
- Clique and coclique bounds
- Roos' Theorem
- Schurian schemes
- Separating permutation groups
### Reading
- Brouwer & Haemers: Theorem 3.5.2, Theorem 11.3.3,
- [Godsil's notes](https://www.math.uwaterloo.ca/~cgodsil/pdfs/assoc2.pdf), Lemma 3.4.1
- Section 2 of [Bamberg, Giudici, Lansdown, Royle](https://arxiv.org/abs/2104.13355). (Especially that which relates to separating permutation groups).
Curiously, good references for Schurian schemes are hard to find, but here are some:
- Bannai and Ito, "Algebraic Combinatorics I"
- Godsil and Meagher, "Erdős-Ko-Rado Theorems: Algebraic Approaches"
- Peter Cameron, "Permutation groups"
### Tasks
- Update mathematical journal
## Week 11/12
### Content
- Rank bound and spherical codes
### Reading
- Theorem 4.8, Example 4.9 of [Delsarte, Goethals, Siedel](https://link.springer.com/article/10.1007/BF03187604)
- [Baller et al.](https://arxiv.org/abs/1606.06620)
- John's notes
### Tasks
- Update mathematical journal
Sign in with Wallet
Connect another wallet