Independent Transversals in Sparse Partite Hypergraphs

Authors:

• Paul Erdős,
• András Gyárfás,
• Tomasz Łuczak

Abstract

An [n, k, r]-hypergraph is a hypergraph [formula omitted] = (V, E) whose vertex set V is partitioned into n k-element sets V₁, V₂,…, V_n and for which, for each choice of r indices, 1 ≤ i₁ < i₂ < … < i_r ≤ n, there is exactly one edge e [formula omitted] E such that |e[formula omitted]V_i| = 1 if i [formula omitted] {i₁, i₂.…, i_r} and otherwise |e [formula omitted] V_i| = 0. An independent transversal of an [n, k, r]-hypergraph is a set T = {a₁, a₂,…, a_n} [formula omitted] V such that a_i[formula omitted] V_i for i = 1, 2, …, n and e [formula omitted] T for all e [formula omitted] E. The purpose of this note is to estimate f_r(k), defined as the largest n for which any [n, k, r]-hypergraph has an independent transversal. The sharpest results are for r = 2 and for the case when k is small compared to r. © 1994, Cambridge University Press. All rights reserved.