12
$\begingroup$

A cover $\mathcal C$ of a set $X$ by subsets of $X$ is called

$\bullet$ minimal if for every $C\in\mathcal C$ the family $\mathcal C\setminus\{C\}$ is not a cover of $X$;

$\bullet$ minimizable if $\mathcal C$ contains a minimal subcover of $X$.

For example, any cover of the plane by parallel lines is minimal.

Problem. Is each cover of the plane $\mathbb R^2$ by lines minimizable? What is the answer for the rational plane $\mathbb Q^2$?

Acknowledgement. The problem was motivated by this question of Dominic van der Zypen.


Added in Edit. For the rational plane the affirmative answer can be also deduced from the following general

Theorem. A countable hypergraph $H=(V,\mathcal E)$ admits a minimal set $\mathcal M\subset \mathcal E$ with $\bigcup \mathcal M=\bigcup \mathcal E$ if each infinite set of vertices $I\subset V$ contains a finite set $F\subset I$ such that the set of edges $\{E\in \mathcal E:F\subset E\}$ is finite.

The proof of this theorem is a bit complicated and will be presented in our joint paper with Dominic van der Zypen.

We do not know if this theorem holds for arbitrary (not necessarily countable) hypergraphs.

On the other hand, @Peter Komjath in his comment to the answer of @bof claims that he can prove that every cover of the real plane by lines is minimizable, using some (difficult) general result on minimal covers of hypergraphs whose edges have the same cardinality and have small intersections.

$\endgroup$
3
  • 1
    $\begingroup$ Could you please give an example of non-minimizable covers? $\endgroup$ Aug 21, 2018 at 7:44
  • 2
    $\begingroup$ @MeisamSoleimaniMalekan The cover $\{[0,n]:n\in\omega\}$ of $\omega$ is not minimizable. For less trivial examples, see the answer to the question (mathoverflow.net/questions/308265/…) of Dominic van der Zypen. $\endgroup$ Aug 21, 2018 at 9:04
  • $\begingroup$ In fact, the non-minimizable cover $\{[0,n]\}_{n\in\omega}$ is essentially a unique example of a non-minimizable cover: recently we have proved that for a hypergraph $H$ each subhypergraph is minimizable if and only if no subhypergraph of $H$ is isomorphic to the non-minimizable hypergraph $(\omega,\{n\}_{n\in\omega})$. $\endgroup$ Aug 24, 2018 at 5:55

1 Answer 1

9
$\begingroup$

Unfortunately, you have two questions in one post. The one about $\mathbb R^2$ is too hard for me. The question about $\mathbb Q^2$ seems to have an easy affirmative answer, unless I'm making some dumb mistake.

Let $P=\{p_0,p_1,p_2,\dots\}$ be the set of points, and let $L$ be the set of lines. (In general, the construction seems to work for any countable bipartite graph which is $C_4$-free and has no isolates.)

Let $L_0=L.$ Consider the point $p_0.$ Let $L'_0$ be the set of all lines $\ell\in L_0$ such that $p_0\in\ell$ and $L_0\setminus\{\ell\}$ covers $P.$ So $L_0\setminus L'_0$ covers at least $P\setminus\{p_0\}.$ If $L_0\setminus L'_0$ covers $P,$ let $L_1=L_0\setminus L'_0.$ Otherwise, choose some $\ell\in L'_0$ and let $L_1=(L\setminus L'_0)\cup\{\ell\}.$

Continue in this way. I.e., Let $L'_1$ be the set of all lines $\ell\in L_1$ such that $p_1\in\ell$ and $L_1\setminus\{\ell\}$ covers $P,$ etc.

Finally, I claim that the set $L_\infty=\bigcap_{n=0}^\infty L_n$ is a minimal cover.

Maybe the construction will be clearer in words. At step $n$ we have the set $L_n$ of lines which have not yet been deleted (and this set still covers $P$), and we look at the point $p_n.$ We look at the set of all (undeleted) lines through $p_n.$ If such a line contains some point which is on no other (undeleted) line, we save it; if it contains no such point, we delete it. However, if this results in deleting all lines through $p_n,$ then we save one of them.

Note that, after step $n,$ the point $p_n$ is covered by at least one line $\ell_n$ which will never be deleted, because it contains a point which is on no other line. Therefore $L_\infty$ is a cover. It is a minimal cover because, if $\ell$ is in $L_\infty,$ and if $p_n\in\ell,$ then after step $n$ has been done there is some point on $\ell,$ either $p_n$ or some other point, which is in no other surviving line.

P.S Now suppose $P=\mathbb R^2$ and $L$ is a cover of $\mathbb R^2$ by lines. I think the same construction will work under some very restrictive assumptions on the cover; namely, that we can enumerate the points as $\mathbb R^2=\{p_\alpha:\alpha\lt\mathfrak c\}$ so that, for each $\alpha,$ either $|\{\ell\in L:p_\alpha\in L\}|\lt\omega$ or else $|\{\ell\in L:p_\alpha\in L\}|\gt|\alpha|.$ This is to prevent $p_\alpha$ from getting uncovered at limit stages.

$\endgroup$
5
  • $\begingroup$ Very good. Thanks! So, it remains the uncountable case. $\endgroup$ Aug 21, 2018 at 10:30
  • $\begingroup$ So, the problem is with point-countable covers (under CH)? $\endgroup$ Aug 21, 2018 at 11:13
  • 1
    $\begingroup$ It seems that we can modify the construction so that it will work in uncountable case as well. Just put $L_0'$ be $L_0\setminus\{\ell\in L_0:p_0\in\ell\}$, next consider the set $\bigcup L_0'$ and for every $x\in P\setminus\bigcup L_0'$ choose a line $\ell_x\in L$ that contained the points $p_0$ and $x$. Then put $L_1=L_0'\cup\{\ell_x:x\in P\setminus \bigcup L'_0\}$. And so on. It seems that such modification survives the limit stage. $\endgroup$ Aug 21, 2018 at 11:33
  • 2
    $\begingroup$ I can prove the $\mathbb{R}^2$ case, in general, if the system is {\em uniform}, that is, if it consists of sets of the same cardinality. The proof is pretty complicated. $\endgroup$ Aug 21, 2018 at 14:27
  • $\begingroup$ @PéterKomjáth Unfortunately, I have found a gap in the proof of my general theorem about minimal covers of hypergraphs. It works only for countable hypergraphs, like in the answer of bof. So, for me the problem with covers of real plane is open again, and I am eager to know how do you prove the general result for uniform hypergraphs. $\endgroup$ Aug 23, 2018 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.