11
$\begingroup$

A finite topological space is a finite family of finite sets that is closed under both union and intersection.

Frankl's conjecture states that for any finite union-closed family of finite sets, other than the family consisting only of the empty set, there exists an element that belongs to at least half of the sets in the family.

Is Frankl's conjecture known to be true when restricted to finite topological spaces?

$\endgroup$
20
$\begingroup$

Consider the smallest nonempty set $S$ in our family $\mathcal F$ and pick any $s\in S$. Let $\mathcal F_0$ be the subfamily of sets not containing $s$ (including $\varnothing$) and $\mathcal F_1$ the subfamily of sets containing $s$.

If $s\not\in A\in\mathcal F$, then $S\cap A$ is a smaller element of $\mathcal F$, so it must be empty. Hence the map $\mathcal F_0\to\mathcal F_1,A\mapsto S\cup A$ is an injection (with inverse $B\mapsto B\setminus S$). Hence $|\mathcal F_1|\geq|\mathcal F_0|,|\mathcal F_1|\geq|\mathcal F|/2$.

$\endgroup$
  • $\begingroup$ Very good. Was this known before you answered it? $\endgroup$ – Craig Feinstein Nov 26 '17 at 19:31
  • 2
    $\begingroup$ I have never researched that problem, so I don't know. Given how elementary it is, I would be surprised if we were the first ones to consider it :) $\endgroup$ – Wojowu Nov 26 '17 at 19:46
  • $\begingroup$ I don't recall this form being stated, but I imagine it is part of the folklore of the problem. In particular, Poonen's work in the 90's likely has something similar. You can find on ArXiv a survey that may answer your question about when it may have been formed. Gerhard "Something To Do With Semilattices" Paseman, 2017.11.26. $\endgroup$ – Gerhard Paseman Nov 26 '17 at 21:01
  • 9
    $\begingroup$ You are asking whether Frankl's conjecture holds for distributive lattices. This was stated by Rival and proved by Poonen and subsequently generalized in various ways, e.g., lower semimodular lattices. See zaik.uni-koeln.de/~schaudt/UCSurvey.pdf. It is also easy to prove for lattices such that for every $\hat{0}<s\leq t$ there exists $u\neq t$ for which $s\vee u=t$. See Enumerative Combinatorics, vol. 1, 2nd ed., Exercise 3.102(b). $\endgroup$ – Richard Stanley Nov 26 '17 at 21:22
  • $\begingroup$ Thanks, I saw that survey before but didn't recognize the name semimodular lattices. $\endgroup$ – Craig Feinstein Nov 27 '17 at 1:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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