46
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ @BenjaminDickman: This is an entirely apropos answer, and if you reformulate it as an explicit answer, I will accept it. Thanks! $\endgroup$ – Joseph O'Rourke Mar 5 '16 at 2:49
  • 9
    $\begingroup$ Perhaps the conjecture is false, but the counterexamples are large with very little structure. $\endgroup$ – Richard Stanley Mar 5 '16 at 15:01
30
$\begingroup$

(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).

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – usul Mar 5 '16 at 17:45
  • 1
    $\begingroup$ Link appears to be broken. Is this the same as arxiv.org/abs/1309.3297 ? $\endgroup$ – Yemon Choi Apr 2 '18 at 18:31
  • $\begingroup$ @YemonChoi Yes: That is the same paper (and all page numbers correctly correspond). I've altered the link; thanks! $\endgroup$ – Benjamin Dickman Apr 2 '18 at 18:56

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.