论文标题
整数程序的线性松弛，用于联合关闭的猜想
The Linear Relaxation of an Integer Program for the Union-Closed Conjecture
论文作者
论文摘要
弗兰克（Frankl）的猜想，也称为联盟锁定的集合，指出，在任何有限的非平衡工会封闭的家庭中，至少有一半的集合中存在一个元素。令$ f（n，a）$为$ n $元素的地面集合中的最大套装数量，其中每个元素最多包含在$ a，n \ in \ mathbb {n}^+$中。证明所有$ a，n \ in \ mathbb {n}^+$的$ f（n，a）\ leq 2a $等同于证明弗兰克尔的猜想。通过考虑Pulaj，Raymond和Theis在新猜想中提出的整数编程公式的线性放松，我们证明$ O（a^2）$是$ f（n，a）$的上限。我们还提供了可以加强这种结果的不同方式。此外，我们提供了一个新的证明，即$ f（n，2^{n-1} -1）= 2^n-n $。
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. Let $f(n,a)$ be the maximum 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 some $a,n\in \mathbb{N}^+$. Proving that $f(n,a)\leq 2a$ for all $a, n \in \mathbb{N}^+$ is equivalent to proving the Frankl conjecture. By considering the linear relaxation of the integer programming formulation that was proposed in New Conjectures for Union-Closed Families by Pulaj, Raymond and Theis, we prove that $O(a^2)$ is an upper bound for $f(n,a)$. We also provide different ways that this result could be strengthened. Additionally, we give a new proof that $f(n,2^{n-1}-1)=2^n-n$.
