Menu
A linear system is a pair \((P,\mathcal{L})\) where \(\mathcal{L}\) is a finite family of subsets on a finite ground set \(P\) such that any two subsets of \(\mathcal{L}\) share at most one element. Furthermore, if for every two subsets of \(\mathcal{L}\) share exactly one element, the linear system is called intersecting. A linear system \((P,\mathcal{L})\) has rank \(r\) if the maximum size of any element of \(\mathcal{L}\) is \(r\). By \(\gamma(P,\mathcal{L})\) and \(\nu_2(P,\mathcal{L})\) we denote the size of the minimum dominating set and the maximum 2-packing of a linear system \((P,\mathcal{L})\), respectively. It is known that any intersecting linear system \((P,\mathcal{L})\) of rank \(r\) is such that \(\gamma(P,\mathcal{L})\leq r-1\). Li et al. in [S. Li, L. Kang, E. Shan and Y. Dong, The finite projective plane and the 5-Uniform linear intersecting hypergraphs with domination number four, Graphs and 34 Combinatorics (2018) , no.~5, 931–945.] proved that every intersecting linear system of rank 5 satisfying \(\gamma(P,\mathcal{L})=4\) can be constructed from a 4-uniform intersecting linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of the projective plane of order 3 satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=4\), where \(\tau(P^\prime,\mathcal{L}^\prime)\) is the transversal number of \((P^\prime,\mathcal{L}^\prime)\). In this paper, we give an alternative proof of this result given by Li et al., giving a complete characterization of these 4-uniform intersecting linear subsystems. Moreover, we prove a general case, that is, we prove if $q$ is an odd prime power and \((P,\mathcal{L})\) is an intersecting linear system of rank \((q+2)\) satisfying \(\gamma(P,\mathcal{L})=q+1\), then this linear system can be constructed from a spanning \((q+1)\)-uniform intersecting linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of the projective plane of order \(q\) satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=q+1\).
A set system is a pair \((X,\mathcal{F})\) where \(% \mathcal{F}\) is a finite family of subsets on a finite ground set \(X\). A set system can be also thought of as a hypergraph, where the elements of \(X\) and \(\mathcal{F}\) are called vertices and hyperedges, respectively. The set system \((X,\mathcal{F})\) is intersecting if \(E\cap F\neq\emptyset\), for for every pair of distinct subsets \(E,F \in \mathcal{F}\). On the other hand, the set system \((X,\mathcal{F})\) is a linear system if it satisfies \(|E\cap F|\leq 1\), for every pair of distinct subsets \(E,F \in \mathcal{F}\); and it is denoted by \((P,\mathcal{L})\). The elements of \(P\) and \(\mathcal{L}\) are called points and lines respectively. In this paper, we only consider linear systems, and the most of following definitions can be generalized for set systems.
The rank of a linear system \((P,\mathcal{L})\) is the maximum size of a line of \(\mathcal{L}\). An \(r\)-uniform linear system \((P,\mathcal{L})\) is a linear system such that every line contains exactly \(r\) points. Hence, a (simple) graph is a 2-uniform linear system. In this paper we only consider linear systems of rank \(r\geq2\).
Let \((P,\mathcal{L})\) be a linear system and \(p\in P\) be a point. The degree of \(p\) is the number of lines containing \(p\) and it is denoted by \(deg(p)\). The maximum degree overall points of the linear systems is denoted by \(\Delta(P,\mathcal{L})\). A point of degree \(2\) and \(3\) is called double point and triple point, respectively. Two points \(p\) and \(q\) in \((P,\mathcal{L})\) are adjacent if there is a line \(l\in\mathcal{L}\) such that \(p,q\in l\).
A linear subsystem \((P^{\prime },\mathcal{L}^{\prime })\) of a linear system \((P,\mathcal{L})\) satisfies that for any line \(l^\prime\in\mathcal{L}^\prime\) there exists a line \(l\in\mathcal{L}\) such that \(l^\prime=l\cap P^\prime\). The linear subsystem induced by a set of lines \(\mathcal{L}^{\prime}\subseteq \mathcal{L}\) is the linear subsystem \((P^{\prime },\mathcal{L}^{\prime })\) where \(P^{\prime}=\bigcup_{l\in \mathcal{L}^{\prime }} l\). The linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of \((P,\mathcal{L})\) is called spanning linear subsystem if \(P^\prime=P\). Given a linear system \((P,\mathcal{L})\), and a point \(p\in P\), the linear system obtained from \((P,\mathcal{L})\) by deleting the point \(p\) is the linear system \((P^{\prime },\mathcal{L}^{\prime })\) induced by \(\mathcal{L}^{\prime }=\{l\setminus \{p\}: l\in \mathcal{L}\}\). Given a linear system \((P,\mathcal{L})\) and a line \(l\in \mathcal{L}\), the linear system obtained from \((P,\mathcal{L})\) by deleting the line \(l\) is the linear system \((P^{\prime },\mathcal{L}^{\prime })\) induced by \(\mathcal{L}^{\prime }= \mathcal{L}\setminus \{l\}\). Let \((P^{\prime},\mathcal{L}^{\prime })\) and \((P,\mathcal{L})\) be two linear systems. The linear systems \((P^{\prime},\mathcal{L}^{\prime })\) and \((P,\mathcal{L})\) are isomorphic, denoted by \((P^{\prime },\mathcal{L}^{\prime })\simeq(P,\mathcal{L})\), if after deleting points of degree 1 or 0 from both, the systems \((P^{\prime},\mathcal{L}^{\prime })\) and \((P,\mathcal{L})\) are isomorphic as hypergraphs, see [1].
A subset \(D\) of points of a linear system \((P,\mathcal{L})\) is a dominating set of \((P,\mathcal{L})\) if for every \(p\in P\setminus D\) there exists \(q\in D\) such that \(p\) and \(q\) are adjacent. The minimum cardinality of a dominating set of a linear system \((P,\mathcal{L})\) is called domination number, denoted by \(\gamma(P,\mathcal{L})\). Domination in set systems (hypergraphs) was introduced by Acharya [2] and studied further in [3, 4, 5, 6, 7].
A subset \(T\) of points of a linear system \((P,\mathcal{L})\) is a transversal of \((P,\mathcal{L})\) (also called vertex cover or hitting set) if \(T\cap l\neq\emptyset\), for every line \(l\in\mathcal{L}\). The minimum cardinality of a transversal of a linear system \((P,\mathcal{L})\) is called transversal number, denoted by \(\tau(P,\mathcal{L})\). Since any transversal of a linear system \((P,\mathcal{L})\) is a dominating set, then \(\gamma(P,\mathcal{L})\leq\tau(P,\mathcal{L})\).
A subset \(R\) of lines of a linear system \((P,\mathcal{L})\) is a \(2\)-packing of \((P,\mathcal{L})\) if the elements of \(R\) are triplewise disjoint, that is, if any three elements are chosen in \(R\) then they are not incidents in a common point. The 2-packing number of \((P,\mathcal{L})\) is the maximum cardinality of a 2-packing of \((P,\mathcal{L})\), denoted by \(\nu_2(P,\mathcal{L})\). There are some works related on transversal and 2-packing numbers in linear systems, see for example [1, 8, 9, 10, 11].
Kang et al. [12] proved if \((P,\mathcal{L})\) is an intersecting linear system of rank \(r\geq2\), then \(\gamma(P,\mathcal{L})\leq r-1\). Shan et al. [13] gave a characterization of set systems \((X,\mathcal{F})\) holding the equality when \(r=3\). On the other hand, Dong et al. [6] shown all intersecting linear systems \((P,\mathcal{L})\) of rank 4, satisfying \(\gamma(P,\mathcal{L})=3\), can be constructed by the Fano plane. In this paper, we prove that if \((P,\mathcal{L})\) is an intersecting linear system of rank 5 satisfying \(\gamma(P,\mathcal{L})=4\), then this linear system can be constructed from an 4-uniform intersecting linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of the projective plane of order 3 satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=4\), and we give a complete characterization of this 4-uniform intersecting linear subsystems. The result was also obtained by Li et al. [14]. Furthermore, we prove that if \(q\) is an odd prime power and if \((P,\mathcal{L})\) is an intersecting linear system of rank \((q+2)\) satisfying \(\gamma(P,\mathcal{L})=q+1\) then, this linear system can be constructed from a spanning \((q+1)\)-uniform intersecting linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of the projective plane of order \(q\) satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=q+1\).
Let \(\mathcal{I}_r\) be the family of intersecting linear systems \((P,\mathcal{L})\) of rank \(r\) with \(\gamma(P,\mathcal{L})=r-1\). To better understand this paper, we need the following results:
Lemma 1 (Lemma 2.1 in [6]). For every linear system \((P,\mathcal{L})\in\mathcal{I}_r\), there exists a spanning intersecting \(r\)-uniform linear subsystem \((P^*,\mathcal{L}^*)\) of \((P,\mathcal{L})\) such that every line in \(\mathcal{L}^*\) contains one point of degree one.
Let \((P^*,\mathcal{L}^*)\) be the spanning intersecting \(r\)-uniformlinear subsystem obtained from Lemma 1. Furthermore, let \((P^\prime,\mathcal{L}^\prime)\) be the intersecting \((r-1)\)-uniform linear subsystem obtained from \((P^*,\mathcal{L}^*)\) by deleting the point of degree one of each line of \(\mathcal{L}^*\), see [6].
Lemma 2 (Lemma 2.2 in [6]). For every linear system \((P,\mathcal{L})\in\mathcal{I}_r\) it satisfies \[\gamma(P,\mathcal{L})=\gamma(P^*,\mathcal{L}^*)=\tau(P^*,\mathcal{L}^*)=\tau(P^\prime,\mathcal{L}^\prime)=r-1.\]
Lemma 3 (Lemma 2.4 in [6]). Let \((P,\mathcal{L})\in\mathcal{I}_r\) \((r\geq3)\), then every line of \((P^\prime,\mathcal{L}^\prime)\) has at most one point of degree 2 and \(\Delta(P^\prime,\mathcal{L}^\prime)=r-1\).
Lemma 4 (Lemma 2.5 in [6]). Let \((P,\mathcal{L})\in\mathcal{I}_r\) \((r\geq3)\), then
\(3(r-2)\leq|\mathcal{L}^\prime|\leq(r-1)^2-(r-1)+1\) and \(|P^\prime|=(r-1)^2-(r-1)+1\),
and so \(\gamma(P^\prime,\mathcal{L}^\prime)=1\).
Proposition 1 (Proposition 2.1 and Proposition 2.2 in [1]). Let \((P,\mathcal{L})\) be a linear system with \(|\mathcal{L}|>\nu_2(P,\mathcal{L})\). If \(\nu_2(P,\mathcal{L})\in\{2,3\}\), then \(\tau(P,\mathcal{L})\leq\nu_2(P,\mathcal{L})-1\).
Theorem 1 (Theorem 2.1 in [8]). Let \((P,\mathcal{L})\) be a linear system and \(p,q\in P\) be two points such that \(deg(p)=\Delta(P,\mathcal{L})\) and \(deg(q)=\max\{deg(x): x\in P\setminus\{p\}\}\). If \(|\mathcal{L}|\leq deg(p)+deg(q)+\nu_2(P,\mathcal{L})-3\), then \(\tau(P,\mathcal{L})\leq\nu_2(P,\mathcal{L})-1\).
Lemma 5. Let \((P,\mathcal{L})\) be an \(r\)-uniform intersecting linear system with \(r\geq2\) be an even integer. If \(\nu_2(P,\mathcal{L})=r+1\) then \(\tau(P,\mathcal{L})=\frac{r+2}{2}\).
Proof. Let \((P,\mathcal{L})\) be a \(r\)-uniform intersecting linear system with \(\nu_2(P,\mathcal{L})=r+1\), where \(r\geq2\) is an even integer. Let \(R=\{l_1,\ldots,l_{r+1}\}\) be a maximum 2-packing of \((P,\mathcal{L})\). Since \((P,\mathcal{L})\) is an intersecting linear system then \(l_i\cap l_j\neq\emptyset\), for \(1\leq i<j\leq r+1\), hence \(|l_i|=r\), for \(i=1,\ldots,r+1\). Let \(l\in\mathcal{L}\setminus R\). Since \((P,\mathcal{L})\) is an intersecting linear system it satisfies \(l\cap l_i=l\cap l_i\cap l_{j_i}\neq\emptyset\), for \(i=1,\ldots,r+1\) and for some \(j_i\in\{1,\ldots,r+1\}\setminus\{i\}\), however, by the pigeonhole principle there are a line \(l_s\in R\) such that \(l\cap l_s=\emptyset\), since there are an odd number of lines in \(R\) and by linearity of \((P,\mathcal{L})\). Therefore \(|\mathcal{L}|=|R|\) and \(\tau(P,\mathcal{L})=\lceil \nu_{2}/2\rceil=\frac{r+2}{2}\) (see [9]). ◻
In this section, we give a complete characterization of the linear systems \((P^\prime,\mathcal{L}^\prime)\) of \((P,\mathcal{L})\in\mathcal{I}_5\).
Notice that any line \(l\in\mathcal{L}^\prime\) satisfies \(|l|\geq\nu_2(P^\prime,\mathcal{L}^\prime)-1\) (since \((P^\prime,\mathcal{L}^\prime)\) is intersecting), which implies that. \(\nu_2(P^\prime,\mathcal{L}^\prime)\leq r\). It is clear, by Lemma 2 and Proposition 1, for every \((P,\mathcal{L})\in\mathcal{I}_5\) satisfies \(4\leq\nu_2(P^\prime,\mathcal{L}^\prime)\leq5\). In fact, by the following lemma, Lemma 6, it implies that \(\nu_2(P^\prime,\mathcal{L}^\prime)=4\).
Lemma 6. Any \((P,\mathcal{L})\in\mathcal{I}_5\) satisfies \(\nu_2(P^\prime,\mathcal{L}^\prime)=4\).
Proof. Let \((P,\mathcal{L})\in\mathcal{I}_5\) and suppose that \(\nu_2(P,\mathcal{L})=5\). Then, by Lemma 5 it satisfies \(\tau(P^\prime,\mathcal{L}^\prime)=3\), a contradiction since \(\tau(P^\prime,\mathcal{L}^\prime)=4\). Therefore \(\nu_2(P^\prime,\mathcal{L}^\prime)=4\). ◻
Hence, by the following Theorem 2, if \((P,\mathcal{L})\in\mathcal{I}_5\) then \((P^\prime,\mathcal{L}^\prime)\) is a linear subsystem of the projective plane of order 3.
A finite projective plane (or merely projective plane) is an uniform linear system satisfying that any pair of points have a common line, any pair of lines have a common point and there exist four points in general position (there are not three collinear points). It is well known that if \((P,\mathcal{L})\) is a projective plane then there exists a number \(q\in\mathbb{N}\), called order of projective plane, such that every point (line, respectively) of \((P,\mathcal{L})\) is incident to exactly \(q+1\) lines (points, respectively), and \((P,\mathcal{L})\) contains exactly \(q^2+q+1\) points (lines, respectively). In addition to this, it is well known that projective planes of order \(q\), denoted by \(\Pi_q\), exist when \(q\) is a power prime. For more information about the existence and the unicity of projective planes see, for instance, [15, 16].
Theorem 2 (Theorem 2.1 in [1]). Let \((P,\mathcal{L})\) be a linear system with \(|\mathcal{L}|>4\). If \(\nu_2(P,\mathcal{L})=4\), then \(\tau(P,\mathcal{L})\leq4\). Moreover, if \(\tau(P,\mathcal{L})=\nu_2(P,\mathcal{L})=4\), then \((P,\mathcal{L})\) is a linear subsystem of \(\Pi_3\).
Araujo-Pardo et al. [1] proved that the linear system \((P,\mathcal{L})\) with \(|\mathcal{L}|>4\) satisfying \(\tau(P,\mathcal{L})=\nu_2(P,\mathcal{L})=4\) are a special family of linear subsystems of \(\Pi_3\).
Given a linear system \((P,\mathcal{L})\), a triangle \(\mathcal{T}\) of \((P,\mathcal{L})\), is the linear subsystem of \((P,\mathcal{L})\) induced by three points in general position (non collinear) and the three lines induced by them. Consider the projective plane \(\Pi_3\) and a triangle \(\mathcal{T}\) of \(\Pi_3\) (see \((a)\) of Figure 1). Araujo-Pardo et al. [1] defined the intersecting 4-uniform linear system \(\mathcal{\hat{C}}=(P_\mathcal{\hat{C}},\mathcal{L}_\mathcal{\hat{C}})\) induced by \(\mathcal{L}_\mathcal{\hat{C}}=\mathcal{L}\setminus\mathcal{T}\) (see \((b)\) of Figure 1). The linear system \(\mathcal{\hat{C}}\) just defined has thirteen points and ten lines. In the same paper, [1], it was defined \(\mathcal{\hat{C}}_{4,4}\) to be the family of spanning intersecting 4-uniform linear systems \((P,\mathcal{L})\) such that:
Proposition 2 (Proposition 4.1 in [1]). If \((P,\mathcal{L})\in\mathcal{\hat{C}}_{4,4}\) then \(\tau(P,\mathcal{L})=\nu_2(P,\mathcal{L})=4\).
It is easy to check that if \((P,\mathcal{L})\in\mathcal{\hat{C}}_{4,4}\) then any point \(p\) of degree 4 of \((P,\mathcal{L})\) is a minimum dominating set, which implies \(\gamma(P,\mathcal{L})=1\). Therefore
Corollary 1. If \((P,\mathcal{L})\in\mathcal{I}_5\) then \((P^\prime,\mathcal{L}^\prime)\in\mathcal{\hat{C}}_{4,4}\).
In this section, we prove if \(q\) is an odd prime power and \((P,\mathcal{L})\) is an intersecting linear system of rank \((q+2)\) satisfying \(\gamma(P,\mathcal{L})=q+1\), then this linear system can be constructed from a spanning \((q+1)\)-uniform intersecting linear subsystem \((P^\prime,\mathcal{L}^\prime)\) of the projective plane of order \(q\), \(\Pi_q\), satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=q+1\).
Araujo-Pardo et al. [1] proved if \(q\) is an even prime power then \(\tau(\Pi_q)\leq\nu_2(\Pi_q)-1=q+1\), however, if \(q\) is an odd prime power then \(\tau(\Pi_q)=\nu_2(\Pi_q)=q+1\).
Lemma 7. Let \(q\) be an odd integer. For every \((P,\mathcal{L})\in\mathcal{I}_{q+2}\) it satisfies \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)= q+1\).
Proof. Since \((P^\prime,\mathcal{L}^\prime)\) is an intersecting \((q+1)\)-uniform linear system then \(|l^\prime|\geq\nu_2(P^\prime,\mathcal{L}^\prime)-1\), for any line \(l^\prime\in\mathcal{L}^\prime\). Hence \(\nu_2(P^\prime,\mathcal{L}^\prime)\leq q+2\). On the other hand, if \(\nu_2(P^\prime,\mathcal{L}^\prime)=q+2\) then by Lemma 5 it follows that \(\tau(P^\prime,\mathcal{L}^\prime)=\frac{q+3}{2}\), which is a contradiction, since \(\tau(P^\prime,\mathcal{L}^\prime)=q+1\). Therefore \(\nu_2(P^\prime,\mathcal{L}^\prime)\leq q+1\). On the other hand, let \(p\in P^\prime\) be a point such that \(deg(p)=\Delta(P^\prime,\mathcal{L}^\prime)\) and \(\Delta^\prime(P^\prime,\mathcal{L}^\prime)=\max\{deg(x): x\in P^\prime\setminus\{p\}\}\). By Theorem 1 if \(|\mathcal{L}^\prime|\leq\Delta(P^\prime,\mathcal{L}^\prime)+\Delta^\prime(P^\prime,\mathcal{L}^\prime)+\nu_2(P,\mathcal{L})-3\leq3q\) then \(\tau(P^\prime,\mathcal{L}^\prime)\leq\nu_2(P^\prime,\mathcal{L}^\prime)-1\), which implies \(q+2\leq\nu_2(P^\prime,\mathcal{L}^\prime)\), a contradiction, since \(\nu_2(P^\prime,\mathcal{L}^\prime)\leq q+1\). Hence, if \(\tau(P^\prime,\mathcal{L}^\prime)\geq\nu_2(P^\prime,\mathcal{L}^\prime)\) then \(|\mathcal{L}^\prime|\geq\Delta(P^\prime,\mathcal{L}^\prime)+\Delta^\prime(P^\prime,\mathcal{L}^\prime)+\nu_2(P,\mathcal{L})-2\geq3q+1\), which implies \(\nu_2(P^\prime,\mathcal{L}^\prime)\geq q+1\). Hence \(\nu_2(P^\prime,\mathcal{L}^\prime)=q+1\). ◻
Theorem 3. Let \(q\) be an odd prime power. For every \((P,\mathcal{L})\in\mathcal{I}_{q+2}\), the linear system \((P^\prime,\mathcal{L}^\prime)\) is a spanning \((q+1)\)-uniform linear subsystem of \(\Pi_q\) such that \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=q+1\) with \(|\mathcal{L}^\prime|\geq3q+1\).
Proof. Let \((P,\mathcal{L})\in\mathcal{I}_{q+2}\). Then \((P^\prime,\mathcal{L}^\prime)\) is an \((q+1)\)-uniform intersecting linear system with \(|P^\prime|=q^2+q+1\) (by Lemma 4 ). Furthermore, If \(|\mathcal{L}^\prime|=q^2+q+1\) then all points of \((P^\prime,\mathcal{L}^\prime)\) have degree \(q+1\) (it is a consequence of Lemma 4, see [6]). Since projective planes are dual systems, the 2-packing number coincides with the cardinality of an oval, which is the maximum number of points in general position (no three of them collinear), and it is equal to \(q+1=\nu_2(P^\prime,\mathcal{L}^\prime)\) (Lemma 7), when q is odd, see for example [16]. Hence, the linear system \((P^\prime,\mathcal{L}^\prime)\) is a projective plane of order \(q\), \(\Pi_q\). Therefore, if \((P,\mathcal{L})\in\mathcal{I}_{q+2}\) then \((P^\prime,\mathcal{L}^\prime)\) is a spanning linear subsystem of \(\Pi_q\) satisfying \(\tau(P^\prime,\mathcal{L}^\prime)=\nu_2(P^\prime,\mathcal{L}^\prime)=q+1\) with \(|\mathcal{L}^\prime|\geq3q+1\) (see proof of Lemma 7). ◻
Research was partially supported by SNI and CONACyT.
The author declares no conflict of interests.