2015/09/12 by Araujo-Pardo, Gabriela, Montejano, Amanda, Montejano, Luis +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1509.03696
A linear system is a pair (X,F) where F is a finite family of subsets on a ground set X, and it satisfies that |A∩ B|≤ 1 for every pair of distinct subsets A,B ∈ F. As an example of a linear system are the straight line systems, which family of subsets are straight line segments on ℝ2. By τ and ν2 we denote the size of the minimal transversal and the 2--packing numbers of a linear system respectively. A natural problem is asking about the relationship of these two parameters; it is not difficult to prove that there exists a quadratic function f holding τ≤ f(ν2). However, for straight line system we believe that τ≤ν2-1. In this paper we prove that for any linear system with 2-packing numbers ν2 equal to 2, 3 and 4, we have that τ≤ν2. Furthermore, we prove that the linear systems that attains the equality have transversal and 2-packing numbers equal to 4, and they are a special family of linear subsystems of the projective plane of order 3. Using this result we confirm that all straight line systems with ν2∈\2,3,4\ satisfies τ≤ν2-1.