Abstract
The transversal numberτ(H) of a hypergraphH is the minimum cardinality of a set of vertices that intersects all edges ofH. Fork ≥ 1 definec k =sup τ(H)/(m + n), whereH ranges over allk-uniform hypergraphs withn vertices andm edges. Applying probabilistic arguments we show thatc k = (1 +o(1))log e k/k. This settles a problem of Tuza.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bollobás, B.: Random Graphs, p. 319. New York: Academic Press, 1985
Graham, R.L., Spencer, J.H.: A constructive solution to a tournament problem. Canad. Math. Bull.14, 45–48 (1971)
Lai, Feng-Chu, Chang, Gerard J.: An upper bound for the transversal numbers of 4-uniform hypergraphs. (preprint, 1988)
Tuza, Z.: Covering all cliques of a graph. (preprint, 1986)
Author information
Authors and Affiliations
Additional information
Research supported in part by Allon Fellowship and by a grant from the Bat Sheva de Rothschild Foundation.
Rights and permissions
About this article
Cite this article
Alon, N. Transversal numbers of uniform hypergraphs. Graphs and Combinatorics 6, 1–4 (1990). https://doi.org/10.1007/BF01787474
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01787474