Bounding the number of hyperedges in friendship r-hypergraphs

DOI10.1016/J.EJC.2015.05.002zbMATH Open1321.05172arXiv1412.5822OpenAlexW1606891175MaRDI QIDQ499453FDOQ499453

Authors: Karen Gunderson, Natasha Morrison, Jason Semeraro 

Publication date: 30 September 2015

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

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$.

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

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

zbMATH Keywords

enumerationboundsfriendship graphcomputer algorithmfriendship 3-hypergraphsgeometric friendship designs

Mathematics Subject Classification ID

Hypergraphs (05C65)

Cites Work

• Hypergraph regularity and the multidimensional Szemerédi theorem
• Regularity Lemma for k-uniform hypergraphs
• The counting lemma for regular k‐uniform hypergraphs
• Title not available (Why is that?)
• On generalized graphs
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• On a question of Sós about 3-uniform friendship hypergraphs
• Title not available (Why is that?)
• Friendship 3-hypergraphs
• A sharp lower bound on the number of hyperedges in a friendship 3-hypergraph
• The Friendship Theorem
• On the existence of friendship hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)