![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A linear system is a pair where
is a family of subsets on a ground finite set
, such that
, for every
. The elements of
and
are called points and lines, respectively, and the linear system is called intersecting if any pair of lines intersect in exactly one point. A subset
of points of
is a transversal of
if
intersects any line, and the transversal number,
, is the minimum order of a transversal. On the other hand, a 2-packing set of a linear system
is a set
of lines, such that any three of them have a common point, then the 2-packing number of
,
, is the size of a maximum 2-packing set. It is known that the transversal number
is bounded above by a quadratic function of
. An open problem is to characterize the families of linear systems which satisfies
, for some
. In this paper, we give an infinite family of linear systems
which satisfies
with smallest possible cardinality of
, as well as some properties of
-uniform intersecting linear systems
, such that
. Moreover, we state a characterization of 4-uniform intersecting linear systems
with
.
1 Introduction
A linear system is a pair where
is a family of subsets on a ground finite set
, such that
, for every pair of distinct subsets
. The linear system
is intersecting if
, for every pair of distinct subsets
. The elements of
and
are called points and lines, respectively; a line with exactly
points is called a
-line, and the rank of
is the maximum cardinality of a line in
, when all the lines of
are
lines we have a
-uniform linear system. In this context, a simple graph is a 2-uniform linear system.
A subset is a transversal (also called vertex cover or hitting set in many papers, as example Citation[1–11]) of
if for any line
satisfies
. The transversal number of
, denoted by
, is the smallest possible cardinality of a transversal of
.
A subset is called 2-packing of
if three elements are chosen in
then they are not incident in a common point. The 2-packing number of
, denoted by
, is the maximum number of a 2-packing of
.
There are many interesting works studying the relationship between these two parameters, for instance, in [Citation10], the authors propose the problem of bounding in terms of a function of
for any linear system. In [Citation12], some authors of this paper and others proved that any linear system satisfies:
(1)
(1) That is, the transversal number,
, of any linear system is upper bounded by a quadratic function of their 2-packing number,
.
In order to find how a function of can bound
, the authors of [Citation13] using probabilistic methods to prove that
does not hold for any positive
. In particular, they exhibit the existence of
-uniform linear systems
for which their transversal number is
and their
-packing number is upper bounded by
.
Nevertheless, there are some relevant works about families of linear systems in which their transversal numbers are upper bounded by a linear function of their 2-packing numbers. In [Citation14] the authors proved that if is a 2-uniform linear system, a simple graph, with
then
; moreover, they characterize the simple connected graphs that attain this upper bound and the lower bound given in Eq. (1). In [Citation12] was proved that the linear systems
with
and
satisfy
; and when they attain the equality, they are a special family of linear subsystems of the projective plane of order
,
, with transversal and
-packing numbers equal to
. Moreover, they proved that
when
is a projective plane of order
, consequently the equality holds when q is odd.
The rest of this paper is structured as follows: In Section 2, we present a result about linear systems satisfying . In Section 3, we give an infinite family of linear systems such that
with smallest possible cardinality of lines. And, finally, in Section 4, we presented some properties of the
-uniform linear systems, such that
, and we characterize the
-uniform linear systems with
.
2 On linear systems with ![](//:0)
![](//:0)
Let be a linear system and
be a point. It is denoted by
to the set of lines incident to
. The degree of
is defined as
and the maximum degree overall points of the linear systems is denoted by
. A point of degrees
and
is called double and triple point, respectively, and two points
and
in
are adjacent if there is a line
with
.
In this section, we generalize Proposition 2.1, Proposition 2.2, Lemma 2.1, Lemma 3.1 and Lemma 4.1 of [Citation12] proving that a linear system with
and “few” lines satisfies
. Notice that, through this paper, all linear systems
are considered with
due to the fact
if and only if
.
Theorem 2.1
Let be a linear system with
being two points such that
and
. If
, then
.
Proof
Let be two points as in the theorem, and let
, which implies that
. Assume that
(
), otherwise, the following set
is a transversal of
of cardinality at most
, and the statement holds. Suppose that
is a set of pairwise disjoint lines because, in otherwise, they induce at least a double point,
, hence the following set of points
, where
is any point of
, is a transversal of
of cardinality at most
, and the statement holds. Let
be a fixed line and let
be any line of
, where
is the line containing to
and
(since
). Then
, since the
induce a triple point on the following 2-packing
, which implies that there exists a line
with
, and hence
. Consequently,
and
(since
). Therefore, the following set:
where
is any point of
, for
, is a transversal of
of the cardinality at most
, and the statement holds.□
3 A family of uniform linear systems with ![](//:0)
![](//:0)
In this section, we exhibit an infinite family of linear systems with two points of maximum degree and
with
. It is immediately, by Theorem 2.1, that
for linear systems with less lines.
In the remainder of this paper, is an additive Abelian group with neutral element
. Moreover, if
, then the group is called neutral sum group. In the following, every group
is a neutral sum group, such that
, for all
. As an example of this type of groups we have
, for
odd.
Let , with
a positive integer, and
be a neutral sum group of order
. Let:
for
, and:
for
, and
, where:
for
.
Hence, the set of lines is a set of pairwise disjoint lines with
and each line of
has
points. On the other hand,
and
are set of lines incidents to
and
, respectively, with
, and each line of
has
points. Moreover, this set of lines satisfies that, giving
there exists a unique
with
, otherwise, there exists
such that
, for all
, which implies that
, for all
, which is a contradiction.
The linear system with
, denoted by
, is an
-uniform linear system with
points and
lines. Notice that, this linear system has 2 points of degree
(points
and
) and
points of degree
.
A linear subsystem of a linear system
satisfies that for any line
there exists a line
such that
, where
. Given a linear system
and a point
, the linear system obtained from
by deleting the point
is the linear system
induced by
. On the other hand, given a linear system
and a line
, the linear system obtained from
by deleting the line
is the linear system
induced by
. The linear systems
and
are isomorphic, denoted by
, if after deleting the points of degree 1 or 0 from both, the systems
and
are isomorphic as hypergraphs (see [Citation15]).
It is important to state that in the rest of this paper is considered linear system without points of degree one because, if
is a linear system which has all lines with at least two points of degree 2 or more, and
is the linear system obtained from
by deleting all points of degree one, then they are essentially the same linear system because it is not difficult to prove that transversal and 2-packing numbers of both coincide (see [Citation12]).
Example 3.1
Let . The linear system
has as set of points to
and as set of lines to
, where
and depicted in . This linear system is isomorphic to the linear system giving in [Citation12] Figure 3, which is the linear system with the less number of lines and maximum degree 3 such that
.
Proposition 3.1
The linear system satisfies that:
Proof
Notice that since
is a transversal of
. To prove that
, suppose on the contrary that
. If
is a transversal of cardinality
then
, i.e.,
because, in other case, if
then, by the Pigeonhole principle, there is a line
such that
, since
, which is a contradiction, unless that
, which implies that there exists
such that
(because
), which is also a contradiction. Therefore
.
Suppose that:
where
and
, for
. Then:
since
, which implies that there exists
that satisfies
, which is a contradiction, and consequently
.□
Proposition 3.2
The linear system satisfies that:
Proof
Notice that because, for any two lines
,
is a 2-packing. To prove that
, suppose on the contrary that
, and that
is a maximum 2-packing of size
, we analyze two cases:
Case : Suppose that
, where
and
; since there is a unique line
which intersects
, then we assume that
. By construction of
there exists
that satisfies
, inducing a triple point, which is a contradiction.
Case : Let
be an element of
and
with
and
, without loss of generality, suppose that
,
,
and
, otherwise,
is not a 2-packing. It is claimed that there exists
such that either
or
, which implies that
induces a triple point, which is contradiction and hence
. To verify the claim suppose on the contrary that every
satisfies
and
. It means that
and
. By construction of
it follows that:
If and
, then
. On the other hand, as
and
, then
. As a consequence of
and
we obtain
, which is a contradiction. Therefore,
.□
Hence, by Propositions 3.1 and 3.2 it was proved that:
Theorem 3.2
Let , with
, then
with smallest possible cardinality of lines.
3.1 Straight line systems
A straight line representation on of a linear system
maps each point
to a point
of
, and each line
to a straight line segment
of
in such a way that for each point
and line
satisfies
if and only if
, and for each pair of distinct lines
satisfies
. A straight line system
is a linear system, such that it has a straight line representation on
. In [Citation12] was proved that the linear system
is not a straight one. The Levi graph of a linear system
, denoted by
, is a bipartite graph with vertex set
, where two vertices
, and
are adjacent if and only if
.
In the same way as in [Citation12] and according to [Citation16], any straight line system is Zykov-planar, see also [Citation17]. Zykov proposed to represent the lines of a set system by a subset of the faces of a planar map on , i.e., a set system
is Zykov-planar if there exists a planar graph
(not necessarily a simple graph) such that
and
can be drawn in the plane with faces of
two-colored (say red and blue) so that there exists a bijection between the red faces of
and the subsets of
such that a point
is incident with a red face if and only if it is incident with the corresponding subset. In [Citation18] was shown that the Zykov’s definition is equivalent to the following: A set system
is Zykov-planar if and only if the Levi graph
is planar. It is well-known that for any planar graph
the size of
,
, is upper bounded by
(see [Citation19] page 135, exercise 9.3.1 (a)), where
is the girth of
(the length of a shortest cycle contained in the graph
). It is not difficult to prove that the Levi graph
of
is not a planar graph, since the size of the girth of
is
, it follows:
for all
. Therefore, the linear system
is not a straight line system.
Finally, as a Corollary of Theorem 2.1, we have the following:
Corollary 3.1
Let be a straight line system with
being two points such that
and
. If
, then
.
4 Intersecting ![](//:0)
-uniform linear systems with ![](//:0)
![](//:0)
In this subsection, we give some properties of -uniform linear systems that satisfy
as well as a characterization of
-uniform linear systems with
.
Let be the family of intersecting linear systems
of rank
that satisfies
, then we have the following lemma:
Lemma 4.1
Each element of is an
-uniform linear system.
Proof
Let us consider and
any line of
. It is clear that
is a transversal of
. Hence
, which implies that
, for all
. Moreover,
, for all
and
. □
In [Citation20] was proved the following:
Lemma 4.2
[Citation20] Let be an
-uniform intersecting linear system then every edge of
has at most one vertex of degree 2. Moreover
.
Lemma 4.3
[Citation20] Let be an
-uniform intersecting linear system then
Hence, by Theorem 2.1 and Lemma 4.3 it follows:
Corollary 4.1
If then
.
In [Citation12] was proved that the linear systems with
and
satisfy
; and when they attain the equality, they are a special family of linear subsystems of the projective plane of order
,
(some of them 4-uniform intersecting linear systems) with transversal and
-packing numbers equal to
. Recall that a finite projective plane (or merely projective plane) is a 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
is a projective plane, there exists a number
, called order of projective plane, such that every point (line, respectively) of
is incident to exactly
lines (points, respectively), and
contains exactly
points (lines, respectively). In addition to this, it is well known that projective planes of order
, denoted by
, exist when
is a power prime. For more information about the existence and the unicity of projective planes see, for instance, Citation[21,22].
Given a linear system , a triangle
of
, is the linear subsystem of
induced by three points in general position (non collinear) and the three lines induced by them. In [Citation12] was defined
to be the linear system obtained from
by deleting
; also there was defined
to be the family of linear systems
with
, such that:
(i) |
| ||||
(ii) |
|
this is .
Hence, the authors proved the following:
Theorem 4.1
[Citation12] Let be a linear system with
. Then,
if and only if
.
Now, consider the projective plane and a triangle
of
(see
of ). Define
to be the linear subsystem induced by
(see
of ). The linear system
just defined has ten points and ten lines. Define
to be the family of 4-uniform intersecting linear systems
with
, such that:
Fig. 2 (a) Projective plane of order 3, and (b) Linear system obtained from
by deleting the lines of the triangle
.
![Fig. 2 (a) Projective plane of order 3, Π3 and (b) Linear system obtained from Π3 by deleting the lines of the triangle T.](/cms/asset/eeb1ec81-50b9-4eeb-93ec-524bd0a2e0c0/uakc_a_1760550_f0002_b.jpg)
(i) |
| ||||
(ii) |
|
It is clear that and each linear system
is a 4-uniform intersecting linear system. Hence
Corollary 4.2
if and only if
.
Acknowledgments
The author would like to thank the referees for careful reading and suggestions, which improved the manuscript.
References
- ChvátalV.McDiarmidC., Small transversal in hypergraphs Combinatorica 12 1 1992 19–26
- DorflingM.HenningM.A., Linear hypergraphs with large transversal number and maximum degree two European J. Combin. 362014 231–236
- EckhoffJ., A survey of the Hadwiger-Debrunner (p,q)-problem Discrete and Computational Geometry, Algorithms Combin. Vol, 252003SpringerBerlin347–377
- ErdösP.Fon-Der-FlaassD.KostochkaA.V.TuzaZ., Small transversals in uniform hypergraphs Siberian Adv. Math. 2 1 1992 82–88
- HuicocheaM.Jerónimo-CastroJ.MontejanoL.OliverosD., About the piercing number of a family of intervals Discrete Math. 338 12 2015 2545–2548
- KynčlJ.TancerM., The maximum piercing number for some classes of convex sets with the (4,3)-property Electron. J. Combin. 15 1 2008Research Paper 27, 16
- MontejanoL.SoberónP., Piercing numbers for balanced and unbalanced families Discrete Comput. Geom. 45 2 2011 358–364
- NogaA.GilK.MatousekJ.MeshulamR., Transversal numbers for hypergraphs arising in geometry Adv. Appl. Math. 29 1 2002 79–101
- NogaA.KleitmanD.J., Piercing convex sets Bull. Amer. Math. Soc. (N.S.) 27 2 1992 252–256
- NogaA.KleitmanD.J., Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem Adv. Math. 96 2 1992 252–256
- StersoulF., A characterization of the graphs in which the transversal number equals the matching number J. Combin. Theory Ser. B 271979 228–229
- Araujo-PardoG.MontejanoA.MontejanoL.Vázquez-ÁvilaA., On transversal and 2-packing numbers in straight line systems on R2 Util. Math. 1052017 317–336
- EustisA.VerstraëteJ., On the independence number of Steiner systems Combin. Probab. Comput. 22 2 2013 241–252
- C.A. Alfaro, C. Rubio-Montiel, A. Vázquez-Ávila, Covering and 2-packing number in graphs, preprint,https://arxiv.org/abs/1707.02254s.
- BergeC., Hypergraphs: Combinatorics of Finite Sets1984North-Holland Mathematical LibraryElsevier Science
- KaufmannM.van KreveldM.SpeckmannB., Subdivision drawings of hypergraphs Graph Drawing2009Berlin: Springer396–407
- ZykovA.A., Hypergraphs Uspekhi Mat. Nauk 29 6(180) 1974 89–154
- WalshT.R.S., Hypermaps versus bipartite maps J. Combin. Theory Ser. B 181975 155–163
- BondyJ.A., Graph Theory With Applications1976Elsevier Science Ltd.Oxford, UK
- DongY.ShanE.LiS.KangL., Domination in intersecting hypergraphs Discrete Appl. Math. 2512018 155–159
- BattenL.M., Combinatorics of Finite Geometries1986Cambridge Univ PressCambridge
- BuekenhoutF., Handbook of Incidence Geometry: Buildings and Foundations1995Elsevier