On regular hypergraphs of high girth

MaRDI QIDQ405152zbMATH OpenFDO

Authors David Ellis, Nathan Linial

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.5090, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p54

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

girthhypergraph theory

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Hypergraphs (05C65)

Abstract: We give lower bounds on the maximum possible girth of an $r$-uniform, $d$-regular hypergraph with at most $n$ vertices, using the definition of a hypergraph cycle due to Berge. These differ from the trivial upper bound by an absolute constant factor (viz., by a factor of between $3/2+o(1)$ and $2+o(1)$). We also define a random $r$-uniform `Cayley' hypergraph on $S_n$ which has girth $Omega(n^{1/3})$ with high probability, in contrast to random regular $r$-uniform hypergraphs, which have constant girth with positive probability.

Recommendations

• On the girth of random Cayley graphs
• Counting hypergraphs with large girth
• Hypercycles in a random hypergraph
• On hypergraphs of girth five
• A randomized construction of high girth regular graphs

Cites work

• scientific article; zbMATH DE number 3929049 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 1750094 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• A Moore bound for simplicial complexes
• A new series of dense graphs of high girth
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Graphs with even girth and small excess
• Higher dimensional Moore bounds
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Lifts, discrepancy and nearly optimal spectral gap
• New upper bounds on the order of cages
• On hypergraphs of girth five
• On the girth of random Cayley graphs
• Pentagons vs. triangles
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Ramanujan graphs
• Regular graphs with excess one
• The non-existence of certain regular graphs of girth 5
• The size of bipartite graphs with a given girth

Cited in

(16)

• On the girth of random Cayley graphs
• Counting hypergraphs with large girth
• Small cores in 3-uniform hypergraphs
• scientific article; zbMATH DE number 2188339 (Why is no real title available?)
• Smart elements in combinatorial group testing problems with more defectives
• Hypercycles in a random hypergraph
• scientific article; zbMATH DE number 7720720 (Why is no real title available?)
• scientific article; zbMATH DE number 1500656 (Why is no real title available?)
• Generalized Turán problems for even cycles
• On a conjecture of Erdős on locally sparse Steiner triple systems
• A randomized construction of high girth regular graphs
• Small graphs and hypergraphs of given degree and girth
• Extremal regular graphs and hypergraphs related to fractional repetition codes
• Regular graphs of large girth and arbitrary degree
• Large girth approximate Steiner triple systems
• Identifying defective sets using queries of small size

This page was built for publication: On regular hypergraphs of high girth

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