2010/07/30 by Borg, Peter
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1007.5426
An r-graph G is a pair (V,E) such that V is a set and E is a family of r-element subsets of V. The independence number α(G) of G is the size of a largest subset I of V such that no member of E is a subset of I. The transversal number τ(G) of G is the size of a smallest subset T of V that intersects each member of E. G is said to be connected if for every distinct v and w in V there exists a path from v to w (that is, a sequence e1, …, ep of members of E such that v ∈ e1, w ∈ ep, and if p ≥ 2, then for each i ∈ \1, …, p-1\, ei intersects ei+1). The degree of a member v of V is the number of members of E that contain v. The maximum of the degrees of the members of V is denoted by Δ(G). We show that for any 1 ≤ k < n, if G = (V,E) is a connected r-graph, |V| = n, and Δ(G) = k, then α(G) ≤ n - \lceil (n-1)/(k(r-1)) \rceil, τ(G) ≥ \lceil (n-1)/(k(r-1)) \rceil, and these bounds are sharp. The two bounds are equivalent.