Article ID Journal Published Year Pages File Type
6424040 European Journal of Combinatorics 2016 10 Pages PDF
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+1r(n−1r−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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,