Irreducible hypergraphs for Hall-type conditions, and arc-minimal digraph expanders

DOI10.1016/J.EJC.2004.04.014MaRDI QIDQ2567286zbMATH OpenOpenAlexFDO

Authors Douglas R. Woodall, Alexandr Kostochka

Publication date 29 September 2005

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

Full work available at URL https://doi.org/10.1016/j.ejc.2004.04.014

zbMATH Keywords

arc-minimal expanderbipartite expander

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Hypergraphs (05C65)

Review text

Suppose that hypergraph \(H\) point-critically satisfies a Hall-type condition of the form \(| \bigcup {\mathcal F}|\geq r| {\mathcal F}|+ \delta.\) If \(\delta\) is rational than the edge size in \(H\) is bounded from above. If, however, \(\delta\) is irrational then there is no upper bound for it. The paper gives full analysis of the results. Generalizations for expander theory are obtained.

Recommendations

• A condition for matchability in hypergraphs
• A generalization of Hall's theorem for \(k\)-uniform \(k\)-partite hypergraphs
• Hall's and Kőnig's theorem in graphs and hypergraphs
• Hypergraph expanders of all uniformities from Cayley graphs
• On a possible extension of Hall's theorem to bipartite hypergraphs

Cites work

• Density conditions for panchromatic colourings of hypergraphs
• Distinct representatives of subsets
• On Representatives of Subsets

This page was built for publication: Irreducible hypergraphs for Hall-type conditions, and arc-minimal digraph expanders

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