Minimal covering sets for infinite set systems
type: Item
instance of: scholarly article
title: Minimal covering sets for infinite set systems
zbMATH Open document ID: 1475.03094
published in: Discrete Mathematics
publication date: 2019-06-27T00:00:00Z
review text: Given a set \(V\) and a collection \(\mathcal H\) of non-empty subsets of \(V\), \(M \subseteq V\) is a covering set if \(M \cap A \neq \emptyset\) for all \(A \in \mathcal H\). \(M\) is a minimal covering set if \(M\) is a covering set and no proper subset of \(M\) is a covering set. Covering sets are the topic of a question raised by \textit{T. Banakh} and \textit{D. van der Zypen} [Discrete Math. 342, No. 11, 3043--3046 (2019; Zbl 1419.05156)]. If \(r\) is a fixed natural number and \(\mathcal H\) is a system of sets with the property that \(|A \cap B| \leq r\) for all distinct \(A,B \in \mathcal H\), must \(\mathcal H\) have a minimal covering set? In 1937, E.W. Miller show that if \(\mathcal H\) is a collection of infinite sets with the intersection property in the question, then \(\mathcal H\) is 2-chromatic. Erdoős and Hajnal generalized this in [\textit{P. Erdős} and \textit{A. Hajnal}, Acta Math. Acad. Sci. Hung. 12, 87--123 (1961; Zbl 0201.32801)]. In this paper, the author applies some of the techniques of Erdős and Hajnal [loc. cit.] to investigate some specific instances of this problem where additional information about the set system \(\mathcal H\) is available. He finds criteria that guarantee an affirmative answer to the question and also shows that, consistently, there are systems \(\mathcal H\) with small intersections that do not have minimal covering sets. As a sample, the following conditions on \(\mathcal H\) guarantee the existence of a minimal covering set: \begin{itemize} \item[1.] \(\mathcal H\) consists of finite sets. \item[2.] \(S\) is a set, \(\mu\) is an infinite cardinal, \(\mathcal H\) consists of \(\mu\)-sized subsets of \(S\), and there is a natural number \(r\) so that \(|A \cap B| \leq r\) for all distinct \(A,B \in \mathcal H\). \item[3.] \(S\) is a set, \(\mu\) is an infinite cardinal, \(\mathcal H\) consists of \(\mu\)-sized subsets of \(S\), and there is a well-ordering \(\prec\) of \(\mathcal H\) so that \(A \not\subseteq \…
reviewed by: Jared Holshouser
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 7074174
zbMATH Keywords: infinite set system
zbMATH Keywords: minimal covering set
author: Péter Komjáth
describes a project that uses: MathOverflow
MaRDI profile type: Publication
full work available at URL: j.disc.2019.03.007
OpenAlex ID: W2923009083
cites work: On a property of families of sets
cites work: Q3344197
cites work: Splitting Strongly Almost Disjoint Families
cites work: On the minimal covering of infinite sets
cites work: Q3686707
cites work: Families close to disjoint ones
cites work: Q3895456
DOI: 10.1016/J.DISC.2019.03.007
description: scientific article; zbMATH DE number 7074174