Bounding the number of hyperedges in friendship r-hypergraphs. (January 2016) - Gunderson, Karen; Morrison, Natasha; Semeraro, Jason
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 .