Let H be a hypergraph of order nH=|V(H)| and size mH=|E(H)|. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge of H. A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A k-uniform hypergraph has all edges of size k. Let Lk be the class of k-uniform linear hypergraphs. In this paper we study the problem of determining or estimating the best possible constants qk (which depends only on k) such that τ(H)≤qk(nH+mH) for all H∈Lk. We establish lower bounds on qk for all k≥2. For all k≥2 and for all 0<a<1, we show that qk≥a(1−a)k∕((1−a)k+aln(e∕a)), where here ln denotes the natural logarithm to the base e.
Bibliographical notePublisher Copyright:
© 2021 Elsevier B.V.
- Affine plane
- Linear hypergraph