In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Brouwer–Haemers graph is a 20- regular

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

with 81 vertices and 810 edges. It is a

strongly regular graph In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have comm ...

, a

distance-transitive graph In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carrie ...

, and a

Ramanujan graph In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders. AMurty's survey papernotes, Ramanu ...

. Although its construction is folklore, it was named after

Andries Brouwer Andries Evert Brouwer (born 1951) is a Dutch mathematician and computer programmer, Professor Emeritus at Eindhoven University of Technology (TU/e). He is known as the creator of the greatly expanded 1984 to 1985 versions of the roguelike compute ...

and Willem H. Haemers, who proved its uniqueness as a strongly regular graph.

Construction

The Brouwer–Haemers graph has several related algebraic constructions. One of the simplest is as a degree-4 generalized

Paley graph In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, ...

: it can be defined by making a vertex for each element in the

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...

GF(81)

and an edge for every two elements that differ by a

fourth power In arithmetic and algebra, the fourth power of a number ''n'' is the result of multiplying four instances of ''n'' together. So: :''n''4 = ''n'' × ''n'' × ''n'' × ''n'' Fourth powers are also formed by multiplying a number by its cube. Further ...

Properties

The Brouwer–Haemers graph is the unique

with parameters (81, 20, 1, 6). This means that it has 81 vertices, 20 edges per vertex, 1 triangle per edge, and 6 length-two paths connecting each non-adjacent pair of vertices. As a strongly regular graph with the third parameter equal to 1, the Brouwer–Haemers graph has the property that every edge belongs to a unique triangle; that is, it is locally linear. Finding large dense graphs with this property is one of the formulations of the Ruzsa–Szemerédi problem. As well as being strongly regular it is a

History

Although Brouwer writes that this graph's "construction is folklore", and cites as an early reference a 1964 paper on

Latin square In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...

s by Dale M. Mesner, it is named after

and Willem H. Haemers, who in 1992 published a proof that it is the only strongly regular graph with the same parameters.

Related graphs

The Brouwer–Haemers graph is the first in an infinite family of

s defined as generalized

s over fields of characteristic three. With the

3\times 3

Rook's graph In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...

and the Games graph, it is one of only three possible strongly regular graphs whose parameters have the form

\bigl((n^2+3n-1)^2,n^2(n+3),1,n(n+1)\bigr)

. It should be distinguished from the Sudoku graph, a different 20-regular 81-vertex graph. The Sudoku graph is derived from

Sudoku Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...

puzzles by making a vertex for each square of the puzzle and connecting two squares by an edge when they belong to the same row, column, or

3\times 3

block of the puzzle. It has many 9-vertex

cliques A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

and requires 9 colors in any graph coloring; a 9-coloring of this graph describes a solved Sudoku puzzle. In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.

References

{{DEFAULTSORT:Brouwer-Haemers Graph Individual graphs Strongly regular graphs