Transversals in 4-uniform linear hypergraphs

Abstract: The transversal number

a u (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

a u (H) l e (n + m) / (k + 1)

holds for all

k

-uniform, linear hypergraphs

H

when

k i n 2, 3

or when

k g e 4

and the maximum degree of

H

is at most two. It has been conjectured that

a u (H) l e (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

c_{k}

in the bound

a u (H) l e c_{k} (n + m)

has order

l n (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

A G (2, k)

of order

k g e 2

. We raise the problem to find the smallest value,

k_{m i n}

, of

k

for which the conjecture fails. We prove a general result, which when applied to a projective plane of order

331

shows that

k_{m i n} l e 166

. Even though the conjecture fails for large

k

, our main result is that it still holds for

k = 4

, implying that

k_{m i n} g e 5

. The case

k = 4

is much more difficult than the cases

k i n 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.

Recommendations

Cited in

(5)

This page was built for publication: Transversals in 4-uniform linear hypergraphs