On transversal and 2-packing numbers in uniform linear systems

DOI10.1016/J.AKCEJ.2019.03.014MaRDI QIDQ5154597zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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$.

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

Cites work

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

Cited in

(6)

• On transversal numbers of intersecting straight line systems and intersecting segment systems
• On transversal and 2-packing numbers in straight line systems on \({\mathbb R}^2\)
• On domination and 2-packing numbers in intersecting linear systems.
• 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 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)