## Abstract

Let H be a hypergraph of order n_{H}= |V(/H)| and size m_{H}= |E(H)|. The transversal number τ (H) of a hypergraph 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. For k ≥ 2, let L_{k}denote the class of k-uniform linear hypergraphs. We consider the problem of determining 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}. It is known that q_{2}= 1/3 and q_{3}= 1/4. In this paper we show that q_{4}= 1/5, which is better than for non-linear hypergraphs. Using the affine plane AG(2,4) of order 4, we show there are a large number of densities of hypergraphs H ∈ L_{4}such that τ(H) ≈ 1/5{n_{H}+ m_{H}).

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

Journal | Journal of Combinatorial Mathematics and Combinatorial Computing |

Volume | CXVI |

Pages (from-to) | 111-142 |

ISSN | 0835-3026 |

Publication status | Published - Feb 2021 |

### Bibliographical note

Publisher Copyright:© 2021 Charles Babbage Research Centre. All rights reserved.

## Keywords

- Affine plane
- Hypergraph
- Linear hypergraph
- Transversal