Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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). –  Dustin G. Mixon May 22 '13 at 13:44
    
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. –  Allen Knutson May 22 '13 at 14:15
add comment

2 Answers

up vote 9 down vote accepted

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 http://en.wikipedia.org/wiki/Erdős–Ko–Rado_theorem 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.

share|improve this answer
2  
"in the 1979 edition of the Handbook of Combinatorics" I do not believe such a book exists (or ever existed). –  quid May 22 '13 at 16:25
    
I think you have empty intersection in a place where you mean nonempty intersection. Gerhard "Ask Me About Feeling Empty" Paseman, 2013.05.22 –  Gerhard Paseman May 22 '13 at 16:26
    
@Gerhard: yes, that's embarrassing. Fixed it. –  Russ Woodroofe May 22 '13 at 16:33
    
@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. –  Russ Woodroofe May 22 '13 at 16:36
    
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. –  quid May 22 '13 at 16:47
show 3 more comments

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

share|improve this answer
    
From the abstract of Poonen's 1992 article Union-closed families dx.doi.org/10.1016/0097-3165(92)90068-6 comes the sentence "Frankl conjectured in 1979 that...". –  András Salamon May 22 '13 at 21:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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