On a problem of Henning and Yeo about the transversal number of uniform linear systems whose 2-packing number is fixed

preprint2020arXivOpen access

Abstract

A linear system is a pair (P,L)(P,\mathcal{L}) where L\mathcal{L} is a family of subsets on a ground finite set PP such that ∣l∩l′∣≤1|l\cap l^\prime|\leq 1, for every l,l′∈Ll,l^\prime \in \mathcal{L}. If all elements of L\mathcal{L} of a linear system (P,L)(P,\mathcal{L}), then the linear system is called rr-uniform linear system. The transversal number of a linear system (P,L)(P,\mathcal{L}), τ(P,L)τ(P,\mathcal{L}), is the minimum cardinality of a subset P^⊆P\hat{P}\subseteq P satisfying l∩P^≠∅l\cap\hat{P}\neq\emptyset, for every l∈Ll\in\mathcal{L}. The 2-packing number of a linear system (P,L)(P,\mathcal{L}), ν2(P,L)ν_2(P,\mathcal{L}), is the maximum cardinality of a subset R⊆LR\subseteq\mathcal{L} such that, any three elements of RR don't have a common point (are triplewise disjoint), that is, if three elements are chosen in RR, then they are not incidents in a common point. For r≥2r\geq2, let (P,L)(P,\mathcal{L}) be an rr-uniform linear system. In "{\sc M. A. Henning and A. Yeo:} {\it Hypergraphs with large transversal number,} Discrete Math. {\bf 313} (2013), no. 8, 959--966." Henning and Yeo state the following question: Is it true that if (P,L)(P,\mathcal{L}) is an rr-uniform linear system then τ(P,L)≤∣P∣+∣L∣r+1τ(P,\mathcal{L})\leq\displaystyle\frac{|P|+|\mathcal{L}|}{r+1} holds for all r≥2r\geq2?. In this note, we give some results of rr-uniform linear systems, whose 2-packing number is fixed, satisfying the inequality.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.