On the Existence of Friendship Hypergraphs

• Published in: Journal of combinatorial designs 2015-05, Vol.23 (5), p.183-194
• Main Authors: Jørgensen, Leif Kjær, Sillasen, Anita Abildgaard
• Format: Article
• Language: English
• Subjects: 3-uniform friendship hypergraph; friendship graph; r-uniform friendship hypergraph
• ISSN: 1063-8539; 1520-6610
• DOI: 10.1002/jcd.21388

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 xyw, xzw, and yzw 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 2k vertices and 2k−1(3k−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.