TRANSVERSAL NUMBERS OF UNIFORM HYPERGRAPHS

被引：103

作者：

ALON, N

机构：

[1] TEL AVIV UNIV,SACKLER FAC EXACT SCI,DEPT MATH,IL-69978 TEL AVIV,ISRAEL

[2] BELL COMMUN RES INC,MORRISTOWN,NJ 07960

来源：

GRAPHS AND COMBINATORICS | 1990年 / 6卷 / 01期

关键词：

D O I：

10.1007/BF01787474

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The transversal number τ(H) of a hypergraph H is the minimum cardinality of a set of vertices that intersects all edges of H. For k ≥ 1 define ck =sup τ(H)/(m + n), where H ranges over all k-uniform hypergraphs with n vertices and m edges. Applying probabilistic arguments we show that ck = (1 +o(1))logek/k. This settles a problem of Tuza. © 1990 Springer-Verlag.

引用

页码：1 / 4

页数：4