Chapter21.hpp File Reference

Chapter "Strongly regular graphs and partial geometries" from [A Course in Combinatorics]. More...

Go to the source code of this file.

Detailed Description

Chapter "Strongly regular graphs and partial geometries" from [A Course in Combinatorics].

Parameters of strongly regular graphs

See module ComputerAlgebra/Graphs/Lisp/StrongRegularity.

The adjacency matrix and its eigenvalues

Partial geometries

See module ComputerAlgebra/IncidenceStructures.

Neighbourhood-regular graphs

The "friendship theorem"

Exercise 21Q: "If every two persons have exactly one mutual friend, then there is a politician (who is the friend of everybody (else))."

  • See Exercise 1J in CourseCombinatorics_LintWilson/Chapter01.hpp.
  • According to ComputerAlgebra/Graphs/Lisp/StrongRegularity/plans/general.hpp, we call a graph with loops, such that every two distinct vertices have exactly one neighbour, a "weak design graph with loops".
  • The isomorphism types of weak design graphs with loops correspond exactly to the isomorphism types of projective incidence planes with given polarity (see ComputerAlgebra/IncidenceStructures/Lisp/plans/ProjectivePlanes.hpp).
  • The "friendship theorem" states that every non-empty weak design graph has a dominating vertex:
    1. Weak design graphs with dominating vertices exist exactly for odd vertex numbers, and then there is exactly one isomorphism type, namely the disjoint union of triangles, all glued together at one common vertex.
    2. Considered as a (polar) incidence structure, these are the "near-pencils". Note that near-pencils have other polar representations, which correspond to weak design graphs with loops, where the underlying graph has a dominating vertex. (There is just one near-pencil with n points, but ceil(n/2) polar representations (always w.r.t. the appropriate isomorphisms).)
    3. Proving, that no non-empty weak design graph without dominating vertex exists, is done in the book by first employing Exercise 1J, from which we get that we must have a non-empty design graph without dominating vertex (that is, we have regularity), and then showing using the eigenvalue-conditions that this is impossible.
    4. The (directly) equivalent statement for projective incidence planes is, that every projective incidence plane with a polarity without absolute points (i.e., every point is mapped to a line not incident with that vertex) is empty or a pencil (has a line containing all points) or a near-pencil (has a line containing all vertices except of one).
    5. Important here: Isomorphisms are considered for projective incidence planes (not for polar projective planes!).
    6. Since empty projective planes, pencils and near-pencils are degenerated projective planes, this is typically expressed by "Polarities for projective incidence planes must have absolute points."

Definition in file Chapter21.hpp.