\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm, amssymb,amsmath} \usepackage{mathrsfs} \usepackage{xcolor} \usepackage{empheq} \usepackage{lscape} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\boxedeq}[1]{\begin{empheq}[box={\fboxsep=6pt\fbox}]{align*}#1\end{empheq}} \title{New Conjectures For Union-Closed Families} \author{Jonad Pulaj \\ \small Dept. of Optimization\\[-0.8ex] \small Zuse Institute Berlin\\[-0.8ex] \small Takusstra\ss e 7\\[-0.8ex] \small 14195 Berlin\\[-0.8ex] \small Germany\\ \small\tt pulaj@zib.de\\ \and Annie Raymond\\ \small Dept. of Mathematics\\[-0.8ex] \small University of Washington\\[-0.8ex] \small Box 354350\\[-0.8ex] \small Seattle, WA 98195\\[-0.8ex] \small United States\\ \small\tt raymonda@uw.edu\\ \and Dirk Theis\\ \small Inst. of Computer Science\\[-0.8ex] \small University of Tartu\\[-0.8ex] \small Juhan Liivi 2\\[-0.8ex] \small 50409 Tartu\\[-0.8ex] \small Estonia\\ \small\tt dirk.theis@ut.ee } \date{\dateline{November 30, 2015}{July 26, 2016}\\ \small Mathematics Subject Classifications: 05D05, 90C27} \begin{document} \maketitle \begin{abstract} The Frankl conjecture, also known as the union-closed sets conjecture, states that in any finite non-empty union-closed family, there exists an element in at least half of the sets. From an optimization point of view, one could instead prove that $2a$ is an upper bound to the number of sets in a union-closed family on a ground set of $n$ elements where each element is in at most $a$ sets for all $a,n\in \mathbb{N}^+$. Similarly, one could prove that the minimum number of sets containing the most frequent element in a (non-empty) union-closed family with $m$ sets and $n$ elements is at least $\frac{m}{2}$ for any $m,n\in \mathbb{N}^+$. Formulating these problems as integer programs, we observe that the optimal values we computed do not vary with $n$. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having wide-reaching implications if proven true. Finally, we prove special cases of the new conjectures and discuss possible approaches to solve them completely. \end{abstract} \section{Introduction} The union-closed sets conjecture is a celebrated open problem in combinatorics which was popularized by Frankl in the late 1970's \cite{Frankl1983}, and is thus often referred to as the Frankl conjecture. Before stating the conjecture, we need a few definitions. Throughout this paper, we think of a \emph{family of sets} or \emph{set system} $\mathcal{F}=(E(\mathcal{F}), \mathcal{S}(\mathcal{F}))$ as being a collection $\mathcal{S}(\mathcal{F})$ of distinct sets $S$ such that every set $S\subseteq E(\mathcal{F})$ where $E(\mathcal{F})$ is the ground set of elements. In general, we let $E(\mathcal{F})=\{1,\ldots, n\}=:[n]$. A family of sets is said to be \emph{union-closed} if and only if the union of two sets of the family is also a set of the family. \begin{conjecture}[Frankl, 1979]\label{franklconj} In a union-closed family $\mathcal{F}$ such that $\mathcal{S}(\mathcal{F})\neq \{\emptyset\}$, there exists an element of $E(\mathcal{F})$ that is in at least half of the sets of $\mathcal{S}(\mathcal{F})$. \end{conjecture} Since 1979, the conjecture has attracted the attention of both lattice theorists as well as combinatorial probabilists, and, more recently, computer scientists. To the best of our knowledge, this is the first time the problem is investigated through combinatorial optimization. After defining a few more concepts, we give an overview of the literature and present our contributions. Let $m(\mathcal{F})$ and $n(\mathcal{F})$ be respectively the numbers of sets and elements of a family $\mathcal{F}$, i.e., $m(\mathcal{F})=|\mathcal{S}(\mathcal{F})|$ and $n(\mathcal{F})=|E(\mathcal{F})|$. Moreover, let $m_e(\mathcal{F})$ be the number of sets in $\mathcal{F}$ containing some element $e\in E(\mathcal{F})$. Let the \emph{degree} of $\mathcal{F}$, denoted by $a(\mathcal{F})$, be the maximum number of sets in $\mathcal{F}$ containing any element of $E(\mathcal{F})$, that is, $a(\mathcal{F})=\max_{e\in E(\mathcal{F})} m_e(\mathcal{F})$. Let $e^*(\mathcal{F})$ be an arbitrary element of maximum degree, i.e., any of possibly many elements in $E(\mathcal{F})$ contained in $a(\mathcal{F})$ sets. For example, if $\mathcal{F}$ is such that $E(\mathcal{F})=[3]$ and $\mathcal{S}(\mathcal{F})=\{\{1,2,3\},\{1,2\},\{1,3\},\emptyset \}$, then $\mathcal{F}$ is union-closed, $m(\mathcal{F})=4$, $n(\mathcal{F})=3$, $m_1(\mathcal{F})=3$, $m_2(\mathcal{F})=2$, $m_3(\mathcal{F})=2$, $a(\mathcal{F})=3$ and $e^*(\mathcal{F})=1$. Since $\frac{3}{4} \geq \frac{1}{2}$, the Frankl conjecture holds for $\mathcal{F}$. \subsection{A bit of history} Conjecture \ref{franklconj} is known to hold for certain specific families. For example, it has long been known that the conjecture is trivially true for any family $\mathcal{F}$ containing a singleton or a pair, i.e., when there exists $S\in \mathcal{S}(\mathcal{F})$ such that $|S|=1$ or $2$, or when the average size of the sets, $\frac{1}{m(\mathcal{F})}\sum_{S\in \mathcal{S}({\mathcal{F}})} |S|$, is greater or equal to $\frac{n(\mathcal{F})}{2}$. Another early result is the following: \begin{theorem}[Roberts, 1992]\label{Roberts1992} The inequality $m(\mathcal{F})<4n(\mathcal{F})-1$ holds for any union-closed family $\mathcal{F}$ that is a minimum counterexample to the Frankl conjecture. \end{theorem} The above results and a few others allowed the conjecture to be proven for increasing values of $m$ and $n$ over time (\cite{SarvateRenaud1989}, \cite{SarvateRenaud1990}, \cite{LoFaro19942}, \cite{Poonen1992}, \cite{GaoYu1998}, \cite{Roberts1992}). The current status is as follows: \begin{theorem}[Roberts and Simpson, 2010] The Frankl conjecture is true for any family $\mathcal{F}$ with $m(\mathcal{F})\leq 46$. \end{theorem} \begin{theorem}[Bo\v{s}njak and Markovi\'c, 2008] The Frankl conjecture is true for any family $\mathcal{F}$ with $n(\mathcal{F})\leq 11$. \end{theorem} More recently, Vu\v{c}kovi\'c and \v{Z}ivkovi\'c announced the following result which is still unpublished. \begin{theorem}[Vu\v{c}kovi\'c and \v{Z}ivkovi\'c, 2012] The Frankl conjecture is true for any family $\mathcal{F}$ such that $n(\mathcal{F})\leq 12$ and $m(\mathcal{F})\leq 50$. \end{theorem} Thus the conjecture is still open for $m(\mathcal{F})\geq 51$ and $n(\mathcal{F})\geq 13$. A breakthrough in the field is the following result from Reimer \cite{Reimer2003}. \begin{theorem}\label{ReimerThm} For any union-closed family $\mathcal{F}$, $\frac{1}{m(\mathcal{F})} \sum_{S\in \mathcal{S}(\mathcal{F})} |S|$, the average size of sets, is at least $\frac{1}{2}\log_2(m(\mathcal{F}))$. \end{theorem} We now turn our attention to three important results which are quite useful for the purposes of this paper. Firstly, Balla, Bollob\'as and Eccles recently proved that the Frankl conjecture holds for families $\mathcal{F}$ containing at least $\frac{2}{3}$ of the sets in the power set of $n(\mathcal{F})$. \begin{theorem}[Balla, Bollob\'as \& Eccles, 2013]\label{BBE} The union-closed conjecture holds for any family $\mathcal{F}$ where $m(\mathcal{F}) \geq \frac{2}{3} 2^{n(\mathcal{F})}$. \end{theorem} Even more recently, Eccles strengthened this result by proving a stability version in \cite{Eccles2015}. Secondly, instead of proving the Frankl conjecture, one could instead try to prove that any union-closed family contains an element present in at least some fraction of the sets, just as Knill did in the following theorem. \begin{theorem}[Knill, 1994]\label{knillaverage} In any union-closed family $\mathcal{F}$, there always exists an element present in at least $\frac{m(\mathcal{F})-1}{\log_2 m(\mathcal{F})}$ sets, that is, $a(\mathcal{F}) \geq \frac{m(\mathcal{F})-1}{\log_2 m(\mathcal{F})}$. \end{theorem} W\'ojcik improved this result slightly in \cite{Wojcik1999}, but, amazingly, still no constant fraction is known. Thirdly, Bruhn and Schaudt in \cite{BruhnSchaudt2014} observed the following corollary to Reimer's theorem and the bounds from \cite{VuckovicZivkovic2012}. \begin{theorem}[Bruhn \& Schaudt, 2013] \label{BSsurvey} Let $\mathcal{F}$ be any union-closed family $\mathcal{F}$ such that $2^{n(\mathcal{F})-1} < m(\mathcal{F}) \leq 2^{n(\mathcal{F})}$. Then $a(\mathcal{F}) \geq \frac{6}{13}\cdot m(\mathcal{F})$, i.e., there exists an element in a least $\frac{6}{13}$ of the sets of the family. \end{theorem} Many other results have been discovered throughout the years. For a more complete history of the problem, we refer the reader to the following excellent survey \cite{BruhnSchaudt2014}. Finally, we note that Timothy Gowers recently led a polymath project, FUNC, on this topic. \subsection{Our contributions} In this paper, we examine the Frankl conjecture through a different lens by viewing it as an optimization problem. Indeed, we can rewrite Conjecture \ref{franklconj} either as a maximization or minimization problem, depending on whether we fix $m(\mathcal{F})$ or $a(\mathcal{F})$. \begin{conjecture}[Maximization Version]\label{maxconj} For any positive integer $a$, let $$\mathscr{F}(a)=\{\mathcal{F}|\mathcal{F} \textup{ is a union-closed family}, \mathcal{S}(\mathcal{F})\neq \emptyset \textup{ and } a(\mathcal{F})\leq a\}.$$ Then $\max_{\mathcal{F}\in \mathscr{F}(a)} m(\mathcal{F})\leq 2a$ for all $a\in \mathbb{N}^+$. \end{conjecture} \begin{conjecture}[Minimization Version]\label{minconj} For any positive integer $m$, let $$\mathscr{G}(m)=\{\mathcal{F}|\mathcal{F} \textup{ is a union-closed family}, \mathcal{S}(\mathcal{F}) \neq \emptyset \textup{ and } m(\mathcal{F})=m\}.$$ Then $\min_{\mathcal{F}\in \mathscr{G}(m)} a(\mathcal{F}) \geq \frac{m}{2}$ for all $m\in \mathbb{N}^+$. \end{conjecture} Note that the conjectures \ref{franklconj}, \ref{maxconj} and \ref{minconj} are equivalent since there exists a counterexample to the original Frankl conjecture if and only if there exists a union-closed family $\mathcal{F}$ such that $m(\mathcal{F})>0$ and $a(\mathcal{F})<\frac{m(\mathcal{F})}{2}$. In Section \ref{sec:model}, we model the optimization versions of the Frankl conjecture as integer programs for a fixed $n$ (the number of elements in $E(\mathcal{F})$ for all families $\mathcal{F}$ considered). In Proposition~\ref{fgproperties}, we discuss some of the properties of the optimal values of said programs. Then in Section \ref{sec:compconj}, we present computational results for the models. We observe that the optimal values we computed do not vary as $n$ increases, i.e., \begin{align*} \max_{\substack{\mathcal{F}\in \mathscr{F}(a):\\ n(\mathcal{F})=n}} m(\mathcal{F})= \max_{\substack{\mathcal{F}\in \mathscr{F}(a):\\ n(\mathcal{F})=n+1}} m(\mathcal{F}) \end{align*} and \begin{align*} \min_{\substack{\mathcal{F}\in \mathscr{G}(m):\\ n(\mathcal{F})=n}} a(\mathcal{F})=\min_{\substack{\mathcal{F}\in \mathscr{G}(m):\\ n(\mathcal{F})=n+1}} a(\mathcal{F}) \end{align*} for $n \geq \log_2(a)$. We did not expect this and this is not necessary for the Frankl conjecture to hold. We formally present these two observations as conjectures and prove that they are equivalent. However, these new conjectures do not imply the Frankl conjecture, and conversely, the Frankl conjecture does not imply these two new conjectures. Still, in Section \ref{sec:consequences}, we discuss some of the important implications the new conjectures have on the Frankl conjecture. Notably, proving these conjectures would prove Conjecture \ref{franklconj} for infinitely many values of $|\mathcal{S}(\mathcal{F})|=m$. Moreover, their proof would yield that there always exists an element in $\frac{6}{13}$ of the sets of a union-closed family, and would thus achieve the first known constant bound for the percentage of sets containing some element in any union-closed family. Finally, in Section \ref{sec:newresults}, we prove a restricted version of the new conjectures using an observation of Falgas-Ravry in \cite{FalgasRavry2011} and discuss the importance of twin sets, which we define as sets that differ only in one element. \section{The Frankl Integer Problems and Two New Conjectures}\label{sec2} \subsection{Modeling the Frankl optimization problems}\label{sec:model} For any positive integers $a, n$, let $$\mathscr{F}(n,a)=\{\mathcal{F}\in \mathscr{F}(a)|n(\mathcal{F})=n\}.$$ Then proving that $\max_{\mathcal{F}\in \mathscr{F}(n,a)} m(\mathcal{F}) \leq 2a$ for all possible $n, a$ would prove Conjecture \ref{maxconj} (and thus the original conjecture). Fix $n, a$, and let $f(n,a)=\max_{\mathcal{F} \in \mathscr{F}(n,a)} m(\mathcal{F})$. Then we can find $f(n,a)$ by solving the following integer program \boxedeq{% f(n,a)= \max & \sum_{S\in \mathcal{S}_n} x_S && \\ \textup{such that } & x_U+x_T \leq 1+x_S \quad \quad\quad \quad\quad \quad \hspace{0.05cm} \forall T\cup U = S \in \mathcal{S}_n \\ & \sum_{S\in \mathcal{S}_n: e\in S} x_S \leq a \quad \quad\quad \quad\quad \quad \quad \forall e\in [n] \\ & x_S \in \{0,1\}\quad \quad\quad \quad\quad\quad\quad\quad \quad \hspace{0.1cm}\forall S\in \mathcal{S}_n, } where $\mathcal{S}_n$ is the power set of $[n]$, and the variable $x_S$ for any set $S\in \mathcal{S}_n$ is $1$ if $S$ is in the family, and $0$ otherwise. Thus, we maximize the number of sets while ensuring the family is union-closed (through the first constraint) and that $a(\mathcal{F}) \leq a$ holds (through the second constraint), i.e., we calculate $f(n,a)$. Similarly, let $$\mathscr{G}(n,m)=\{\mathcal{F}\in \mathscr{G}(m)|n(\mathcal{F})=n\}$$ for any positive integers $m$ and large enough $n$. Then, it is easy to see that proving that $\min_{\mathcal{F} \in \mathscr{G}(n,m)} a(\mathcal{F}) \geq \frac{m}{2}$ for all large enough $n$ and $m$ would prove Conjecture \ref{minconj}. Fix $n, m$, and let $g(n,m)=\min_{\mathcal{F}\in \mathscr{G}(n,m)} a(\mathcal{F})$ for $m \geq 2$. Then we can find $g(n,m)$ by solving the following integer program \boxedeq{% g(n,m) = \min & \sum_{S\in \mathcal{S}_n: 1\in S} x_S \\ \textup{such that } & x_U+x_T \leq 1+x_S \hspace{0.2cm} \quad \quad \quad \quad \quad \forall T\cup U = S \in \mathcal{S}_n \\ & \sum_{S\in \mathcal{S}_n: i\in S} x_S \geq \sum_{S\in \mathcal{S}_n: j\in S} x_S \quad \quad \forall 1\leq i\leq j\leq n\\ & \sum_{S\in \mathcal{S}_n} x_S = m \\ & x_S \in \{0,1\} \hspace{0.25cm}\quad\quad\quad\quad\quad\quad\quad\quad \forall S\in \mathcal{S}_n, } where the variables $x_S$ are as before. The second constraint says that element $1$ is the element contained in the most number of sets in the family, so we are minimizing the maximum number of sets containing the most frequent element while enforcing that the family is union-closed (through the first constraint) and has $m$ sets (through the third constraint). Most work done on the Frankl conjecture has been from the $g(n,m)$ point of view, not $f(n,a)$. Moreover, in \cite{Renaud1991} and \cite{Renaud1995}, Renaud defined $\varphi(m)$ to be the minimum number of sets containing the most frequent element in a family among all union-closed families on $m$ sets. Some of the properties he proves for $\varphi(m)$ are not unlike those we will prove for $g(n,m)$. Note moreover that there are values of $a, m, n$ for which $f(n,a)$ and $g(n,m)$ have trivial solutions that do not interest us. For example, it is clear that $f(n,a)=2^n$ if $a\geq 2^{n-1}$. Indeed, the power set of $n$, $\mathcal{S}_n$, is union-closed, and there are $2^n$ sets in $\mathcal{S}_n$ where each element is in exactly $2^{n-1}$ sets. It is thus a trivially optimal solution for $f(n,a)$. It is also clear that $g(n,m)$ has trivially no solution if $m>2^n$. Indeed, even if we take all of the $2^n$ sets in $\mathcal{S}_n$, we would have less sets than the number of sets required by the program. We first study a few properties of the functions $f$ and $g$ for non-trivial values of $a, m, n$. \begin{proposition}\label{fgproperties} The following properties hold. \begin{enumerate} \item The function $f$ is non-decreasing in $n$, that is, $f(n,a) \leq f(n+1,a)$ for every $a, n \in \mathbb{N}^+$ such that $n \geq \lceil \log_2 a \rceil + 1$.\label{fnondecreasing} \item The function $g$ is non-increasing in $n$, that is, $g(n,m) \geq g(n+1,m)$ for every $m, n\in \mathbb{N}^+$ such that $n \geq \lceil \log_2 m \rceil$.\label{gnonincreasing} \item The function $f$ is strictly increasing in $a$, that is, $f(n,a) < f(n,a+1)$ for every $a, n\in \mathbb{N}^+$ such that $n > \lceil \log_2 a \rceil + 1$.\label{fstrict} \item The function $g$ is non-decreasing in $m$, that is, $g(n,m) \leq g(n,m+1)$ for every $m,n\in \mathbb{N}^+$ such that $n \geq \lceil \log_2 m \rceil$.\label{gnondecreasing} \item We have that $g(n,f(n,a)) = a$ for all $a, n\in \mathbb{N}^+$ such that $n > \lceil \log_2 a \rceil + 1$.\label{gfequal} \item We have that $f(n,g(n,m)) \geq m$ for all $m,n \in \mathbb{N^+}$ such that $n \geq \lceil \log_2 m \rceil$.\label{fggeq} \end{enumerate} \end{proposition} \proof \begin{enumerate} \item Fix $a, n$ and suppose $f(n,a) = m$. Take a family $\mathcal{F}$ that is optimal, i.e., a family $\mathcal{F}\in \mathscr{F}(n,a)$ such that $m(\mathcal{F})=m$. Add an element $n+1$ to the family such that this element is exactly in the same sets as some other element $e$ of the family. Then this augmented family is still union-closed, and every element of it is still in at most $a$ sets. Thus, $f(n+1,a) \geq m = f(n,a)$. \item Just as for (\ref{fnondecreasing}), we clone an element. \item Fix $a, n$ and suppose $f(n,a)=m$. Take a family $\mathcal{F}$ that is optimal (as before). Then add to this family one of the largest sets that is not already present in the family, i.e., a set in $\mathcal{S}_n\backslash \mathcal{S}(\mathcal{F})$ containing as many elements as possible. This is always possible if $f(n,a)<2^n$ (note that this is the case if $a<2^{n-1}$ since we cannot take all of $\mathcal{S}_n$ then). The new family we built has $m+1$ sets and is still union-closed since taking the union of any other set with the added set will give either the new set itself or a greater set (which is present in the family by construction). Moreover, every element in this new family is present in at most $a+1$ sets. Thus, $f(n,a+1)\geq m+1 = f(n,a) + 1$. \item Fix $m,n$ and suppose $g(n,m+1)=a$. Take a family $\mathcal{F}$ that is optimal (as before). Remove the smallest set of the family, i.e., one of the sets in $\mathcal{S}(\mathcal{F})$ with the least number of elements. The family is still union-closed since the set that was removed was not the union of any other two sets since they would have to be smaller. Moreover, this new family has $m$ sets and every element is still there at most $a$ times, so $g(n,m) \leq a=g(n,m+1)$. \item Fix $a, n$ and suppose that $f(n,a)=m$. Thus $m$ is the maximum number of sets in any union-closed family $\mathcal{F}$ on $n$ elements with $a(\mathcal{F})\leq a$. Because $m \leq 2^n$, $g(n,m)$ is feasible. Certainly, this implies that $g(n,m)=g(n,f(n,a)) \leq a$. Suppose that $g(n,f(n,a))=a' < a$. Then $f(n,a') \geq m$. Since we have already shown that the function $f$ strictly increases in $a$ when $n>\lceil \log_2 a \rceil +1$, this is a contradiction. \item Suppose that $g(n,m)=a$. Then $n \geq \lceil \log_2 m \rceil$, else $g(n,m)$ would be infeasible. Thus, the most frequent element in a union-closed family with $n$ elements and $m$ sets is present in a least $a$ sets. Certainly, this means that $f(n,a)=f(n,g(n,m))\geq m$. \end{enumerate} \qed \subsection{Computations and Conjectures}\label{sec:compconj} We computed $f(n,a)$ and $g(n,m)$ for different values with the mixed-integer commercial solver IBM ILOG CPLEX version 12.4. For the source code to generate the .lp files, see http://www.math.washington.edu/$\sim$raymonda/frankl.py. Table \ref{tablefg} contains some of the results we obtained. \begin{table}[h!] \caption{Values of $f(n,a)$ and $g(n,m)$ (respectively left and right)} \label{tablefg} \begin{center} \setlength{\tabcolsep}{2.6pt} \begin{tabular}{|l|cccccccc|} \hline $a\backslash n$ & 1 & 2 & 3 & 4 & 5& 6& 7& 8\\ \hline 1 & 2 & 2 & 2 & 2 & 2& 2& 2& 2\\ 2 & \textcolor{gray}{2} & 4 & 4 & 4& 4& 4& 4& 4\\ 3 & \textcolor{gray}{2}& \textcolor{gray}{4}& 5 & 5 & 5 & 5 & 5 & 5\\ 4 & \textcolor{gray}{2}& \textcolor{gray}{4}& 8& 8& 8& 8& 8& 8 \\ 5 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& 9& 9& 9& 9& 9\\ 6 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& 10& 10& 10& 10& 10 \\ 7 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& 12& 12& 12& 12& 12 \\ 8 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& 16& 16& 16& 16& 16 \\ 9 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 17& 17& 17& 17 \\ 10 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 18& 18& 18& 18 \\ 11 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 19& 19& 19& 19 \\ 12 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 21& 21& 21& 21 \\ 13 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 23& 23& 23& 23 \\ 14 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 25 & 25 & 25 & 25 \\ 15 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 27& 27& 27& 27 \\ 16 & \textcolor{gray}{2}& \textcolor{gray}{4}& \textcolor{gray}{8}& \textcolor{gray}{16}& 32& 32& 32& 32 \\ \hline \end{tabular} \quad \begin{tabular}{|l|cccccccc|} \hline $m\backslash n$ & 1 & 2 & 3 & 4 & 5& 6& 7& 8 \\ \hline & & & & & & & & \\ 2 & 1& 1 &1 & 1& 1& 1& 1& 1 \\ 3 &\textcolor{gray}{-} & 2& 2 & 2 & 2 & 2 & 2 & 2 \\ 4 &\textcolor{gray}{-} & 2& 2& 2& 2& 2& 2& 2\\ 5 &\textcolor{gray}{-} &\textcolor{gray}{-} &3 & 3& 3& 3& 3& 3\\ 6 &\textcolor{gray}{-} &\textcolor{gray}{-} & 4& 4& 4& 4& 4& 4 \\ 7 &\textcolor{gray}{-} &\textcolor{gray}{-} & 4& 4&4& 4& 4& 4\\ 8 &\textcolor{gray}{-} &\textcolor{gray}{-} & 4& 4& 4& 4& 4& 4\\ 9 &\textcolor{gray}{-} &\textcolor{gray}{-} &\textcolor{gray}{-} & 5& 5& 5& 5& 5\\ 10 &\textcolor{gray}{-} &\textcolor{gray}{-} &\textcolor{gray}{-} & 6& 6& 6& 6& 6\\ 11 &\textcolor{gray}{-} &\textcolor{gray}{-} & \textcolor{gray}{-}& 7& 7& 7& 7& 7\\ 12 &\textcolor{gray}{-} &\textcolor{gray}{-} & \textcolor{gray}{-}& 7& 7& 7& 7& 7\\ 13 &\textcolor{gray}{-} &\textcolor{gray}{-} & \textcolor{gray}{-}& 8& 8& 8& 8& 8\\ 14 &\textcolor{gray}{-} &\textcolor{gray}{-} & \textcolor{gray}{-}& 8& 8 & 8 & 8 & 8\\ 15 &\textcolor{gray}{-} &\textcolor{gray}{-} & \textcolor{gray}{-}& 8& 8& 8& 8& 8\\ 16 &\textcolor{gray}{-} &\textcolor{gray}{-} & \textcolor{gray}{-}& 8& 8& 8& 8& 8\\ \hline \end{tabular} \end{center} \end{table} A clear pattern emerges: For any $n\geq\lceil \log_2 a \rceil + 1$, that is, for any non-trivial value of $n$ when $a$ is fixed, $f(n,a)$ takes the same value as $n$ increases. Similarly, for any $n \geq \lceil \log_2 m \rceil$, that is, for any non-trivial value of $n$ when $m$ is fixed, $g(n,m)$ takes the same value as $n$ increases. To the best of our knowledge, this has never been observed before. We formulate these observations as conjectures. \begin{conjecture}[$f$-conjecture]\label{fconjecture} Fix $a\in \mathbb{N}^+$. Then $f(n,a) = f(n+1,a)$ for every $n\in \mathbb{N}^+$ such that $n \geq \lceil \log_2 a \rceil + 1$. \end{conjecture} \begin{conjecture}[$g$-conjecture]\label{gconjecture} Fix $m\in \mathbb{N}^+$. Then $g(n,m) = g(n+1,m)$ for every $n\in \mathbb{N}^+$ such that $n \geq \lceil \log_2 m \rceil $. \end{conjecture} We checked these conjectures computationally up to $n=9$ for all non-trivial values of $a$ for $f(n,a)$ and up to $n=8$ for all non-trivial values of $m$ for $g(n,m)$ (see Appendix). We first show that these two conjectures are equivalent. \begin{theorem}\label{conjecturesequivalent} We have that $f(n,a)=f(n+1,a)$ for every $a,n\in \mathbb{N}^+$ such that $n \geq \lceil \log_2 a \rceil + 1$ if and only if $g(n',m)=g(n'+1,m)$ for every $m,n' \in \mathbb{N}^+$, $m \geq 2$ such that $n' \geq \lceil \log_2 m \rceil$. \end{theorem} \proof Suppose that $g(n',m)=g(n'+1,m)$ for every $m,n' \in \mathbb{N}^+$, $m \geq 2$ such that $n' \geq \lceil \log_2 m \rceil$. Pick an arbitrary $a\in \mathbb{N}^+$ and choose any $n\in \mathbb{N}^+$ such that $n\geq \lceil \log_2 a \rceil + 1$. By Proposition~\ref{fgproperties}(\ref{gfequal}), we know that there exists $m$ such that $g(n,m)=a$, namely $m:=f(n,a)$. Let $m^*$ be the greatest number for which $g(n,m^*)=a$. By definition, it follows that $f(n,a) \leq m^*$. Moreover, $f(n,a) \geq m^*$ since $f(n,g(n,m^*)) \geq m^*$ by Proposition~\ref{fgproperties}(\ref{fggeq}). Thus, $f(n,a) = m^*$ for any $n\geq \lceil \log_2 a \rceil + 1$. Suppose that $f(n,a)=f(n+1,a)$ for every $a,n\in \mathbb{N}^+$ such that $n \geq \lceil \log_2 a \rceil + 1$. Pick an arbitrary $m\geq 2$, and choose any $n'\geq \lceil \log_2 m \rceil$. If there exists $a$ such that $f(n',a)=m$, then, by Proposition~\ref{fgproperties}(\ref{gfequal}), $g(n',m)=g(n',f(n',a))=a$. Therefore, $g(n',m)=g(n'+1,m)$ for all $n' \geq \lceil \log_2 m \rceil$. If there does not exists $a$ such that $f(n',a)=m$, then, by Proposition~\ref{fgproperties}(\ref{fggeq}), $f(n',g(n',m))=m+b$, $b>0$, and $g(n',m)=g(n',m+b)$. Then $g(n', m+b)=:a'$ for all $n'$ since $f(n'(g(n', m+b))=m+b$, which brings us back to the first case. Therefore, $g(n',m)=g(n',m'+b)=a'$ for all $n'\geq \lceil \log_2 m \rceil$. \qed The two conjectures are thus equivalent: proving one would prove the other. Another way to view the $f$-conjecture is as follows: to construct an optimal solution for $f(n,a)$, first construct an optimal solution for $f(\lceil \log_2 a \rceil + 1, a)$, and make $n-\lceil \log_2 a \rceil -1$ copies of some element, i.e., put these new elements in the same sets as the original element, or if you prefer, put these new elements in none of the sets. If the $f$-conjecture is true, such families would be optimal for $f(n,a)$. Note though that there can also be other optimal families: the conjecture simply states that families obtained through this process are optimal. The same idea can be applied to the $g$-conjecture. Note that these conjectures are different from the Frankl conjecture. For one thing, even if the $f$- and $g$-conjectures hold, one would still need to show that $f(\lceil \log_2 a \rceil + 1,a) \leq 2a$ for every $a$ or that $g(\lceil \log_2 m \rceil,m) \geq \frac{m}{2}$ for all $m$ to prove the Frankl conjecture; therefore the $f$- and $g$-conjectures do not imply the Frankl conjecture. Moreover, the Frankl conjecture does not immediately imply the $f$- and $g$-conjectures. Certainly, if the Frankl conjecture is true, then \begin{align*} \max_{n} f(n,a) \leq 2a \end{align*} for all $a\in \mathbb{N}^+$, else the Frankl conjecture would not be true; however, how the function $f(n,a)$ behaves for different $n$ for a fixed $a$ is irrelevant. Certainly, one can easily observe that the Frankl conjecture implies that the function $f$ has to stabilize at some point as $n$ increases since, by Proposition~\ref{fgproperties}(\ref{fnondecreasing}), $f(n,a)\leq f(n+1,a)$, and since $f(n,a)\in \mathbb{N}$ by definition. However, the Frankl conjecture does not imply that the function $f$ should be stable immediately as $n\geq \lceil \log_2 a \rceil + 1$, that is, as soon as there are enough elements for there to be at least $a$ sets containing an element $e$. Similarly, if the Frankl conjecture is true, then \begin{align*} \min_{n\geq \lceil \log_2 m \rceil} g(n,m) \geq\frac{m}{2} \end{align*} for all $m\in \mathbb{N}^+$, and so again one can observe that the $g$ function has to stabilize at some point as $n$ increases since we show in Proposition~\ref{fgproperties}(\ref{gnonincreasing}) that $g(n,m) \geq g(n+1,m)$. But again, the Frankl conjecture does not imply that the function $g$ has to stabilize immediately when $n \geq \lceil \log_2 m\rceil$, that is, as soon as there are enough elements for there to be at least $m$ sets in the power set of $n$. Therefore, the $f$- and $g$-conjectures do not imply the Frankl conjecture and the latter does not imply the former two either. Still, proving the $f$- and $g$-conjectures would have wide-reaching implications for the Frankl conjecture. \subsection{Consequences of the $f$- and $g$-conjectures on the Frankl conjecture}\label{sec:consequences} Note that if the $f$- and $g$-conjectures are true, then proving the union-closed sets conjecture for \emph{large} families, i.e., families such that $m\geq 2^{n-1}+1$ would be enough to prove it for \emph{all} families. Such a proof does not yet exist, however, combining the $f$- and $g$-conjectures with Theorem \ref{BBE} would already go a long way towards solving the Frankl conjecture. \begin{theorem}\label{fgBBE} If the $f$- and $g$-conjectures hold, then Conjecture \ref{minconj} holds for all $m$ for which there exists $i\in \mathbb{N}^+$ such that $\frac{2}{3}2^i \leq m \leq 2^i$. \end{theorem} \proof Let $m$ be such that $\frac{2}{3}2^i \leq m \leq 2^i$ for some $i$. If $g(n,m)<\frac{m}{2}$ for some $n\geq \lceil \log_2 m \rceil$, then we have a counterexample: a union-closed family on $n$ elements and $m$ sets where every element is in less than half of the sets. By the $g$-conjecture, since $i \geq \lceil \log_2 m \rceil$, $g(n,m)=g(i, m)<\frac{m}{2}$. However, by Theorem \ref{BBE}, $g(i,m) \geq \frac{m}{2}$ since $m\geq \frac{2}{3}2^i$. Thus, we have obtained a contradiction and $g(n,m)\geq \frac{m}{2}$ for all $n\geq \lceil \log_2 m \rceil$. \qed This would mean that Conjecture \ref{minconj} would hold for about $\frac{2}{3}$ of all possible values of $m$. Recall that Conjecture \ref{minconj} is equivalent to the Frankl conjecture, and so Theorem~\ref{fgBBE} could be reformulated in such terms. Another nice consequence of the $f$- and $g$-conjectures would be that there would finally be a known constant fraction of sets containing $e^*(\mathcal{F})$, the most frequent element in $\mathcal{F}$, in any union-closed family $\mathcal{F}$. \begin{theorem} If the $f$- and $g$-conjectures hold, then any union-closed family on $m$ sets contains an element in at least $\frac{6}{13} m$ sets of the family. \end{theorem} \proof By Theorem \ref{BSsurvey}, we know that $g(\lceil \log_2 m \rceil,m) \geq \frac{6}{13}m$ for any $m\in \mathbb{N}^+$. By the $g$-conjecture, we know that $g(n,m) \geq \frac{6}{13}m$ for all $n\geq \lceil \log_2 m \rceil$. Therefore, we know that any family on $m$ sets contains an element in at least $\frac{6}{13}m$ sets of the family. \qed Thus, from our point of view, studying the $f$- and $g$-conjectures offers new ways of attacking the Frankl conjecture, in addition to being interesting in and of itself. Hence, the new conjectures warrant a closer examination. \section{Towards Proving the New Conjectures}\label{sec:newresults} \subsection{Twin sets and a partial proof of the new conjectures} As noted before in Theorem \ref{conjecturesequivalent}, the $f$- and $g$-conjectures are equivalent, so from now on, we will focus only on the $f$-conjecture. We now introduce a new idea: twin sets. \begin{definition} We call two sets $S_1,S_2$ with $n>|S_1|>|S_2|$ \emph{twin sets} if $|S_1\triangle S_2| = 1$ . We call $S_1$ the \emph{big twin} and $S_2$ the \emph{little twin}. Moreover, we call the element $e=S_1\triangle S_2$ the \emph{twin difference of $S_1$ and $S_2$}. \end{definition} Twin sets play an important role in proving the $f$-conjecture as made clear by the following lemma. \begin{lemma}\label{ftwinscont} Suppose that the $f$-conjecture is not true and that there exists values of $n$ and $a$ with $n \geq \lceil \log_2 a \rceil + 1$ such that $f(n,a)a$. \begin{theorem}\label{falgasravryf} We have that $f(n-1,a)=f(n,a)$ for all $n> a$. \end{theorem} \proof First assume $f(n-1,a) a$. By Lemma \ref{ftwinscont}, every element in any optimal solution of $f(n,a)$ is a twin difference of at least one pair of sets. This implies that any optimal solution for $n$ elements contains no two elements that are exactly in the same sets. Indeed, such elements would not be twin differences. We can thus apply the same construction as in \cite{FalgasRavry2011}. Order the elements $[n]$ by decreasing frequency. Observe now that for all elements $1\leq i0$. Then we know that any optimal solution for $f(n+1,a)$ must be such that every element is a twin difference, otherwise we could remove that element and get an $m+k$ union-closed family spanning $n$ elements such that none is in more than $a$ sets, and so $f(n,a)\geq m+k$, a contradiction. Now let $$k':=\min_{e\in [n+1]}|\{S\in \mathcal{F}|e\not\in S, \ e\cup S\in \mathcal{F} \textup{ and } \mathcal{F} \textup{ is an optimal family for } f(n+1,a)\}|,$$ i.e., $k'$ is the minimum number of twin pairs for which an element is a twin difference in an optimal solution for $f_{n+1}(a)$. We now show that $k\leq k'$. Suppose not. Let $e'$ and $\mathcal{F}'$ be an element and a family such that $e'$ is a twin difference for $k'$ twin pairs. Remove $e'$ from $\mathcal{F}'$, and remove the $k'$ sets that are now duplicated. Call this new family $\mathcal{F}''$. What remains is a union-closed family of $m+k-k'$ sets on $n$ elements. So $m=f(n,a) \geq m+k-k'$, which implies that $k\leq k'$. Now suppose that $k=k'$. Notice then that there must exist $e''$ such that $e''$ is contained in $a$ sets of $\mathcal{F}'$ that must still be contained in $a$ sets of $\mathcal{F}''$. If not, each element of the new family $\mathcal{F}''$ would be contained in at most $a-1$ sets of $\mathcal{F}''$, and so we would have that $f(n,a-1)\geq m+k-k'=m$, which is a contradiction on the fact that $f(n,a-1) < f(n,a)$. Thus if $k=k'$, then there exists $e''$ such that $|\{S\in \mathcal{F}'| S\ni e''\}|=a$ and such that $e''$ is never contained in a set of the family that does not contain $e'$. Indeed, if there existed $S'\in \mathcal{F}'$ such that $e'\not\in S'$ and $e''\in S'$, then for any set $S''\in \mathcal{F}$ such that $S''\cup e' \in \mathcal{F}$ as well, i.e. twin sets with difference $e'$, then one of $S'\cup S''$ and $S'\cup (S''\cup e')$ will disappear in $\mathcal{F}''$ and so $e''$ would be present $a-1$ times, a contradiction. Thus $\{S\in \mathcal{F}'| S\ni e''\} \subseteq \{S\in \mathcal{F}'| S\ni e'\}$ and since $|\{S\in \mathcal{F}'| S\ni e''\}|=a$, then $|\{S\in \mathcal{F}'| S\ni e'\}|=a$ as well and $\{S\in \mathcal{F}'| S\ni e''\} = \{S\in \mathcal{F}'| S\ni e'\}$ which is a contradiction of the fact that $e'$ and $e''$ are twin differences for some sets. Since they are copies of each other, we can remove either one of them without creating duplicate sets. Thus, $k < k'$, and so if $k'=1$, then $k\leq 0$, and then $f(n,a)\geq f(n+1,a)$. \qed Note that this also means that if we remove any element from such a solution, and remove a copy of every duplicated set created, what remains is never an optimal solution for $f(n,a)$. \section{Conclusion} As we have seen, a complete proof of the new conjectures has far-reaching implications: the Frankl conjecture would hold for about $\frac{2}{3}$ of all possible cases, and we could show that there always exists an element in $\frac{6}{13}$ of the sets of a union-closed family. Therefore we believe our new conjectures merit additional attention. In order to encourage further progress in this direction, we conclude with a few open problems of interest. \begin{enumerate} \item Show that $f(n,a)=f(n+1,a)$ for smaller values of $n$, i.e., for values of $n