## Abstract

Let H be a hypergraph of order n_{H}=|V(H)| and size m_{H}=|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 L_{k} be the class of k-uniform linear hypergraphs. In this paper we study the problem of determining or estimating the best possible constants q_{k} (which depends only on k) such that τ(H)≤q_{k}(n_{H}+m_{H}) for all H∈L_{k}. We establish lower bounds on q_{k} for all k≥2. For all k≥2 and for all 0<a<1, we show that q_{k}≥a(1−a)^{k}∕((1−a)^{k}+aln(e∕a)), where here ln denotes the natural logarithm to the base e.

Original language | English |
---|---|

Pages (from-to) | 12-22 |

Number of pages | 11 |

Journal | Discrete Applied Mathematics |

Volume | 304 |

DOIs | |

Publication status | Published - 15 Dec 2021 |

## Keywords

- Affine plane
- Hypergraph
- Linear hypergraph
- Transversal

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics