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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page