TY - JOUR

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

AU - Kostochka, Alexandr V.

AU - Woodall, Douglas R.

N1 - Funding Information:
Part of this work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by NSF grant DMS-0099608.

PY - 2005/10

Y1 - 2005/10

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

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

KW - Arc-minimal digraph

KW - Arc-minimal expander

KW - Bipartite expander

KW - Digraph expander

KW - Hall-type condition

KW - Irreducible hypergraph

UR - http://www.scopus.com/inward/record.url?scp=22644437403&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=22644437403&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2004.04.014

DO - 10.1016/j.ejc.2004.04.014

M3 - Article

AN - SCOPUS:22644437403

SN - 0195-6698

VL - 26

SP - 1119

EP - 1138

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 7

ER -