Bounding the number of hyperedges in friendship r-hypergraphs

DOI10.1016/J.EJC.2015.05.002MaRDI QIDQ499453zbMATH OpenOpenAlexFDO

Authors Karen Gunderson, Natasha Morrison, Jason Semeraro

Publication date 30 September 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1412.5822

zbMATH Keywords

enumerationboundsfriendship graphcomputer algorithmfriendship 3-hypergraphsgeometric friendship designs

Mathematics Subject Classification ID

Hypergraphs (05C65)

Abstract: For $rge2$, 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 $xotinR$ with the property that for each subset $AsubseteqR$ of size $r-1$, the set $Acupx$ is a hyperedge. We show that for $rgeq3$, the number of hyperedges in a friendship $r$-hypergraph is at least $$, 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$.

Recommendations

• A sharp lower bound on the number of hyperedges in a friendship 3-hypergraph
• On the existence of friendship hypergraphs
• On a question of Sós about 3-uniform friendship hypergraphs
• Friendship 3-hypergraphs
• The maximum size of hypergraphs without generalized 4-cycles

Cites work

• scientific article; zbMATH DE number 3561362 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3358480 (Why is no real title available?)
• scientific article; zbMATH DE number 3384021 (Why is no real title available?)
• A sharp lower bound on the number of hyperedges in a friendship 3-hypergraph
• Friendship 3-hypergraphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On a question of Sós about 3-uniform friendship hypergraphs
• On generalized graphs
• On the existence of friendship hypergraphs
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Regularity Lemma for k-uniform hypergraphs
• The Friendship Theorem
• The counting lemma for regular k‐uniform hypergraphs

Cited in

(7)

• On the existence of friendship hypergraphs
• Symmetry in domination for hypergraphs with choice
• Friendship 3-hypergraphs
• A sharp lower bound on the number of hyperedges in a friendship 3-hypergraph
• A doubling construction for 3-uniform friendship hypergraphs with the universal pairs property
• A note on the pancyclism of block intersection graphs for universal friendship hypergraphs
• On a question of Sós about 3-uniform friendship hypergraphs

This page was built for publication: Bounding the number of hyperedges in friendship \(r\)-hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499453)