7
$\begingroup$

Let $X$ be an infinite set, and let ${\cal A}\subseteq{\cal P}(X)$ be a family of non-empty sets. We say $S\subseteq X$ is a cover for ${\cal A}$ if $A\cap S \neq \emptyset$ for all $A\in{\cal A}$.

Suppose that we have $A\neq B \in {\cal A}$ implies $|A\cap B|\leq 1$. Is there a cover $M\subseteq X$ for ${\cal A}$ such that for all $m\in M$ the set $M\setminus \{m\}$ is not a cover of ${\cal A}$?

$\endgroup$

3 Answers 3

4
$\begingroup$

I think I can do one case. Assume that $A_i\subseteq S$, $|A_i|=\aleph_0$ for $i\in I$, and $|A_i\cap A_j|\leq 1$ for $i\neq j$. By a theorem in the paper P. Komjáth: Families close to disjoint ones, Acta Math. Hung. 43 (1984), 199–204, there are cofinite sets $A'_i\subseteq A_i$ such that $\{A'_i:i\in I\}$ is disjoint.

Let $X$ be the following graph on $I$: $\{i,j\}\in X$ iff $(A_i-A'_i)\cap A'_j\neq\emptyset$. Given $i$ there is just finitely many $j$ as above, so there is an orientation of $X$ with all vertices having finite outdegrees. By an old result of Erdos and Hajnal, there is a well ordering $\prec$ of $I$ s. t. each vertex has only finitely many edges of $X$ going down. By transfinite recursion on $\prec$ pick $x_i\in A'_i$ for some $i\in I$ (let $I'$ be the set of those elements of $I$) as follows. If there is $j\prec i$ with $x_j\in A_i$, then set $i\notin I'$. Otherwise, pick $x_i\in A'_i-\bigcup\{A_j-A'_j:j\prec i\}$. This is possible, as the subtracted set is finite by the property of $\prec$. Now $B=\{x_i:i\in I'\}$ is obviously covering. Remove one element of it: $B'=B-\{x_i\}$ for some $i\in I'$. The way of the construction, $x_j\notin A_i$ for $j\prec i$. But there is no $i\prec j$ with $x_j\in A_i-A'_i$ either by the way $x_j$ was chosen, so $B'\cap A_i=\emptyset$.

$\endgroup$
4
  • 1
    $\begingroup$ Another easy, case: if ${\cal A}$ is an infinite collection of finite sets, then there is always a minimal covering by Zorn's lemma. $\endgroup$ Commented Aug 3, 2017 at 15:24
  • $\begingroup$ Thank you Peter for these cases! As it is a partial answer (but a very valuable one) I hope you don't mind me not accepting yet. $\endgroup$ Commented Aug 3, 2017 at 19:47
  • $\begingroup$ Yes, that's correct. $\endgroup$ Commented Aug 4, 2017 at 21:15
  • $\begingroup$ In P. Komjáth, "Families close to disjoint ones," Acta Math. Hung. 43 (1984), 199–204, you state that you have a generalization of Theorem 2. What is it? And precisely what result of Erdos and Hajnal are you using (so I can look up the proof)? $\endgroup$
    – Tri
    Commented Nov 26, 2017 at 20:21
2
$\begingroup$

We could not solve the original problem, but we could handle some more cases of the problem in 1.

1 T. Csernák, L. Soukup, Minimal vertex covers in infinite hypergraphs, Discrete Mathematics, Volume 346, Issue 4, April 2023.

A hypergraph possesses property $C({k},{\rho})$ iff $|\bigcap \mathcal E'|<{\rho}$ for each $k$ element set $\mathcal E'$ of hyperedges.

Komjáth proved that every uniform hypergraph possessing property $C(2,r)$ for some $r\in {\omega}$ has a minimal vertex cover. In this paper we relaxed the assumption of uniformity to an assumption that the set of cardinalities of the hyperedges is a ``small'' set of infinite cardinals, e.g. it is countable, or it does not contain uncountably many limit cardinals.

Komjáth also proved that GCH does not decide the following statement: "If a hypergraph $G$ possessing property $C({2},{{\omega}})$ is ${\mu}$-uniform for some ${\mu}\ge {\omega}_1$, then $G$ has a minimal vertex cover."

Using Shelah's Revised GCH theorem, we show that if we strengthen the assumption ${\mu}\ge {\omega}_1$ to ${\mu}\ge \beth_{\omega}$, then we can prove the statement in ZFC!

We also show that if all the hyperedges of a hypergraph are countably infinite,
then instead of $C({2},{r})$ the assumption $C({k},{r})$ (for some $k\in {\omega}$) is enough to guarantee the existence of a minimal vertex cover. If every hyperedge has cardinality ${\omega}_1$, then we can only prove that $C({3},{r})$ is enough.

$\endgroup$
1
  • 1
    $\begingroup$ Congratulations on your result! $\endgroup$ Commented Dec 9, 2022 at 13:49
1
$\begingroup$

[Incorrect answer, perhaps mendable, perhaps not, sorry, see my comments below]

The answer is yes, the statement is in fact equivalent to AC.

AC is equivalent to "every set of pairwise disjoint nonempty sets has a choice set". So to see that the statement implies AC we can let ${\cal A}\subseteq{\cal P}(X)$ consist of pairwise disjoint sets.

Let $M\subseteq X$ be a minimal cover for ${\cal A}$ , that is: for all $m\in M$ the set $M\setminus \{m\}$ is not a cover of ${\cal A}$. Then $M$ is a choice set for ${\cal A}$. $$ $$ To see that AC implies the statement, we use Zorn's lemma.

For given ${\cal A}\subseteq{\cal P}(X)$ with the property that $A\neq B \in {\cal A}$ implies $|A\cap B|\leq 1$, let $H\subset {\cal P}({\cal A})\times{\cal P}(X)$ be defined by: $$ $$ $$H := \ \{(K,L)\in {\cal P}({\cal A})\times{\cal P}(X)\ |\ L\ \mbox{is a minimal cover for}\ K\ \}$$

$$ $$ We define a partial order on $H$ using set-inclusion: $$(K,L)\leq(K',L'):= K\subseteq K' \wedge L\subseteq L'$$ $$ $$ For $J=(K,L)\in H$ let $J_0=K, J_1=L$ be the coordinate projections.

We verify that every ascending chain in $(H,<)$ has an upper bound. Let $G\subseteq H$ such that $<$ is a total order on $G$. Then the upper bound $T$ for $G$ is given by:

$$T = (\bigcup_{J\in G} J_0, \bigcup_{J\in G} J_1)$$

It is straightforward to see that $\bigcup_{J\in G} J_1$ is again a minimal cover for $\bigcup_{J\in G} J_0$, so indeed $T$ is in $H$.

It is easy to see that there are non-empty ascending chains. By Zorn's lemma, $(H,<)$ contains a maximal element $U=(V,W)$. We claim that $V={\cal A}$, or in other words: $W$ is the desired minimal cover for ${\cal A}$.

To see that $V={\cal A}$, suppose there is $X\in{\cal A}, X\not\in V$.

case 1) $X\cap W \not= \emptyset$. Then $(V\cup\{X\},W)$ is larger than $(V,W)$, contradiction.

case 2) $X\cap W = \emptyset$. Pick $x\in X$. Then $(V\cup\{X\},W\cup\{x\})$ is larger than $(V,W)$, again contradiction.

$\endgroup$
7
  • $\begingroup$ aww... it always happens to me that possible flaws occur 5 minutes after I post something. I suddenly see a possible snag in the upper bound argument, but do not have the time to check it out now. Sorry, will come back to this. $\endgroup$ Commented Nov 26, 2017 at 11:01
  • $\begingroup$ It might be necessary (and hopefully sufficient) to demand that the sets which are minimally covered stay stable, in the ascending chain. But I really have to spend some more time on this. $\endgroup$ Commented Nov 26, 2017 at 11:07
  • $\begingroup$ So perhaps the order definition should be: $(K,L)\leq(K',L'):= K\subseteq K' \wedge L\subseteq L'\wedge\forall A\in K\,[|A\cap L|= 1\rightarrow |A\cap L'|=1]$. $\endgroup$ Commented Nov 26, 2017 at 11:13
  • $\begingroup$ Ah but then case 2 fails. Sorry, I have to think better and longer. $\endgroup$ Commented Nov 26, 2017 at 11:16
  • 1
    $\begingroup$ No problem. Everybody makes mistakes. Take your time. Meanwhile, if you feel like it, you have an option to delete your answer and to undelete it later when you know how to fix it. Letting it stay is also OK, just put a remark in the beginning that it is still "work in progress" to spare reader's time $\endgroup$
    – fedja
    Commented Nov 26, 2017 at 11:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .