Premium
On the Existence of Friendship Hypergraphs
Author(s) -
Jørgensen Leif Kjær,
Sillasen Anita Abildgaard
Publication year - 2015
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21388
Subject(s) - hypergraph , friendship , mathematics , combinatorics , vertex (graph theory) , construct (python library) , integer (computer science) , discrete mathematics , graph , computer science , psychology , social psychology , programming language
A 3‐uniform friendship hypergraph is a 3‐uniform hypergraph in which, for all triples of vertices x , y , z there exists a unique vertex w , such that x y w , x z w , and y z w are edges in the hypergraph. Sós showed that such 3‐uniform friendship hypergraphs on n vertices exist with a so‐called universal friend if and only if a Steiner triple system, S ( 2 , 3 , n − 1 ) exists. Hartke and Vandenbussche used integer programming to search for 3‐uniform friendship hypergraphs without a universal friend and found one on 8, three nonisomorphic on 16 and one on 32 vertices. So far, these five hypergraphs are the only known 3‐uniform friendship hypergraphs. In this paper we construct an infinite family of 3‐uniform friendship hypergraphs on 2 k vertices and2 k − 1( 3 k − 1 − 1 )edges. We also construct 3‐uniform friendship hypergraphs on 20 and 28 vertices using a computer. Furthermore, we define r ‐uniform friendship hypergraphs and state that the existence of those with a universal friend is dependent on the existence of a Steiner system, S ( r − 1 , r , n − 1 ) . As a result hereof, we know infinitely many 4‐uniform friendship hypergraphs with a universal friend. Finally we show how to construct a 4‐uniform friendship hypergraph on 9 vertices and with no universal friend.