##
**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 V_{1}, ..., V_{n}; (2) for any r-element subfamily **{**V_{i1},..., V_{ir}**}** form an edge by picking from each V_{ij} exactly one element. An independent transversal is a set of vertices which meets each V_{i} in exactly one point and does not contain any edge. The paper provides estimates for the function f_{r}(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} k^{2} < f_{2}(k) < (1+o(1))k^{2}. For those values of k for which an affine plane of order k+1 exists, it is shown that f_{2}(k) < (k+1)^{2}. Asymptotics for f_{r}(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