TY - JOUR

T1 - Bounds on upper transversals in hypergraphs

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2020

Y1 - 2020

N2 - A set S of vertices in a hypergraph H is a transversal if it has a nonempty intersection with every edge of H. For k≥ 1 , if H is a hypergraph with every edge of size at least k, then a k-transversal in H is a transversal that intersects every edge of H in at least k vertices. In particular, a 1-transversal is a transversal. The upper k-transversal number Υ k(H) of H is the maximum cardinality of a minimal k-transversal in H. Let H be a hypergraph with nH vertices and mH edges. We show that for r≥ 2 and for every integer k∈ [r] , if H is r-uniform with maximum degree Δ , then Υk(H)≤(k·Δk(Δ-1)+r)nH and Υk(H)≤(k·ΔΔ(k+1)+r-k)(nH+mH), and both bounds are tight. As a special case of this result, if H is a 3-regular, 3-uniform hypergraph, then Υ2(H)≤67nH, and equality in this bound is achieved by the Fano plane. We also discuss a relation between upper transversals in 3-uniform hypergraphs and the famous cap set problem, and show that for every given ϵ> 0 , there exists a 3-uniform, connected, linear hypergraphs of sufficiently large order such that Υ1(H)<ϵ·nH.

AB - A set S of vertices in a hypergraph H is a transversal if it has a nonempty intersection with every edge of H. For k≥ 1 , if H is a hypergraph with every edge of size at least k, then a k-transversal in H is a transversal that intersects every edge of H in at least k vertices. In particular, a 1-transversal is a transversal. The upper k-transversal number Υ k(H) of H is the maximum cardinality of a minimal k-transversal in H. Let H be a hypergraph with nH vertices and mH edges. We show that for r≥ 2 and for every integer k∈ [r] , if H is r-uniform with maximum degree Δ , then Υk(H)≤(k·Δk(Δ-1)+r)nH and Υk(H)≤(k·ΔΔ(k+1)+r-k)(nH+mH), and both bounds are tight. As a special case of this result, if H is a 3-regular, 3-uniform hypergraph, then Υ2(H)≤67nH, and equality in this bound is achieved by the Fano plane. We also discuss a relation between upper transversals in 3-uniform hypergraphs and the famous cap set problem, and show that for every given ϵ> 0 , there exists a 3-uniform, connected, linear hypergraphs of sufficiently large order such that Υ1(H)<ϵ·nH.

KW - k-transversal number

KW - Transversal

KW - Upper transversal

U2 - 10.1007/s10878-019-00456-4

DO - 10.1007/s10878-019-00456-4

M3 - Journal article

AN - SCOPUS:85075809045

VL - 39

SP - 77

EP - 89

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

ER -