Feb. 19 -- intro to _strongly regular graphs_ (ch.2) Def. 2.1 (p.29): graph G = (V,E) where V is a finite set of "vertices" (singular = "vertex") and E is a collection of two-element subsets of V ("edges"). Equivalently, a finite set with a relation that is symmetric and never reflexive. So we're dealing only with _undirected_ graphs -- edge {v,v'} is the same as {v',v} -- without loops {v,v'} or multiple edges. We say v is _adjacent_ to v', or a _neighbor_ of v', in the graph iff {v,v'} is an edge; the latter term suggests _neighborhood_ of v = set of all vertices v' adjacent to v, denoted G(v). Also we can say v is "incident" with an edge e iff v is one of its two vertices. [Isomorphism and automorphism of graphs as expected: isomorphism G=(V,E) --> G'=(V',E') is a bijection V --> V' that induces a bijection E --> E'; if G=G' this is an automorphism, and automorphisms form a group.] So a graph is at least a 0-(n,2,#E) design, and never a 2-(n,2,\lam) design except in the trivial cases of the _null graph_ (E is empty, \lam=0) or the _complete graph_ (E consists of all 2-element subsets, \lam=1). Graphs that are 1-(n,2,d) designs are called _regular_ of _degree_ d. (In general the _degree_ of a vertex v of G is the number of edges containing it; the text calls this the "valency" (p.30), which makes some sense if you think about organic chemistry and forget double bonds. So a graph is regular iff all vertices have the same degree.) But we already know that we don't expect to do much with 1-designs. How to impose more structure than t=1 (too flabby, except for degree 1 or 2 and their complements) but less than t=2 (only trivial examples)? As suggested by the Petersen graph: Def. 2.4 (p.32) a graph G that is neither null nor complete is _strongly regular_ iff the number of common neighbors of any two vertices v,v' depends only on whether v and v' are equal, adjacent or non-adjacent. In the first case that number is just deg(v) so the graph must be regular. So we have two parameters: n=#V, k=degree. The other two cases give us two more parameters. We say the graph is regular with parameters (n,k,\lam,\mu) if: n vertices; regular of degree k; any two adjacent vertices have \lam common neighbors; any two non-adjacent vertices have \mu common neighbors. [NB: i) excluding null or complete graphs relieves us from the conundrum of an ill-defined \lam or \mu respectively. ii) The book uses \Gamma, and you're welcome to do so too, but G is easier to type or TeX (though no easier to handwrite). iii) I use American spellings but you won't be penalized for using the text's British spellings such as "neighbours" ;-)] Examples: The _complement_ of G@ of a graph G = (V,E) is (V,E@) where E@ is the set of all two-element subsets of V not in E. (Same as the complement of a t-design.) G is regular of degree k iff G@ is regular of degree #V-k-1. G is strongly regular with parameters (n,k,\lam,\mu) iff G@ is strongly regular with parameters (n, n-k-1, \lam@, \mu@) with \lam@ = n-2 + \mu - 2k, \mu@ = n + \lam - 2k (Prop. 2.7 (p.33), using Inclusion-Exclusion; see also Problem 3 on the present problem set. As the text notes, since \lam@ and \mu@ are nonnegative we must have n >= 2k-\lam, n >= 2k - \mu + 2.) (2.8) i) The "triangular graph" T(m) has (m^2-m)/2 vertices, indexed by 2-element subsets of an m-element set S; two are adjacent iff they have an element in common. (So the complement has two pairs adjacent if disjoint.) Parameters: ((m^2-m)/2, 2m-4, m-2, 4) [why?]. We must take m>=4, else the graph is complete (and also null if m<3...). T(4) is the octahedron, complement of 3.K_2: 12--34 13--24 14--23. T(5) is the complement of the Petersen graph, as you can check from its labeling in the introductory handout. These examples may be misleading: for m large enough T(m) has smaller degree than its complement (how large is large enough?). See the second picture on p.35 (Fig. 2.3) for T(9), and note the convention (p.34) for drawing this graph so the picture doesn't become an ugly clutter. Automorphism group contains S_m, and usually equal to it, though with a couple of exceptions -- trivial for m=2, a bit more interesting for m=4. We'll use this to study the structure of S_m later in the course. ii) "square lattice graph" L_2(m): vertices = S x S with #S = m; adjacent iff common coordinate; parameters (m^2, 2m-2, m-2, 2). Why doesn't S x T work if #S does not equal #T? Must have m>1; L_2(2) is a 4-cycle and the complement of 2.K_2 (the only cycles that are strongly regular with our definitions are the 4- and 5-cycle); for L_2(3) see Figure 2.2 (p.34); this graph is its own complement (Problem 5ii = page 45, exercise 4ii). Automorphism group? It contains (and we'll soon easily show it equals) the wreath product of S_m with S_2, with 2*m!^2 elements. iii) (2.9, p.34-35) for r>1 and m>1 the disjoint union r.K_m of r complete graphs of order m is strongly regular with parameters (rm, m-1, m-2, 0) -- the only strongly regular graphs with \mu = 0 (problem 2). See 34-35 for some further quaint terminology involving some of these graphs and their complements. iv) (2.10, p.35: what happens to Paley's construction of Hadamard matrices when q is 1 mod 4?) If q is a prime power congruent to 1 mod 4: _Paley graph_ P(q) with vertices V=k=F_q and x,y adjacent iff x-y is a nonzero square (recall -1 is a square here so this relation is symmetric). Strongly regular with parameters (q, (q-1)/2, (q-5)/4, (q-1)/4). Proof is analogous to what we did for Paley-Hadamard. First few examples: P(5) = pentagon; P(9) = L_2(3). As with 2-designs, we aim to describe, at least in some cases, which parameters (n,k,\lam,\mu) are feasible, and to describe the graphs and automorphisms for the feasible cases. We start with an easy algebraic condition: Proposition 2.6 (p.33): If a strongly regular graph has parameters (n,k,\lam,\mu) then k (k-\lam-1) = (n-k-1) \mu. Proof: double count, of course. Fix x, count edges {y,z} where y is a neighbor of x but z isn't (and does not equal x either). There are k choices for y; for each of them there are k neighbors, of which one is x and \lam are the common neighbors of x and y, so there are k-\lam-1 choices for z. On the other hand there are n-k-1 choices for z, and for each of them there are \mu choices for y, QED. You should verify that the parameters of G@ satisfy this necessary condition iff those of G do, and that the parameters of the graphs we've seen so far (triangular, square lattice, r.K_m, and Paley) satisfy it as well. Next time we'll introduce an adjacency matrix of a graph, and use it to obtain a further necessary condition on n,k,\lam,\mu that is considerably subtler and quite powerful -- e.g. it's the source of the result noted in the introductory lecture that if there is a Moore graph of degree d then d is in {2, 3, 7, 57}.