MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a naive question that could justifiably be quickly closed. Nevertheless:

Q. Why is Péter Frankl's conjecture so difficult?

If any two sets in some family of sets have a union that also belongs to the family, must some element belong to at least half of the sets in the family?

This has remained unsolved for ~$37$ years. It seems that, unlike other conjectures (say, concerning prime conjectures), it has not been confirmed for vastly huge sets (just: families of at most $50$ sets).

More specifically, can anyone indicate why this conjecture seems so difficult to prove or disprove? Why it has withstood assaults so long?

share|cite|improve this question
1  
@BenjaminDickman: This is an entirely apropos answer, and if you reformulate it as an explicit answer, I will accept it. Thanks! – Joseph O'Rourke Mar 5 at 2:49
6  
Perhaps the conjecture is false, but the counterexamples are large with very little structure. – Richard Stanley Mar 5 at 15:01
up vote 28 down vote accepted

(Migrated by request from the comments.)

Bruhn and Schaud's (2013) The journey of the union-closed sets conjecture provides a rather readable write-up. Particularly relevant is the section Obstacles to a proof; for example, you may check just after Conjecture 15 in which the authors ask (essentially) your question here:

"So, why then has the conjecture withstood more than twenty years of proof attempts?" (p. 14)

Bruhn and Schaud then list three possible techniques of proof, and go into a bit of detail around why they do not seem to work out; these techniques are: injections, local configurations, and averaging.

The paper also provides a few relevant re-formulations using, e.g., lattices, (maximal stable sets of bipartite) graphs, and the "Salzborn" formulation (p. 12). In each case, a re-formulation of the Frankl (or union-closed sets) conjecture brings corresponding ideas and techniques with varying potential; the authors of this particular survey do well by their promise early on:

"The focus of this survey is on the methods employed to attack the conjecture. Our treatment of the literature is therefore somewhat uneven. Whenever we can identify a technique that, to our eyes, seems interesting and potentially powerful we discuss it in greater detail" (p. 3).

share|cite|improve this answer
2  
I find the "injection" argument and obstruction intriguing: There cannot be any singletons $\{x\}$ in a family violating the conjecture, as the map $S \to S \cup \{x\}$ is injective (hence $x$ lives in half the sets). There cannot be any two-element sets $\{x,y\}$ by a similar argument. But the argument breaks down for sizes $k \geq 3$. – usul Mar 5 at 17:45

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.