co.combinatoricshypergraph
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?
Here is a nice example due to Bjorn Poonen, which I have taken from this survey paper of Bruhn and Schaudt. It is motivated by the following observations. Let $\mathcal{A}$ be a union-closed family. Call an element $x$ abundant if $x$ is contained in at least half of the members of $\mathcal{A}$.
Observation. If $\mathcal{A}$ contains a singleton $\{x\}$, then $x$ is abundant.
Proof. Partition $\mathcal{A}$ as $\mathcal{A}_x$ and $\overline{A}_x$ where $\mathcal{A}_x$ consists of the members of $\mathcal{A}$ containing $x$ and $\overline{A}_x$ are the members of $\mathcal{A}$ not containing $x$. Since $\{x\} \in \mathcal{A}$ and $\mathcal{A}$ is union-closed, the map $S \mapsto S \cup \{x\}$ is an injection from $\overline{A}_x$ to $\mathcal{A}_x$. Thus, $|\overline{A}_x| \leq |\mathcal{A}_x|$, as required. $\square$
Similarly, we also have the following.
Observation. If $\mathcal{A}$ contains a $2$-set $\{x,y\}$, then $x$ or $y$ is abundant.
This might lead one to conjecture the following false strengthening of Frankl's Union-closed Conjecture.
False Strengthening. Let $S$ be a non-empty member of $\mathcal{A}$ with the smallest number of elements. Then $S$ contains an abundant element.
Disproof. For two families $\mathcal{A}$ and $\mathcal{B}$ we let $$ \mathcal{A} \uplus \mathcal{B}=\{S \cup T: S \in \mathcal{A}, T \in \mathcal{B}\}. $$
Fix $k \geq 3$ and for each $i \in [k]$ define $$ \mathcal{B}^i=\{[k+1,3k] \setminus \{2i+k-1\}, [k+1,3k] \setminus \{2i+k\}\}. $$
Finally, define $$ \mathcal{A}^k=\{[k]\} \cup \bigcup_{i=1}^k(\{\emptyset, \{i\}, [k]\} \uplus \mathcal{B}^i) \cup (2^{[k]} \uplus [k+1,3k]). $$
It is easy to check that $\mathcal{A}^k$ is union-closed and that $[k]$ is the unique smallest set in $\mathcal{A}^k$. However, $|\mathcal{A}^k|=1+6k+2^k$ and each $i \in [k]$ is contained in only $1+(2k+2)+2^{k-1}$ members of $\mathcal{A}^k$. Thus, no element of $[k]$ is abundant. $\square$
This example highlights one of the obstacles in proving the Union-closed Conjecture; it is difficult to predict where abundant elements will be.
In a somewhat different direction from Alireza: the conjecture is true for a large family of groups, including all abelian groups and many supersolvable groups.
Let me start with the abelian case. Pick an element $g$ of highest possible prime-power order in an abelian group $G$. Then $\langle g \rangle$ has a complement: that is, there is a subgroup $K$ such that $K \langle g \rangle = G$ and $K \cap \langle g \rangle = 0$. In particular, $K \cong G / \langle g \rangle $ by the Isomorphism Theorems, and for any subgroup $X$ with $\langle g \rangle \subseteq X$ there is a corresponding subgroup $X \cap K$ which does not contain $\langle g \rangle$.
In fact, the same argument applies to any $G$ and prime-power order element $g$ if 1) $g$ generates a normal subgroup, and 2) we can find a complement $K$ to $\langle g \rangle$ in G. In this situation, $[\langle g \rangle, G] \cong [1,K]$.
(Edit: deleted discussion of supersolvable groups, which is irrelevant in light of update below.)
UPDATE: The conjecture is true for all finite solvable groups.
Proof: Let $G$ be a solvable group. Then $G$ has a normal subgroup $N$ of prime index, and some element of prime-power order $g \notin N$. Since $N$ is maximal in $G$, we have $\langle g,N \rangle = G$, and since $N$ is normal we have $\langle g,N \rangle = \langle g \rangle N$. Then by Dedekind's identity, we get that $\langle g \rangle (H \cap N) = H \cap G = H$ for any $H$ containing $\langle g \rangle$.
The last tells us that the map from the interval $[\langle g \rangle,G] \rightarrow [1,N]$ given by $H \mapsto H \cap N$ is an injection. Since $N$ doesn't contain $g$, we get the conjectured statement. $\square$
Indeed, the above works whenever $G$ has a maximal normal subgroup of prime index. (E.g., for symmetric groups.)
(Thanks to John Shareshian for several useful comments and discussion.)
UPDATE 2: By combining my argument for solvable groups with Alireza's argument for (certain) finite simple groups, we can prove the conjecture for all groups having a quotient satisfying a certain condition. This very likely holds for all finite groups, but as I'll explain, a little bit of work remains on the group theory side.
Theorem 1: If $G$ is a finite group with a normal subgroup $N$ such that $G/N$ is generated by (at most) two elements of prime power order, then $G$ satisfies the Frankl condition.
Proof: A routine argument shows that we can pick $g,h \in G$ of prime power order such that $g$ and $h$ project in the quotient to generators of $G/N$. (If $G/N$ is cyclic, assume $g=h$.) Let $K = \langle g, h \rangle$, and notice that $KN = \langle N, g, h\rangle = G$.
Then wlog there are at least as many subgroups containing $h$ as containing $g$ (else switch $h$ and $g$). This gives an injection $\varphi_1$ from the set of subgroups containing $g$ but not $h$ to the set of subgroups containing $h$ but not $g$.
Moreover, if $H$ is a subgroup containing both $h$ and $g$, then $H \supseteq K$. It then follows from the Dedekind identity that $K (H \cap N) = H \cap KN = H$, hence the map $\varphi_2$ sending $H \mapsto H \cap N$ is an injection from $[K,G] \rightarrow [1,N]$.
Since the intervals $[\langle h \rangle, G]$ and $[1,N]$ are disjoint, combining the two maps gives an injection from $[\langle g \rangle, G]$ to its complement, and we see the Frankl condition to hold. $\square$
Remark 1: The solvable case (above) is the case when $G/N$ is cyclic -- here, $K = \langle g,h \rangle = K$. The case where $N=1$ solved by Alireza has $K = G$, in which case we map $G$ to $1$ and all other subgroups containing $g$ to a subgroup containing $h$.
Remark 2: The proof has a particularly pleasing explanation if we can take $g$ and $h$ to be conjugate. In this case, the intervals $[\langle g \rangle, G]$ and $[\langle h \rangle, G]$ are isomorphic lattices, with the isomorphism given by conjugation of subgroups. As we shall see below, this stronger conjugacy condition often does seem to occur.
Now, if $N$ is a maximal normal subgroup, then $G/N$ is simple, so to verify the conjecture for all groups it suffices to verify that every finite simple group is generated by two elements of prime-power order. I managed to put together the following from results in the literature:
Theorem 2: All but possibly finite many of the finite simple groups are generated by two elements of prime power order. The two elements may be taken to be conjugate. Any exceptions are classical groups.
The conjugacy part will come from the following lemma:
Lemma: If a finite simple group $G$ is generated by $x$ and $g$, where $x$ has order 2, then $G = \langle g, g^x \rangle$.
Proof (of Lemma): Suppose not, and let $H = \langle g, g^x \rangle$. Then $H$ is easily seen to permute with $\langle x \rangle$, hence $H$ has index 2, contradicting simplicity of $G$. $\square$
We say a group is $(2,q)$-generated if it is generated by an element of order 2, together with an element of order $q$. To prove Theorem 2, it suffices to show that (modulo possible exceptions) every finite simple group is (2,$q$)-generated for some prime-power $q$. We go through the list of groups from the Classification Theorem.
Many finite simple groups are known to be (2,3)-generated, and this condition has been well-studied. ((2,3)-generated groups can be represented as quotients of $PSL_2(\mathbb{Z})$, explaining the high level of interest in this condition.)
A. Liebeck and Shalev in "Classical groups, probabilistic methods, and the (2,3)-generation problem" showed that, excluding the groups $PSp_4(q)$, all but finitely many of the classical groups are (2,3)-generated.
B. Di Martino and Cazzola in "$(2,3)$-generation of $PSp(4,q),\ q=p^n,\ p\neq 2,3$" showed that $PSp_4(q)$ is (2,3)-generated, except in characteristic 2 or 3.
C. Malle, and Lübeck and Malle in a series of papers culminating in "(2,3)-generation of exceptional groups" show that all exceptional groups of Lie type are (2,3)-generated, except for the Suzuki groups and $G(2)' \cong PSU_2(9)$.
(Nick Gill also referenced this paper in his comment to Alireza's answer.)
D. Woldar in "On Hurwitz generation and genus actions of sporadic groups" showed the sporadic groups to be (2,3)-generated, except for $M_{11}$, $M_{22}$, $M_{23}$, and $McL$
E. GA Miller proved in 1901 that the alternating groups $A_n$ are (2,3)-generated for $n \neq 6,7,8$.
$A_6, A_7, A_8$ are easily verified to all be (2,5)-generated.
Liebeck and Shalev in Proposition 6.4 of the same paper referenced above show that all but finitely many of the groups $PSp_4(2^n)$ and $PSp_4(3^n)$ are (2,5)-generated.
Suzuki, in his original paper on the topic, showed that the Suzuki groups are (2,4)-generated.
For the remaining sporadics, $M_{11}$ and $M_{22}$ are (2,4)-generated, while $M_{23}$ and $McL$ are (2,5)-generated. (The best place I found to read about this is in a series of papers on symmetric genus of groups. These papers are by various authors, frequently including Conder and Woldar.)
Theorem 2 follows from the list above, together with the Classification of Finite Simple Groups.
There is very likely a nicer approach to some of the simple group stuff than what I do above -- I'm far from an expert. (Maybe one of the real experts around here can remove the possible exceptions from the statement!!)
I found the slides linked here of Maxim Vsemirnov on (2,3)-generated groups very helpful for understanding the exceptions to (2,3)-generation.
In particular, he has a list of groups that are not (2,3)-generated on page 15 (which he conjectures to be complete). I've verified with GAP that all are (2,$q$)-generated for some prime $q$, except for the PSp's and $\Omega_8^+(2), P\Omega_8^+(3)$.
Corollary: The conjecture holds for any $G$ with a maximal normal subgroup $N$ such that $G/N$ is not one of the exceptional (small) classical groups in Theorem 2.
Best Answer
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 erdos-ko-rado 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.
UPDATE MAY 2016: I've had cause to look into the provenance more. Apparently Frankl asked the question in '79, and talked about it with several people, but never published it. The first appearance in print arises from a problem session at the 1984 conference on Graphs and Order in Banff, where Duffus presented several forms of the problem. The conference proceedings are in the volume "Graphs and order". From the summary there, Duffus appears to have already known several partial results on the conjecture that were only published much later.
See also the recent survey article of Bruhn and Schaudt.