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

Alexandr V. Kostochka, Douglas R. Woodall

Research output: Contribution to journalArticlepeer-review

## Abstract

Suppose that a hypergraph H = (V, E) satisfies a Hall-type condition of the form ∪ F ≥ r F + δ whenever ∅ ≠ F ⊆ E, but that this condition fails if any vertex (element) is removed from any edge (set) in E. How large an edge can H contain? It is proved here that there is no upper bound to the size of an edge if r is irrational, but that if r = p/q as a rational in its lowest terms then H can have no edge with more than max {p, p + ⌈δ⌉} vertices (and if δ < 0 then H must have an edge with at most ⌈(p - 1)/q⌉ vertices). If δ > 0 then the upper bound p is sharp, but if δ > 0 then the bound p + ⌈δ⌉ can be improved in some cases (we conjecture, in most cases). As a generalization of this problem, suppose that a digraph D = (V, A) satisfies an expansion condition of the form N+ (X) \ X ≥ r X + δ whenever ∅ ≠ X ⊆ S, where S is a fixed subset of V, but that this condition fails if any arc is removed from D. It is proved that if r = p/q as a rational in its lowest terms, then every vertex of S has outdegree at most max {p + q, p + q + ⌈δ⌉ - 1}, and at most max {p, p + ⌈δ⌉} if S is independent, but that if r is irrational then the vertices of S can have arbitrarily large outdegree.

Original language English (US) 1119-1138 20 European Journal of Combinatorics 26 7 https://doi.org/10.1016/j.ejc.2004.04.014 Published - Oct 2005

## Keywords

• Arc-minimal digraph
• Arc-minimal expander
• Bipartite expander
• Digraph expander
• Hall-type condition
• Irreducible hypergraph

## ASJC Scopus subject areas

• Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'Irreducible hypergraphs for Hall-type conditions, and arc-minimal digraph expanders'. Together they form a unique fingerprint.