On transversal and 2-packing numbers in uniform linear systems

DOI10.1016/J.AKCEJ.2019.03.014zbMATH Open1473.05303arXiv1903.08984OpenAlexW2963919712WikidataQ128175912 ScholiaQ128175912MaRDI QIDQ5154597FDOQ5154597

Authors: Carlos A. Alfaro, Christian Rubio-Montiel, Adrián Vázquez Ávila, G. Araujo-Pardo 

Publication date: 5 October 2021

Published in: AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Abstract: A linear system is a pair $(P,mathcalL)$ where $mathcalL$ is a family of subsets on a ground finite set $P$, such that $|lcap{l}^{p}rime|leq1$, for every $l,l^{p}rimeinmathcalL$. The elements of $P$ and $mathcalL$ 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 $T$ of points of $P$ is a transversal of $(P,mathcalL)$ if $T$ intersects any line, and the transversal number, $au(P,mathcalL)$, is the minimum order of a transversal. On the other hand, a 2-packing set of a linear system $(P,mathcalL)$ is a set $R$ of lines, such that any three of them have a common point, then the 2-packing number of $(P,mathcalL)$, $u_2(P,mathcalL)$, is the size of a maximum 2-packing set. It is known that the transversal number $au(P,mathcalL)$ is bounded above by a quadratic function of $u_2(P,mathcalL)$. An open problem is to haracterize the families of linear systems which satisfies $au(P,mathcalL)leqlambda{u}_2(P,mathcalL)$, for some $lambdageq1$. In this paper, we give an infinite family of linear systems $(P,mathcalL)$ which satisfies $au(P,mathcalL)=u_2(P,mathcalL)$ with smallest possible cardinality of $mathcalL$, as well as some properties of $r$-uniform intersecting linear systems $(P,mathcalL)$, such that $au(P,mathcalL)=u_2(P,mathcalL)=r$. Moreover, we state a characterization of $4$-uniform intersecting linear systems $(P,mathcalL)$ with $au(P,mathcalL)=u_2(P,mathcalL)=4$.

Full work available at URL: https://arxiv.org/abs/1903.08984

Recommendations

• A note on a problem of Henning and Yeo about the transversal number of uniform linear systems whose 2-packing number is fixed
• On transversal and 2-packing numbers in straight line systems on \({\mathbb R}^2\)
• On transversal numbers of intersecting straight line systems and intersecting segment systems
• A note on domination in intersecting linear system
• Transversals in 4-uniform linear hypergraphs

zbMATH Keywords

linear systemsfinite projective planetransversal number2-packing number

Mathematics Subject Classification ID

Transversal (matching) theory (05D15) Combinatorial structures in finite projective spaces (51E20) Helly-type theorems and geometric transversal theory (52A35)

Cites Work

• Small transversals in hypergraphs
• Graph theory with applications
• Title not available (Why is that?)
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Hypermaps versus bipartite maps
• Transversal numbers for hypergraphs arising in geometry
• Linear hypergraphs with large transversal number and maximum degree two
• Title not available (Why is that?)
• A characterization of the graphs in which the transversal number equals the matching number
• HYPERGRAPHS
• On the independence number of Steiner systems
• Subdivision Drawings of Hypergraphs
• Piercing numbers for balanced and unbalanced families
• The maximum piercing number for some classes of convex sets with the \((4,3)\)-property
• Title not available (Why is that?)
• Piercing convex sets
• Small transversals in uniform hypergraphs
• About the piercing number of a family of intervals
• Domination in intersecting hypergraphs
• On transversal and 2-packing numbers in straight line systems on \({\mathbb R}^2\)

Cited In (5)

• On transversal and 2-packing numbers in straight line systems on \({\mathbb R}^2\)
• A note on domination in intersecting linear system
• A note on a problem of Henning and Yeo about the transversal number of uniform linear systems whose 2-packing number is fixed
• On transversal numbers of intersecting straight line systems and intersecting segment systems
• On intersecting straight line systems

This page was built for publication: On transversal and 2-packing numbers in uniform linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5154597)