Further analysis on the second frequency of union-closed set families
Saintan Wu · 2024
Read Further analysis on the second frequency of union-closed set families by Saintan Wu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03863.txt.
Introduction
Saintan Wu wrote this math paper in two thousand twenty-four as the sole author. It digs into the one case left open in Nagel's stronger form of the union-closed sets conjecture, also known as Frankl's conjecture.
The base guess says some element lies in at least half the sets of any union-closed family. Nagel asked for more such common elements, with a weaker share for each. Past work settled ground sets of size three and up, and size two outside a set range of family sizes. This companion paper uses linear programming to study the families in that range, where the strong guess can fail.
Catalog record
| CREATOR | Saintan Wu |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03863
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Further analysis on the second frequency of union-closed set families Saintan Wu Abstract The Union-Closed Sets Conjecture, also known as Frankl’s conjecture, asks whether, for any union-closed set family ℱ \mathcal{F} with m m sets, there is an element that lies in at least 1 2 ⋅ m \frac{1}{2}\cdot m sets in ℱ \mathcal{F} . In 2022, Nagel posed a stronger conjecture that within any union-closed family whose ground set size is at least k k , there are always k k elements in the ground set that appear in at least 1 2 k − 1 + 1 \frac{1}{2^{k-1}+1} proportion of the sets in the family. Das and Wu showed that this conjecture is true for k ≥ 3 k\geq 3 and k = 2 k=2 if | ℱ | |\mathcal{F}| is outside a particular range. In this companion paper, we analyse further when ℱ \mathcal{F} fails Nagel’s conjecture for k = 2 k=2 via linear programming. 1 Introduction A union-closed set family \mathcal{F} is a set family satisfying A,B\in\mathcal{F}\implies A\cup B\in\mathcal{F} . Nagel [ 2 ] conjectured that: Conjecture 1 . For any union-closed set family |\mathcal{F}| with ground set \geq k , there are k elements, each of them lies in at least \frac{1}{2^{k-1}+1}|\mathcal{F}| many sets in \mathcal{F} . Let F_{k}(\mathcal{F}) denote the ratio of sets in \mathcal{F} that contain the k -th most frequent element. So the above conjecture states that F_{k}(\mathcal{F})\geq\frac{1}{2^{k-1}+1} for such families. Notice that when k=1 , it conjectures the well-known Union-Closed Sets Conjecture, that every nonempty union-closed family has an element appearing in at least \frac{|\mathcal{F}|}{2} sets. [ 1 ] gives a notion about k -good set, which here we will only use 2 -good sets: Definition 1.1 . Given a union-closed family \mathcal{F} , a set S is 2 -good for \mathcal{F} if it does not contain 1 , and for each set A that is not \varnothing nor \{1\} , S\cap A\neq\varnothing . A 2 -good set is called minimal if its proper subsets are not 2 -good. Then, in the paper, [ 1 ] proved, via the entropic method for large families and shattering method for small families, that Theorem 1.2 . Let k\geq 2 , and let \mathcal{F} be a union-closed set family with |\mathcal{F}|=m and |\cup_{F\in\mathcal{F}}F|\geq k . Then the k th-most frequent element lies in at least \frac{m}{2^{k-1}+1} sets in \mathcal{F} , with equality only if \mathcal{F} is a near- k -cube, provided: (i) k\geq 3 , or (ii) k=2 , and either m\leq 44 or m\geq 114 . We still did not know if there is a counterexample for k=2 when |\mathcal{F}|\in[45,113] . We will analyse this case more carefully and narrow the range. Our main result in this paper is the following: Theorem 1.3 . Let \mathcal{F} be union-closed with |\cup_{F\in\mathcal{F}}F|\geq 2 , and that \mathcal{F} is not a near- 2 -cube. Then, if f_{2}(\mathcal{F})\leq\frac{1}{3} , we must have 1. 81\leq|\mathcal{F}|\leq 113 , and 2. All minimal 2 -good sets S have size 4 . In the following sections, we will focus on the case when \mathcal{F} has f_{2}(\mathcal{F})\leq\frac{1}{3} and is in the case that Theorem 1.2 didn’t cover. That is, when |\mathcal{F}|\in[45,113] and any of its minimal 2 -good sets S has size 4 or 5 . We will further assume that \varnothing\in\mathcal{F} , and 1 is the most abundant element in sets of \mathcal{F} . Paper structure and notations In Section 2, we will briefly explain the idea behind the proof. Then, we will prove several lemmas mentioned in the heuristics. After that, two separate cases |S|=4 and |S|=5 will be done in Section 4 and Section 5 , respectively. For simplicity, for any set S and element x , we use S+x for S\cup\{x\} , and S-x for S\setminus\{x\} . We will also write, for example, abd for short of \{a,b,d\} . 2 Heuristics behind the proof 2.1 Review of the shattering strategy Let us first have a brief review of the proof for the case 4\leq|\mathcal{F}|\leq 113 and k=2 . We considered a minimal 2 -good set S and showed that by the minimality, for any element y\in S , there is F_{y}\in\mathcal{F} that F_{y}\cap S=\{y\} because if there was no such F_{y} , S-y became a smaller 2 -good set. By the union-closed property, for any T\subseteq S , we find that F_{T}:=\bigcup_{y\in T}F_{y} is in \mathcal{F} , and F_{T}\cap S=T . This shows that |S|\leq\log_{2}|\mathcal{F}| because these 2^{|S|} sets F_{T},T\subseteq S , are surely different. Lastly, using F_{T} ’s to analyse the incidence \sum_{A\in\mathcal{F}}|A\cap S| of \mathcal{F} over S when f_{2}(\mathcal{F})\leq\frac{1}{3} , we get that either s=4 and m\geq 45 , or s=5 and m\geq 70.5 . 2.2 Linear programming and two ways of winning We can make a more careful estimate: For each subset T of S , we define q_{T} as the quantity of sets A in \mathcal{F} that S\cap A=T . • By S being 2 -good, there are at most 2 sets that do not intersect S , namely \varnothing and \{1\} . Thus q_{\varnothing}\leq 2. • By F_{T}\cap S=T , we obtain q_{T}\geq 1\qquad\text{for each }T\subseteq S. • As f_{2}(\mathcal{F})\leq\frac{1}{3} , we obtain \sum_{y\in T}q_{T}\leq\frac{m}{3}\qquad\text{for each }y\in S. It turns out that these are all linear constraints for q_{T} ’s and m , so we can solve it by setting the following linear programming L_{0} : Variables m,q_{T}:T\subseteq S Minimize m Subject to \begin{array}[]{r@{\,}ll}q_{\varnothing}&\leq 2,&\\ q_{T}&\geq 1,&T\subseteq S\\ \sum_{T\subseteq S}q_{T}&=m,&\\ \sum_{y\in T}q_{T}&\leq\frac{m}{3},&y\in S.\\ \end{array} By solving this directly, we get same bounds m\geq 45 for |S|=4 and m\geq 70.5 for |S|=5 . So what happens when this LP reaches the lower bound? A solution reaching the lower bound of m when |S|=4 is q_{T}=\begin{cases}2,&T=\varnothing;\\ 8,&|T|=1;\\ 1,&|T|\geq 2.\end{cases} This configuration can cause many dependencies. For example, while there are many pairs of choices of F_{a},F_{b} in the proof, they all result in the unique F_{ab}:=F_{a}\cup F_{b} ! This phenomenon could only happen when each element in F_{ab} is either a common element of F_{a} s or a common element of F_{b} s. In this scenario, elements outside S appear in many sets. Hence, we can strengthen L_{0} by considering another carefully chosen element x . This x allows two ways of winning: Either • this x helps us find different sets (by spotting x\notin F_{T},x\in F_{T}^{\prime} ) that F_{T}\cap S=T=F_{T}^{\prime}\cap S for big T . In this way, it gives a greater lower bound for q_{T} . Or, • x itself lies in many sets. In this way, it gives an extra constraint for L_{0} , as x cannot lie in over \frac{m}{3} sets if x\neq 1 . 2.3 The choice of x and three lemmas We will pick x\neq 1 and an a\in S such that there are two sets F_{a},F_{a}^{\prime} with F_{a}\cap(S+x)=a,F_{a}^{\prime}\cap(S+x)=ax . For any choice of F_{y},y\in S , such that F_{y}\cap S=\{y\} , we associate F_{T}:=\bigcup_{y\in T}F_{y},T\subseteq S. Now we see how the flexibility of choice of F_{a} helps us: If we can choose F_{y} for y\in S such that x\notin F_{T} , then F_{T}\cup F_{a} and F_{T}\cup F_{a}^{\prime} are two different sets in \mathcal{F} , both of which intersect S at T+a , thus q_{T+a}\geq 2 . We can