3
$\begingroup$

[Crossposted at math.stackexchange.]

Originally I posted a slightly more complicated version of this question. I decided to edit and put it in this simplified form, because I think that if we can answer this question then we can answer the original one too.

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is intersection-closed ($\mathcal{F}$ must contain at least one instance of $A \cap B$ for any $A,B \in \mathcal{F}$);
  2. every element in $U(\mathcal{F})$ belongs to at least $\lceil (n-1)/2 \rceil$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).

Is it possible to prove that, for any possible choice of $\mathcal{F}$, there exist $A, B \in \mathcal{F}$ such that $A \cup B = U(\mathcal{F})$?

Maybe a sketch of a possible approach could be starting from the power set $\mathcal{P}(U(\mathcal{F}))$, then try to remove an intersection irreducible set to obtain another intersection-closed family modifying set multiplicites as needed by requirement $2$, and show that we cannot do that without removing all intersection irreducible sets of the same size. Alternatively, start from an intersection-closed family without any $A,B$ such that $A \cup B = U(\mathcal{F})$, then show that if we add sets still without such $A, B$, then condition $2$ keeps being unsatisfied.

$\endgroup$
9
  • 2
    $\begingroup$ Is the problem solvable/easier without the condition " In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set."? $\endgroup$
    – kodlu
    Commented Jul 19 at 15:28
  • 1
    $\begingroup$ @AlecRhea yes I think so. See for example here. $\endgroup$ Commented Jul 19 at 15:33
  • 1
    $\begingroup$ Regardless, it seems everything would get clearer if you replace each set with the complement: Then the assumptions are that the family is union-closed and each element is in at most $\lfloor (n+1)/2\rfloor $ of the sets in the family, and the desired conclusion is that the family has two members that are disjoint. $\endgroup$
    – Will Sawin
    Commented Jul 19 at 19:15
  • 1
    $\begingroup$ Please be aware that every edit of a question or of one of its answers bumps the thread to the front page. This has happened for this thread already about 20 times in just a few days, and this is a nuisance for other users. Please refrain from unnecessary edits to your posts. $\endgroup$
    – Stefan Kohl
    Commented Jul 20 at 12:40
  • 1
    $\begingroup$ @StefanKohl sorry, I will try to be less anxious and make less errors next time. $\endgroup$ Commented Jul 20 at 12:52

1 Answer 1

5
$\begingroup$

No.

Let $U$ be the Fano plane, a set of $7$ elements. Let $\mathcal F$ consist of the complements of the lines in the Fano plane, each with multiplicity $1000000000000$, together with all their intersections, each with multiplicity $1$. Since each point lies in $4$ of the $7$ line complements, it lies in very slightly more than $4/7$ of the sets, so the second condition is satisfied. But since any two lines intersect at a point, any two line complements must together miss a point, and then the same property holds for any two intersections of line complements.

$\endgroup$
2
  • $\begingroup$ It's probably easier to see this by thinking complementarily, as your language suggests implicitly and your comment suggests explicitly. $\endgroup$
    – LSpice
    Commented Jul 19 at 19:46
  • $\begingroup$ Thank you. I formulated the problem for an intersection-closed family because the question is related to this other question and your answer here can be used to build an example as asked by that question. $\endgroup$ Commented Jul 19 at 20:56

You must log in to answer this question.

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