Open AccessTransversal numbers of uniform hypergraphs
Author(s) -
Noga Alon
Publication year - 1990
Publication title -
graphs and combinatorics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.59
H-Index - 40
eISSN - 1435-5914
pISSN - 0911-0119
DOI - 10.1007/bf01787474
Subject(s) - transversal (combinatorics) , cardinality (data modeling) , mathematics , combinatorics , hypergraph , set (abstract data type) , fork (system call) , discrete mathematics , mathematical analysis , computer science , data mining , programming language , operating system
The transversal numbert(H) of a hypergraphH is the minimum cardinality of a set of vertices that intersects all edges ofH. Fork = 1 defineck =sup t(H)/(m + n), whereH ranges over allk-uniform hypergraphs withn vertices andm edges. Applying probabilistic arguments we show thatck = (1 +o(1))logek/k. This settles a problem of Tuza.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom