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

Suppose that a hypergraph H = ( V , E ) satisfies a Hall-type condition of the form | ⋃ F | ⩾ r | F | + δ whenever 0̸ ≠ 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 0̸ ≠ 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.