Orthogonal representations of Steiner triple system incidence graphs |
| |
Authors: | Louis Deaett H Tracy Hall |
| |
Institution: | 1. Department of Mathematics, Quinnipiac University, Hamden, CT 06518, USA;2. Department of Mathematics, Brigham Young University, Provo, UT 84602, USA |
| |
Abstract: | The unique Steiner triple system of order has a point-block incidence graph known as the Heawood graph. Motivated by questions in combinatorial matrix theory, we consider the problem of constructing a faithful orthogonal representation of this graph, i.e., an assignment of a vector in to each vertex such that two vertices are adjacent precisely when assigned nonorthogonal vectors. We show that is the smallest number of dimensions in which such a representation exists, a value known as the minimum semidefinite rank of the graph, and give such a representation in real dimensions. We then show how the same approach gives a lower bound on this parameter for the incidence graph of any Steiner triple system, and highlight some questions concerning the general upper bound. |
| |
Keywords: | Faithful orthogonal representation Heawood graph Steiner triple system Minimum rank problem Minimum semidefinite rank |
本文献已被 ScienceDirect 等数据库收录! |
|