mathematics 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 ...

, a two-graph is a set of (unordered) triples chosen from a finite vertex set ''X'', such that every (unordered) quadruple from ''X'' contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph. Two-graphs have been studied because of their connection with

equiangular lines In geometry, a set of lines is called equiangular if all the lines intersect at a single point, and every pair of lines makes the same angle. Equiangular lines in Euclidean space Computing the maximum number of equiangular lines in ''n''-dimensi ...

and, for regular two-graphs,

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 ...

s, and also

finite group Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...

s because many regular two-graphs have interesting

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

s. A two-graph is not a graph and should not be confused with other objects called 2-graphs in

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 conne ...

, such as 2-regular graphs.

Examples

On the set of vertices the following collection of unordered triples is a two-graph: :123 124 135 146 156 236 245 256 345 346 This two-graph is a regular two-graph since each pair of distinct vertices appears together in exactly two triples. Given a simple graph ''G'' = (''V'',''E''), the set of triples of the vertex set ''V'' whose induced subgraph has an odd number of edges forms a two-graph on the set ''V''. Every two-graph can be represented in this way. This example is referred to as the standard construction of a two-graph from a simple graph. As a more complex example, let ''T'' be a tree with edge set ''E''. The set of all triples of ''E'' that are not contained in a path of ''T'' form a two-graph on the set ''E''.

Switching and graphs

Switching in a graph A two-graph is equivalent to a switching class of graphs and also to a (signed) switching class of signed complete graphs. Switching a set of vertices in a (simple) graph means reversing the adjacencies of each pair of vertices, one in the set and the other not in the set: thus the edge set is changed so that an adjacent pair becomes nonadjacent and a nonadjacent pair becomes adjacent. The edges whose endpoints are both in the set, or both not in the set, are not changed. Graphs are switching equivalent if one can be obtained from the other by switching. An equivalence class of graphs under switching is called a switching class. Switching was introduced by and developed by Seidel; it has been called graph switching or Seidel switching, partly to distinguish it from switching of

signed graph In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. A signed graph is balanced if the product of edge signs around every cycle is positive. The name "signed graph" and the no ...

s. In the standard construction of a two-graph from a simple graph given above, two graphs will yield the same two-graph if and only if they are equivalent under switching, that is, they are in the same switching class. Let Γ be a two-graph on the set ''X''. For any element ''x'' of ''X'', define a graph Γ_''x'' with vertex set ''X'' having vertices ''y'' and ''z'' adjacent if and only if is in Γ. In this graph, ''x'' will be an isolated vertex. This construction is reversible; given a simple graph ''G'', adjoin a new element ''x'' to the set of vertices of ''G'', retaining the same edge set, and apply the standard construction above. To a graph ''G'' there corresponds a signed complete graph Σ on the same vertex set, whose edges are signed negative if in ''G'' and positive if not in ''G''. Conversely, ''G'' is the subgraph of Σ that consists of all vertices and all negative edges. The two-graph of ''G'' can also be defined as the set of triples of vertices that support a negative triangle (a triangle with an odd number of negative edges) in Σ. Two signed complete graphs yield the same two-graph if and only if they are equivalent under switching. Switching of ''G'' and of Σ are related: switching the same vertices in both yields a graph ''H'' and its corresponding signed complete graph.

Adjacency matrix

The adjacency matrix of a two-graph is the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

of the corresponding signed complete graph; thus it is

symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

, is zero on the diagonal, and has entries ±1 off the diagonal. If ''G'' is the graph corresponding to the signed complete graph Σ, this matrix is called the (0, −1, 1)-adjacency matrix or

Seidel adjacency matrix In mathematics, in graph theory, the Seidel adjacency matrix of a simple undirected graph ''G'' is a symmetric matrix with a row and column for each vertex, having 0 on the diagonal, −1 for positions whose rows and columns correspond to adjac ...

of ''G''. The Seidel matrix has zero entries on the main diagonal, -1 entries for adjacent vertices and +1 entries for non-adjacent vertices. If graphs ''G'' and ''H'' are in a same switching class, the multiset of eigenvalues of two Seidel adjacency matrices of ''G'' and ''H'' coincide since the matrices are similar. A two-graph on a set ''V'' is regular if and only if its adjacency matrix has just two distinct

eigenvalues In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

ρ₁ > 0 > ρ₂ say, where ρ₁ρ₂ = 1 - , ''V'', .

Equiangular lines

Every two-graph is equivalent to a set of lines in some dimensional

euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...

each pair of which meet in the same angle. The set of lines constructed from a two graph on ''n'' vertices is obtained as follows. Let -ρ be the smallest

eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

of the

, ''A'', of the two-graph, and suppose that it has multiplicity ''n'' - ''d''. Then the matrix is positive semi-definite of rank ''d'' and thus can be represented as the

Gram matrix In linear algebra, the Gram matrix (or Gramian matrix, Gramian) of a set of vectors v_1,\dots, v_n in an inner product space is the Hermitian matrix of inner products, whose entries are given by the inner product G_ = \left\langle v_i, v_j \right\r ...

of the inner products of ''n'' vectors in euclidean ''d''-space. As these vectors have the same

norm Naturally occurring radioactive materials (NORM) and technologically enhanced naturally occurring radioactive materials (TENORM) consist of materials, usually industrial wastes or by-products enriched with radioactive elements found in the envi ...

(namely,

\sqrt

) and mutual inner products ±1, any pair of the ''n'' lines spanned by them meet in the same angle φ where cos φ = 1/ρ. Conversely, any set of non-orthogonal equiangular lines in a euclidean space can give rise to a two-graph (see

for the construction). With the notation as above, the maximum cardinality ''n'' satisfies ''n'' ≤ ''d''(ρ² - 1)/(ρ² - ''d'') and the bound is achieved if and only if the two-graph is regular.

Notes

References

* Brouwer, A.E., Cohen, A.M., and Neumaier, A. (1989), ''Distance-Regular Graphs.'' Springer-Verlag, Berlin. Sections 1.5, 3.8, 7.6C. * * *

Chris Godsil Christopher David Godsil is a professor and the former Chair at the Department of Combinatorics and mathematical optimization, Optimization in the University of Waterloo Faculty of Mathematics, faculty of mathematics at the University of Waterloo. ...

and

Gordon Royle Gordon F. Royle is a professor at the School of Mathematics and Statistics at The University of Western Australia. Royle is the co-author (with Chris Godsil) of the book ''Algebraic Graph Theory'' (Springer Verlag, 2001, ). Royle is also known ...

(2001), ''Algebraic Graph Theory.'' Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York. Chapter 11. * Seidel, J. J. (1976), A survey of two-graphs. In: ''Colloquio Internazionale sulle Teorie Combinatorie'' (Proceedings, Rome, 1973), Vol. I, pp. 481–511. Atti dei Convegni Lincei, No. 17. Accademia Nazionale dei Lincei, Rome. * Taylor, D. E. (1977), Regular 2-graphs. ''Proceedings of the London Mathematical Society'' (3), vol. 35, pp. 257–274. * {{citation, last1=van Lint, first1=J. H., last2=Seidel, first2=J. J., title=Equilateral point sets in elliptic geometry, series=Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, journal=Indagationes Mathematicae, volume=28, year=1966, pages=335-348 Families of sets Algebraic graph theory Extensions and generalizations of graphs