On transversal and $2$-packing numbers in straight line systems on ${\mathbb{R}}^2$

Abstract

A linear system is a pair $(X,\mathcal{F})$ where $\mathcal{F}$ is a finite family of subsets on a ground set $X$, and it satisfies that $|A\cap B|\le 1$ for every pair of distinct subsets $A,B\in \mathcal{F}$. As an example of a linear system are the straight line systems, which family of subsets are straight line segments on ${\mathbb{R}}^2$. By $\tau$ and ${\nu }_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 $\tau \le f({\nu }_2)$. However, for straight line system we believe that $\tau \le {\nu }_2-1$. In this paper we prove that for any linear system with $2$-packing numbers ${\nu }_2$ equal to $2,3$ and $4$, we have that $\tau \le {\nu }_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 ${\nu }_2\in \{2,3,4\}$ satisfies $\tau \le {\nu }_2-1$.

22 pages, 7 figures