首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 7 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 Cd to each vertex such that two vertices are adjacent precisely when assigned nonorthogonal vectors. We show that d=10 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 10 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号