Why is a block graph of a Steiner Triple System is a Strongly Regular Graph?

With parameters: srg(v(v-1)/6, 3(v-3)/2, (v-3)/2, 9)

Should be straightforward counting which alludes me...

Thanks!

Shay

-

It's been a time since I learned something about STS, but let's have a try.

There are of course $\frac{v(v-1)}{6}$ vertices in your srg since there are $v(v-1)$ pairs when you have $v$ elements, and there are 6 pairs when you have 3 elements, so each triple is counted 6 times.

Each element is contained in $v-1$ pairs, so we get $3(v-1)$ triples that are adjacent with a given triple, but we counted each triple twice and of course we also counted the current triple three times so the degree is $\frac{3(v-1)}{2}-3=\frac{3(v-3)}{2}$.

When we have two adjacent triples, then there are $\frac{v-5}{2}$ triples that also contain the common element between these two adjacent triples and there are also 4 triples that contain one of the other elements of the first triple and one of the other elements of the second triple. This means $\lambda=\frac{v-5}{2}+4=\frac{v+3}{2}$ (so it is + 3 and not -3 as you posted.)

When we have two non-adjacent triples then there are 9 possible pairs such that one element belongs to the first triple and one element belongs to the second triple, so $\mu=9$.

-
Please feel free to ask for clarifications where needed, because I'm terrible at using correct terminology. –  nvcleemp Jul 15 '11 at 15:06
Your counts of $v(v-1)$ pairs in $[v]$ and $6$ pairs in $[3]$ are really ordered pairs. The conditions are over unordered pairs, so you should say it is ${v \choose 2} / {3\choose 2}$. Since the factors of two cancel, you get the same number, but your reasoning isn't perfect. –  Derrick Stolee Jul 15 '11 at 19:51
Uhu, you're completely right. blush –  nvcleemp Jul 16 '11 at 6:22