# Why is the Frankl conjecture hard?

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?

• @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 '16 at 2:49
• Perhaps the conjecture is false, but the counterexamples are large with very little structure. – Richard Stanley Mar 5 '16 at 15:01

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

• 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 '16 at 17:45
• Link appears to be broken. Is this the same as arxiv.org/abs/1309.3297 ? – Yemon Choi Apr 2 '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 2 '18 at 18:56