2018/02/06 by Michael A. Henning, Henning, Michael A., Anders Yeo +1
Computer Science · Engineering · Mathematics · #05C65 #51E15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1802.01825
openalex publication_date 2018/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. It is known that τ(H) ≤ (n + m)/(k+1) holds for all k-uniform, linear hypergraphs H when k ∈ \2,3\ or when k ≥ 4 and the maximum degree of H is at most two. It has been conjectured that τ(H) ≤ (n+m)/(k+1) holds for all k-uniform, linear hypergraphs H. We disprove the conjecture for large k, and show that the best possible constant ck in the bound τ(H) ≤ ck (n+m) has order ln(k)/k for both linear (which we show in this paper) and non-linear hypergraphs. We show that for those k where the conjecture holds, it is tight for a large number of densities if there exists an affine plane AG(2,k) of order k ≥ 2. We raise the problem to find the smallest value, kmin, of k for which the conjecture fails. We prove a general result, which when applied to a projective plane of order 331 shows that kmin ≤ 166. Even though the conjecture fails for large k, our main result is that it still holds for k=4, implying that kmin ≥ 5. The case k=4 is much more difficult than the cases k ∈ \2,3\, as the conjecture does not hold for general (non-linear) hypergraphs when k=4. Key to our proof is the completely new technique of the deficiency of a hypergraph introduced in this paper.