49

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 ~$40$ 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?

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 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 05 '16 at 02:49
  • 11
    Perhaps the conjecture is false, but the counterexamples are large with very little structure. – Richard Stanley Mar 05 '16 at 15:01
  • 2
    Apparently there are problems with argument in the preprint you just linked to. See for instance https://mathstodon.xyz/@tao/109829637016032856 – Sam Hopkins Feb 08 '23 at 16:55
  • @SamHopkins: Thanks, I was unaware of the problems. I deleted the reference. – Joseph O'Rourke Feb 08 '23 at 17:16
  • Your formulation of PF's conjecture is a mess. Fortunately, the link that you've provided, https://en.wikipedia.org/wiki/Union-closed_sets_conjecture, is fine. – Wlod AA Feb 08 '23 at 22:56

1 Answers1

33

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

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