Two results on set families: sturdiness and intersection
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913043737214976 |
|---|---|
| author | Wu, Yongjiang Liu, Zhiyi Feng, Lihua Li, Yongtao |
| author_facet | Wu, Yongjiang Liu, Zhiyi Feng, Lihua Li, Yongtao |
| contents | This paper resolves two open problems in extremal set theory. For a family $\mathcal{F} \subseteq 2^{[n]}$ and $i, j\in [n]$, we denote $\mathcal{F} (i,\bar{j})=\{F\backslash\{i\}: F\in \mathcal{F}, F\cap\{i,j\}=\{i\}\}$. The sturdiness $β(\mathcal{F})$ is defined as the minimum $|\mathcal{F} (i,\bar{j})|$ over all $i\neq j$. A family $\mathcal{F}$ is called an IU-family if it satisfies the intersection constraint: $F\cap F'\neq \emptyset $ for all $F,F'\in \mathcal{F}$, as well as the union constraint: $F\cup F' \neq [n]$ for all $F,F'\in \mathcal{F}$. The well-known IU-Theorem states that every IU-family $\mathcal{F}\subseteq 2^{[n]}$ has size at most $ 2^{n-2}$. In this paper, we prove that if $\mathcal{F}\subseteq 2^{[n]}$ is an IU-family, then $β(\mathcal{F})\le 2^{n-4}$. This confirms a recent conjecture proposed by Frankl and Wang.
As the second result, we establish a tight upper bound on the sum of sizes of cross $t$-intersecting separated families. Our result not only extends a previous theorem of Frankl, Liu, Wang and Yang on separated families, but also provides explicit counterexamples to an open problem proposed by them, thereby settling their problem in the negative. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19723 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two results on set families: sturdiness and intersection Wu, Yongjiang Liu, Zhiyi Feng, Lihua Li, Yongtao Combinatorics 05D05 This paper resolves two open problems in extremal set theory. For a family $\mathcal{F} \subseteq 2^{[n]}$ and $i, j\in [n]$, we denote $\mathcal{F} (i,\bar{j})=\{F\backslash\{i\}: F\in \mathcal{F}, F\cap\{i,j\}=\{i\}\}$. The sturdiness $β(\mathcal{F})$ is defined as the minimum $|\mathcal{F} (i,\bar{j})|$ over all $i\neq j$. A family $\mathcal{F}$ is called an IU-family if it satisfies the intersection constraint: $F\cap F'\neq \emptyset $ for all $F,F'\in \mathcal{F}$, as well as the union constraint: $F\cup F' \neq [n]$ for all $F,F'\in \mathcal{F}$. The well-known IU-Theorem states that every IU-family $\mathcal{F}\subseteq 2^{[n]}$ has size at most $ 2^{n-2}$. In this paper, we prove that if $\mathcal{F}\subseteq 2^{[n]}$ is an IU-family, then $β(\mathcal{F})\le 2^{n-4}$. This confirms a recent conjecture proposed by Frankl and Wang. As the second result, we establish a tight upper bound on the sum of sizes of cross $t$-intersecting separated families. Our result not only extends a previous theorem of Frankl, Liu, Wang and Yang on separated families, but also provides explicit counterexamples to an open problem proposed by them, thereby settling their problem in the negative. |
| title | Two results on set families: sturdiness and intersection |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2508.19723 |