Transversal numbers of uniform hypergraphs

Noga Alon

doi:10.1007/BF01787474

Transversal numbers of uniform hypergraphs

Noga Alon

Research output: Contribution to journal › Article › peer-review

118 Scopus citations

Abstract

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 c_k =sup τ(H)/(m + n), where H ranges over all k-uniform hypergraphs with n vertices and m edges. Applying probabilistic arguments we show that c_k = (1 +o(1))log_ek/k. This settles a problem of Tuza.

Original language	English (US)
Pages (from-to)	1-4
Number of pages	4
Journal	Graphs and Combinatorics
Volume	6
Issue number	1
DOIs	https://doi.org/10.1007/BF01787474
State	Published - Mar 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF01787474

Cite this

@article{6ca33369f0bb4171931bca875f8d2d27,

title = "Transversal numbers of uniform hypergraphs",

abstract = "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.",

author = "Noga Alon",

year = "1990",

month = mar,

doi = "10.1007/BF01787474",

language = "English (US)",

volume = "6",

pages = "1--4",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Transversal numbers of uniform hypergraphs

AU - Alon, Noga

PY - 1990/3

Y1 - 1990/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0003106496&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0003106496&partnerID=8YFLogxK

U2 - 10.1007/BF01787474

DO - 10.1007/BF01787474

M3 - Article

AN - SCOPUS:0003106496

SN - 0911-0119

VL - 6

SP - 1

EP - 4

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Transversal numbers of uniform hypergraphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this