Bounding the number of hyperedges in friendship r-hypergraphs. (January 2016)

• Record Type: Journal Article
• Authors: Gunderson, Karen; Morrison, Natasha; Semeraro, Jason
• Is Part Of: European journal of combinatorics. Volume 51(2016:Jan.)
• Page Start: 125
• Page End: 134
• Publication Date: 2016-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.05.002
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: For r ≥ 2, an r -uniform hypergraph is called a friendship r -hypergraph if every set R of r vertices has a unique 'friend' — that is, there exists a unique vertex x ∉ R with the property that for each subset A ⊆ R of size r − 1, the set A ∪ { x } is a hyperedge. We show that for r ≥ 3, the number of hyperedges in a friendship r -hypergraph is at least r + 1 r ( n − 1 r − 1 ), and we characterise those hypergraphs which achieve this bound. This generalises a result given by Li and van Rees in the case when r = 3 . We also obtain a new upper bound on the number of hyperedges in a friendship r -hypergraph, which improves on a known bound given by Li, van Rees, Seo and Singhi when r = 3 .