Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 811.05068
Autor: Erdös, Paul; Gyárfás, András; Luczak, Tomasz
Title: Independent transversals in sparse partite hypergraphs. (In English)
Source: Comb. Probab. Comput. 3, No.3, 293-296 (1994).
Review: An [n, k, r]-hypergraph is any hypergraph with a kn-element set of vertices and whose edges can be obtained in the following manner: (1) partition the set of vertices into n k-element sets V1, ..., Vn; (2) for any r-element subfamily {Vi1,..., Vir} form an edge by picking from each Vij exactly one element. An independent transversal is a set of vertices which meets each Vi in exactly one point and does not contain any edge. The paper provides estimates for the function fr(k)–the largest n for which any [n,k,r]-hypergraph has an independent transversal. In particular, in the case when r = 2, it is proved that (1+o(1))(2e)-1 k2 < f2(k) < (1+o(1))k2. For those values of k for which an affine plane of order k+1 exists, it is shown that f2(k) < (k+1)2. Asymptotics for fr(k), in several cases when k is small compared to r, are also given.
Reviewer: M.Truszczynski (Lexington)
Classif.: * 05D15 Transversal (matching) theory
05C65 Hypergraphs
Keywords: sparse partite hypergraphs; hypergraphics; probabilistic method; independent transversal; affine plane
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag