Lexicographic initial segments as extremal non-FC families: Pulaj–Wood's Conjecture 1 on the threshold $FC(k,n)$

A family of sets is Frankl-complete (FC) if every union-closed family containing it satisfies Frankl's union-closed sets conjecture with an element of its universe, and $FC(k,n)$ is the least number of distinct $k$-sets on an $n$-element ground set that forces Frankl-completeness. Pulaj and Wood (Experimental Mathematics, 2024) computed new exact values and bounds for $FC(k,n)$ and observed that, in all of their exhaustive machine-verified enumerations, there was always a maximum-size non-FC family of $k$-sets that is a lexicographic initial segment of $\binom{[n]}{k}$. They posed Conjecture 1: for fixed $n>k\ge3$, if the $m$-th lexicographic initial segment $[S_m]$ is an FC-family whose universe has size exactly $n$, then $FC(k,n)\le m$. An affirmative answer would reduce computing $FC(k,n)$ to finding a single lexicographic threshold and would immediately complete the exact $FC(k,n)$ table for all defined pairs with $n\le10$. The problem is open.

Background

A finite family of sets $\mathcal{F}$ is union-closed if $A\cup B\in\mathcal{F}$ whenever $A,B\in\mathcal{F}$. Frankl's union-closed sets conjecture (1979) predicts that every finite union-closed family containing at least one nonempty set has an element that belongs to at least half of its member sets; the ground set or universe of $\mathcal{F}$ is $U(\mathcal{F})=\bigcup_{S\in\mathcal{F}}S$. The conjecture remains open. A family of sets $\mathcal{A}$ is called Frankl-complete, or FC, if every union-closed family $\mathcal{F}\supseteq\mathcal{A}$ satisfies Frankl's conjecture with some element of $U(\mathcal{A})$; families that are not FC are called non-FC. Poonen (1992) gave a complete polyhedral characterization that makes FC-status effectively checkable. Write $[n]=\{1,\dots,n\}$ and $\mathcal{P}([n])$ for the power set of $[n]$. A union-closed $\mathcal{A}$ with $\emptyset\in\mathcal{A}$ and $U(\mathcal{A})=[n]$ is FC if and only if there exists a weight vector $c\in\mathbb{R}_{\ge0}^n$ with $\sum_{i\in[n]}c_i=1$ such that $\sum_{i\in[n]}c_i|\mathcal{B}_i|\ge|\mathcal{B}|/2$ for every union-closed $\mathcal{B}\subseteq\mathcal{P}([n])$ with $\mathcal{A}\uplus\mathcal{B}=\mathcal{B}$, where $\mathcal{A}\uplus\mathcal{B}=\{A\cup B:A\in\mathcal{A},B\in\mathcal{B}\}$ and $\mathcal{B}_i=\{B\in\mathcal{B}:i\in B\}$ counts the sets of $\mathcal{B}$ containing $i$; the set of such $c$ is a polyhedron $P^{\mathcal{A}}$, so whether a concrete family is FC is decidable by finite linear programming, which is how all modern FC computations are certified (with linear programming, integer programming, or SMT solvers, where SMT, satisfiability modulo theories, refers to software that decides logical formulas with arithmetic constraints). One strand of work on Frankl's conjecture quantifies how many $k$-element sets force Frankl-completeness: for $3\le k<n$, $FC(k,n)$ is the least integer $m$ such that any family $\mathcal{A}\subseteq\mathcal{P}([n])$ containing $m$ distinct $k$-sets is FC; containing $m$ and containing at least $m$ distinct $k$-sets are equivalent conditions, since any family containing an FC family is itself FC. The value $FC(k,n)$ can be undefined, which happens exactly when the family $\binom{[n]}{k}$ of all $k$-sets is itself non-FC (for example $FC(5,6)$ is undefined). Morris (2006) proved $FC(3,n)\ge\lfloor n/2\rfloor+1$ for all $n\ge4$ and conjectured equality, later confirmed by Pulaj; he also proved $FC(4,5)=5$, and the machine-verified classification of FC-families on six elements gave $FC(4,6)=7$. Pulaj and Wood (2024) added the exact values $FC(4,7)=10$, $FC(4,8)=12$, $FC(5,7)=14$, $FC(6,8)=26$ (each verified with SMT infeasibility certificates; $FC(4,8)$ alone took over 26 days of computation), lower bounds such as $FC(4,9)\ge14$, $FC(5,10)\ge44$, $FC(7,10)\ge85$, and new upper bounds. To state their structural conjecture, order the $k$-subsets of $[n]$ lexicographically, $A<B$ if and only if $\min(A\triangle B)\in A$, where $A\triangle B$ is the symmetric difference; let $S_1<S_2<\cdots$ enumerate $\binom{[n]}{k}$ in this order and let $[S_m]=\{A\in\binom{[n]}{k}:A\le S_m\}$ be the $m$-th initial segment. Running an isomorphism-free enumeration of all non-FC families of $m$ distinct $k$-sets — an exhaustive search that records each family only once up to relabeling of the ground set — the authors observed that there was always a maximum-size non-FC family of the form $[S_m]$, and they conjectured that this is a universal phenomenon. They verified the conjecture for every pair $(k,n)$ with $n>k\ge3$ for which $FC(k,n)$ is known (it is trivial for $k=3$), and showed that, conditional on it, their lower bounds become exact and yield a complete classification of $FC(k,n)$ for all defined pairs with $3\le k<n\le10$.

Problem Statement

Fix integers $n>k\ge3$. Order the $k$-element subsets of $[n]$ lexicographically, $A<B$ if and only if $\min(A\triangle B)\in A$, let $S_1<S_2<\cdots$ be this enumeration of $\binom{[n]}{k}$, and let $[S_m]=\{A\in\binom{[n]}{k}:A\le S_m\}$ denote the $m$-th lexicographic initial segment. Recall that $FC(k,n)$, when it exists, is the least integer $m$ such that every family $\mathcal{A}\subseteq\mathcal{P}([n])$ containing $m$ distinct $k$-sets is Frankl-complete; it is undefined exactly when $\binom{[n]}{k}$ itself is not Frankl-complete, and the hypothesis of the conjecture below already forces $FC(k,n)$ to be defined, since any family containing an FC family is FC and $\binom{[n]}{k}\supseteq[S_m]$. Pulaj and Wood's Conjecture 1 asserts: if $[S_m]$ is an FC-family whose universe $\bigcup_{A\in[S_m]}A$ has size exactly $n$, then $FC(k,n)\le m$. Prove or refute this conjecture in full generality. An affirmative answer would reduce the exact computation of $FC(k,n)$ to a single lexicographic threshold: whenever $[S_m]$ is FC with universe of size $n$ and $[S_{m-1}]$ is not FC, the conjecture gives $FC(k,n)\le m$ while the non-FC family $[S_{m-1}]$ of $m-1$ distinct $k$-sets gives $FC(k,n)\ge m$, so $FC(k,n)=m$; the source paper shows that, conditional on the conjecture, this completes the exact determination of $FC(k,n)$ for all defined pairs with $3\le k<n\le10$, such as pinning $FC(4,9)$, known to lie between $14$ and $21$, to an exact value. A refutation must exhibit integers $n>k\ge3$ and $m$ together with a certificate that $[S_m]$ is FC with universe of size $n$ and an explicit family of exactly $m$ distinct $k$-subsets of $[n]$ that is not FC.

References

1. Jonad Pulaj, Kenan Wood. Local Configurations in Union-Closed Families. Experimental Mathematics 34(4):719–727 (2024), DOI 10.1080/10586458.2024.2410964; arXiv:2301.01331, https://arxiv.org/abs/2301.01331
2. Bjorn Poonen. Union-Closed Families. Journal of Combinatorial Theory, Series A 59(2):253–268 (1992), DOI 10.1016/0097-3165(92)90068-6, https://doi.org/10.1016/0097-3165(92)90068-6
3. Robert Morris. FC-families and improved bounds for Frankl's conjecture. European Journal of Combinatorics 27(2):269–282 (2006), DOI 10.1016/j.ejc.2004.07.012, https://doi.org/10.1016/j.ejc.2004.07.012
4. Stijn Cambie. Progress on the union-closed conjecture and offsprings in winter 2022-2023. arXiv:2306.12351 (2023), https://arxiv.org/abs/2306.12351
5. David Ellis, Maria-Romina Ivan, Imre Leader. Small Sets in Union-Closed Families. Electronic Journal of Combinatorics 30(1):P1.8 (2023), DOI 10.37236/11004, https://doi.org/10.37236/11004
6. Theresa P. Vaughan. A Note on the Union-Closed Sets Conjecture. Journal of Combinatorial Mathematics and Combinatorial Computing 45:95–108 (2003), zbMATH Zbl 1148.05320, https://zbmath.org/1148.05320
7. Filip Marić, Bojan Vučković, Miodrag Živković. Fully Automatic, Verified Classification of all Frankl-Complete (FC(6)) Set Families. arXiv:1902.08765 (2019), https://arxiv.org/abs/1902.08765
8. Jonad Pulaj. Cutting Planes for Families Implying Frankl's Conjecture. Mathematics of Computation 89(322):829–857 (2020; published online 2019), DOI 10.1090/mcom/3461, https://doi.org/10.1090/mcom/3461
9. Jonad Pulaj. Characterizing 3-Sets in Union-Closed Families. Experimental Mathematics 32(2):350–361 (2023; published online 2021), DOI 10.1080/10586458.2021.1927254, https://doi.org/10.1080/10586458.2021.1927254