8
$\begingroup$

Frankl's conjecture, open since 1979, says that if $F$ is a union-closed family of subsets of $X$, then there is some $x \in X$ such that $x$ appears in at least half the sets in $F$.

What was the motivation for this conjecture? Is it a generalization of some simpler known fact?

$\endgroup$
2
  • 1
    $\begingroup$ I think the point is that it's very simply stated, using only basic concepts of set theory, and yet it's extremely difficult to prove anything (perhaps due to the lack of available structure). $\endgroup$ May 22, 2013 at 13:44
  • 2
    $\begingroup$ If by "motivation" one means "why should a mathematician care, how is it related to other mathematics", the evidence is that it's not, or we would have some way of attacking it. If one means "why should one feel that it's true", I always sensed that taking unions `puts elements in' rather than taking them out, and having that $x$ is another sign of having elements in. $\endgroup$ May 22, 2013 at 14:15

2 Answers 2

17
$\begingroup$

Frankl originally stated the dual of the problem as written here, i.e., in terms of intersections instead of unions. This seems to have been in the 1979 edition of the Handbook of Combinatorics [edit: No such edition exists, and I'm not sure of the original source. See comments below], which isn't that easy to find, but the current edition is up on Google Books, and he states it in this form at the beginning of his (updated) chapter on Extremal Set Systems as Conjecture 2.1: For an intersection-closed family of subsets of $[n]$, there is an element that is contained in at most half the subsets.

I always assumed that the conjecture was following in the spirit of Erdos-Ko-Rado type theorems. Let me expand below:

The Erdos-Ko-Rado Theorem bounds the size of a family of small sets $\mathcal{F}$ with pairwise nonempty intersection (see erdos-ko-rado for details). An extension of this due to Hilton-Milner says that a maximum-size family of small subsets of $[n]$ with pairwise nonempty intersection has an element contained in all of the subsets.

In the intersection-closed family $\mathcal{G}$ taken by considering all intersections of sets from $\mathcal{F}$ (satisfying the Erdos-Ko-Rado/Hilton-Milner conditions), this says that there is an element contained in all subsets from $\mathcal{G}$. If one makes it this far, it's reasonable to ask how few a number of subsets an element may be contained in, which is exactly what Frankl's Conjecture concerns.

UPDATE MAY 2016: I've had cause to look into the provenance more. Apparently Frankl asked the question in '79, and talked about it with several people, but never published it. The first appearance in print arises from a problem session at the 1984 conference on Graphs and Order in Banff, where Duffus presented several forms of the problem. The conference proceedings are in the volume "Graphs and order". From the summary there, Duffus appears to have already known several partial results on the conjecture that were only published much later.
See also the recent survey article of Bruhn and Schaudt.

$\endgroup$
9
  • 2
    $\begingroup$ "in the 1979 edition of the Handbook of Combinatorics" I do not believe such a book exists (or ever existed). $\endgroup$
    – user9072
    May 22, 2013 at 16:25
  • $\begingroup$ I think you have empty intersection in a place where you mean nonempty intersection. Gerhard "Ask Me About Feeling Empty" Paseman, 2013.05.22 $\endgroup$ May 22, 2013 at 16:26
  • $\begingroup$ @Gerhard: yes, that's embarrassing. Fixed it. $\endgroup$ May 22, 2013 at 16:33
  • $\begingroup$ @quid: Maybe not. I certainly didn't track it down! I saw a reference (Doug West's page on the conjecture, IIRC) which gave a year of 1979 and referred to the Handbook of Combinatorics. But it's possible that the conjecture was made at a conference/similar, and not written down until much later; this would make giving a reference quite difficult. $\endgroup$ May 22, 2013 at 16:36
  • $\begingroup$ It seems there isn't such thing in MathSciNet (which already makes its existence unlikely). Also I never had the impression the Handbook of Combinatorics (from the mid 1990s) is a new edition of anything, but I do not have physical access to one at the moment to check easily, but in any case again MathSciNet does not link it to any earlier edition, which it typically would. And, the way I read Douglas West's page it mentions a 1985 paper of Duffus as the earliest written source yet implying there must be earlier appeareances and then mentions Frankl's later paper where it is dated 1979. $\endgroup$
    – user9072
    May 22, 2013 at 16:47
3
$\begingroup$

As stated, there are a couple of counterexamples F. There are no known counterexamples when X is in F and X is finite and nonempty.

I do not know of Peter Frankl's original motivation. A 1990 paper of Bjorn Poonen "On the Union-Closed Sets Conjecture" has some suggestive examples, however. Note that it holds when F is the powerset of a nonempty X, and also when F is "large enough" in the sense that the average set size of a set in F is at least half the size of X. Also (as Dustin Mixon remarks), it is a very accessible and nontrivial statement, but not like Gauss said of Fermat's Last Theorem as being one of hundreds of statements in number theory of which he could neither readily prove nor dispose.

Gerhard "Ask Me About Frankl's Conjecture" Paseman, 2013.05.22

$\endgroup$
1

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.