13
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
22
$\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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very good. Was this known before you answered it? $\endgroup$
    – Craig Feinstein
    Nov 26, 2017 at 19:31
  • 3
    $\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, 2017 at 19:46
  • 1
    $\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, 2017 at 21:01
  • 10
    $\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, 2017 at 21:22
  • $\begingroup$ Thanks, I saw that survey before but didn't recognize the name semimodular lattices. $\endgroup$
    – Craig Feinstein
    Nov 27, 2017 at 1:23

Your Answer

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

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