A note on extremal intersecting linear Ryser systems

1. Introduction

A set system is a pair \((X,\mathcal{F})\) where \(% \mathcal{F}\) is a finite family of subsets on a 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 called \(r\)-uniform, when all subsets of \(\mathcal{F}\) are of size \(r\). The set system \((X,\mathcal{F})\) is \(r\)-partite if the elements of \(X\) can be partitioned into \(r\) sets \(X_1,\ldots,X_r\), called the sides, such that each element of \(\mathcal{F}\) contains exactly one element of \(X_i\), for every \(i=1,\ldots,r\). Thus, an \(r\)-partite set system is an \(r\)-uniform set system.

Let \((X,\mathcal{F})\) be a set system. A subset \(T\subseteq X\) is a transversal of \((X,\mathcal{F})\) if \(T\cap F\neq\emptyset\), for every \(F\in\mathcal{F}\). The transversal number of \((X,\mathcal{F})\), \(\tau=\tau(X,\mathcal{F})\), is the smallest possible cardinality of a transversal of \((X,\mathcal{F})\). The transversal number has been studied in the literature in many different contexts and names. For example, with the name of piercing number and co-vering number, see for instance [1,2,3,4,5,6,7,8,9].

Let \((X,\mathcal{F})\) be a set system. A subset \(\mathcal{E}\subseteq\mathcal{F}\) is called a matching if \(F\cap\hat{F}=\emptyset\), for every \(F,\hat{F}\in\mathcal{E}\). The matching number of \((X,\mathcal{F})\), \(\nu=\nu(X,\mathcal{F})\), is the cardinality of the largest matching of \((X,\mathcal{F})\). A set system is called intersecting if \(\nu=1\); that is, \(F\cap\hat{F}\neq\emptyset\), for every \(F,\hat{F}\in\mathcal{F}\).

It is not hard to see that any \(r\)-uniform set system \((X,\mathcal{F})\) satisfies the inequality \(\tau\leq r\nu\). It is well-known that this bound is sharp, as shown by the family of all subsets of size \(r\) in a ground set of size \(kr-1\), which has \(\nu=k-1\) and \(\tau=(k-1)r\). On the other hand, if \(\nu=1\), any projective plane of order \(r-1\), \(\Pi_{r-1}\), where \(r-1\) is a prime power, satisfies \(\tau=r\). However, for \(r\)-partite set systems, Ryser conjectured in the 1960’s that the upper bound could be improved.

Ryser’s Conjecture:

Any \(r\)-partite set system satisfies \(\tau\leq(r-1)\nu\), for every \(r\geq2\) an integer.

For the special case \(r=2\), Ryser’s conjecture is equivalent to Kőnig’s Theorem. Aharoni [10] proved the only other known general case of the conjecture when \(r=3\). However, Ryser’s conjecture is also known to be true in some special cases. Tuza [11] verified Ryser’s conjecture for \(r\leq5\) if the set system is intersecting. Furthermore, Francetic et al., [12] verified Ryser’s conjecture for \(r\leq9\) if the set system is linear, that is, a 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}\). In this note, a linear system will be written by \((P,\mathcal{L})\) instead of \((X,\mathcal{F})\); the elements of \(P\) and \(\mathcal{L}\) are called points and lines, respectively. In the rest of this paper, only linear systems are considered. Most of the definitions can be generalized for set systems. Thus, we deal with Ryser’s conjecture for intersecting \(r\)-partite linear systems, for every \(r\geq2\) an integer.

Intersecting linear Ryser’s Conjecture:

Every intersecting \(r\)-partite li-near system satisfies \(\tau\leq r-1\), for every \(r\geq2\) an integer.

In case the conjecture would be true, it is tight in the sense that for infinitely many \(r\)’s there are constructions of intersecting \(r\)-partite linear systems with \(\tau=r-1\). For example, if \(r-1\) is a prime power, consider the finite projective plane of order \(r-1\) as a linear system, \(\Pi_{r-1}\). This linear system is \(r\)-uniform and intersecting. To make it \(r\)-partite, one just needs to delete one point from the projective plane. This truncated projective plane, \(\Pi^\prime_{r-1}\), gives an intersecting \(r\)-partite linear system with \(\tau\geq r-1\), and \(r(r-1)\) points and \((r-1)^2\) lines. However, the construction obtained from the projective plane is not the “optimal” extremal. Although the projective plane construction only contains \(r(r-1)\) points (which is an optimal number of points), it has a lot of lines. Let \(f(r)\) be the minimum integer so that there exists an intersecting \(r\)-partite set system \((X,\mathcal{F})\) with \(\tau= r-1\) and \(|\mathcal{F}|=f(r)\) lines. Analogously, let \(f_l(r)\) be the minimum integer so that there exists an intersecting \(r\)-partite linear system \((P,\mathcal{L})\) with \(\tau=r-1\) and \(|\mathcal{L}|=f_l(r)\) lines. \(f_l(r)\) probably does not exist for some values of \(r\) (if \(r-1\) is a prime power, then \(\Pi^\prime_{r-1}\) is known to exist, providing proof that \(f_l(r)\) is well-defined). Hence, if \(f_l(r)\) does exist, for some \(r\geq2\) integer, then \(f(r)\leq f_l(r)\) (since any extremal linear system with \(f_l(r)\) edges is in particular a set system).

It is not difficult to prove that \(f_l(2)=1\) and \(f_l(3)=3\), see [13]. Furthermore, Mansour et al., [13] proved that \(f_l(4)=6\) and \(f_l(5)=9\). On the other hand, Aharoni et al., [14] proved that \(f_l(6)=13\) and \(f(7)=17\) (even when the truncated projective plane does not exist, since it has been proved that finite projective planes of order six do not exist, see [15]); however Franceti{\’ c} et al., [12] proved that \(f_l(7)\) does not exist, that is, there is no intersecting \(7\)-partite linear system such that \(\tau=6\). Abu-Khazneha et al., [16] constructed a new infinite family of intersecting \(r\)-partite set systems extremal to Ryser’s conjecture, which exist whenever a projective plane of order \(r-2\) exists. That construction produces a large number of non-isomorphic extremal set systems. Finally, Aharoni et al., [14] gave a lower bound on \(f(r)\) when \(r\to\infty\), showing that \(f(r)\geq\)3.052\(r+O(1)\), this lower bound is an improvement since Mansour et al., [13] proved that \(f(r)\geq(3-\frac{1}{\sqrt{18}})r(1-o(1))\approx\)2.764\((1-o(1))\), when \(r\to\infty\).

In this note, we give a lower bound for \(f_l(r)\) for small values of \(r\geq2\) an even integer.

Theorem 1. If \(r\geq2\) is an even integer, then \(3r-5\leq f_l(r)\).

Our lower bound is better than that given in [14], for some small values of \(r\geq2\) an even integer. If \(r\in\{2,4,6\}\), then \(f_l(r)=3r-5\). Aharoni et al., [14] proved that \(18\leq f(8)\) and \(24\leq f(10)\). Hence, Theorem \ref{thm:main_intro} implies that \(19\leq f_l(8)\) and \(25\leq f_l(10)\).

2. Main Results

In this section, the main results of this paper are presented. Before this, Some definitions and results are necessary.

Let \((P,\mathcal{L})\) be a linear system and \(p\in P\) be a point. The set \(\mathcal{L}_p\) is the set of lines incident to \(p\). In this context, the degree of \(p\) is \(\deg(p)=|\mathcal{L}_p|\) and \(\Delta=\Delta(P,\mathcal{L})\) is the maximum degree over all points of the linear system.

A subset \(R\) of lines of a linear system \((P,\mathcal{L})\) is a \(2\)-packing of \((P,\mathcal{L})\) if any three elements chosen in \(R\) do not have a common point. The 2-packing number of \((P,\mathcal{L})\), \(\nu=\nu_2(P,\mathcal{L})\), is the maximum cardinality of a 2-packing of \((P,\mathcal{L})\). There are some works that study this new parameter, see [17,18, 19, 20,21,22,23,24,25].

Theorem 2.[20] Let \((P,\mathcal{L})\) be a linear system and \(p\in P\) be a point such that \(\Delta=\deg(p)\) and \(\Delta’=\max\{\deg(x): x\in P\setminus\{p\}\}\). If \(|\mathcal{L}|\leq \Delta+\Delta’+\nu_2-3\), then \(\tau\leq\nu_2-1\).

Let \(r\geq3\) be an integer. If \((P,\mathcal{L})\) is an intersecting \(r\)-uniform linear system, then \(\nu_2\leq r+1\). However, if \(\nu_2=r+1\), for \(r\geq4\) an even integer, then \(\tau=\lceil \nu_2/2\rceil\), see [22]. Hence, we assume that \(\nu_2\leq r\) if \(r\geq4\) is an even integer.

Lemma 1.[20] Let \((P,\mathcal{L})\) be an intersecting \(r\)-uniform linear system, with \(r\geq3\) an odd integer. If \(\tau=r\), then \(\nu_2=r+1\).

Lemma 2.[24] Let \((P,\mathcal{L})\) be an intersecting \(r\)-uniform linear system, with \(r\geq4\) an even integer. If \(\tau=r\), then \(\nu_2=r\).

Lemma 3. Let \((P,\mathcal{L})\) be an intersecting \(r\)-uniform linear system with \(r\geq4\) an even integer. If \(\tau=r-1\), then \(\nu_2=r\).

Proof Let \((P,\mathcal{L})\) be an intersecting \(r\)-uniform linear system. Let \(p\in P\) be a point such that \(\Delta=\deg(p)\) and \(\Delta^\prime=\max\{\deg(x): x\in P\setminus\{p\}\}\). By Theorem 2 if \(|\mathcal{L}|\leq\Delta+\Delta^\prime+\nu_2-3\leq3(r-1)\) (since \(\Delta\leq r\) and \(\nu_2\leq r\)), then \(\tau\leq\nu_2-1\), which implies that \(\nu_2=r\), since \(r-1\leq\tau\leq\nu_2-1\leq r-1\).

By Lemmas 2 and 3, we have:

Corollary 1. Let \((P,\mathcal{L})\) be an intersecting \(r\)-uniform linear system with \(r\geq4\) an even number. If \(\tau\in\{r-1,r\}\), then \(\nu_2=r\).

By Lemma 1 and Corollary 1, we have:

Theorem 3. Let \(r\geq3\) be an integer. Then every intersecting \(r\)-partite linear system satisfies

1. \(\tau\leq r-1\) If \(\nu_2\leq r\) and \(r\geq3\) an odd integer; and
2. \(\tau\leq r-2\) if \(\nu_2\leq r-1\) and \(r\geq4\) an even integer.

To prove intersecting linear Ryser’s Conjecture it suffices to analyze the following two cases concerning the 2-packing number:

Conjecture 1. Let \(r\geq3\) be an integer. Then every intersecting \(r\)-partite linear system satisfies:

1. \(\tau\leq r-1\) if \(\nu_2=r+1\), with \(r\geq3\) an odd number.
2. \(\tau\leq r-1\) if \(\nu_2=r\), with \(r\geq4\) an even number.

Theorem 4. Let \(r\geq4\) be an even integer, then \(3r-5\leq f_l(r)\).

Proof Assume that \(\nu_2\leq r-1\) (by Corollary 1). Let \(p\in P\) be a point such that \(\Delta=\deg(p)\) and \(\Delta’=\max\{\deg(x): x\in P\setminus\{p\}\}\). By Theorem 2 if \(|\mathcal{L}|\leq\Delta+\Delta’+\nu_2-3\leq3r-6\) (since \(\Delta\leq r-1\)), then \(\tau\leq\nu_2-1\leq r-2\). Therefore, \(3r-5\leq f_l(r)\).

Acknowledgments

The author would like to thank the referees for careful reading of the manuscript. Research was partially supported by SNI and CONACyT.

Author Contributions:

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

“The authors declare no conflict of interest.”