On Non-Empty Cross-Intersecting Families
Combinatorica · 2022-12 · 42 (S2) · 1513-1525
DOI: 10.1007/s00493-021-4839-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorica, online erschienen am 21.09.2022. Verfasst von Chao Shi und 2 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 21 Literaturangaben.
Abstract (Originalsprache)
Let 2[n] and ([n]i\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\matrix{{\left[ n \right]} \cr i \cr } $$\end{document}) be the power set and the collection of all i-subsets of {1, 2, …, n}, respectively. We call t (t ≥ 2) families A1,A2,…,At⊆2[n]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\cal A}_1},{{\cal A}_2}, \ldots ,{{\cal A}_t} \subseteq {2^{\left[ n \right]}}$$\end{document}cross-intersecting if Ai ∩ Aj ≠ ∅ for any Ai∈Ai\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A_i} \in {{\cal A}_i}$$\end{document} and Aj∈Aj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A_j} \in {{\cal A}_j}$$\end{document} with i ≠ j. We show that, for n ≥ k +l, l ≥ r ≥ 1, c > 0 and A⊆([n]k),ℬ⊆([n]l)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal A} \subseteq \left( {\matrix{{\left[ n \right]} \cr k \cr } } \right),{\cal B} \subseteq \left( {\matrix{{\left[ n \right]} \cr l \cr } } \right)$$\end{document}, if A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal A}$$\end{document} and ℬ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal B}$$\end{document} are cross-intersecting and (n−rl−r)≤|ℬ|≤(n−1l−1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( {\matrix{{n - r} \cr {l - r} \cr } } \right) \le \left| {\cal B} \right| \le \left( {\matrix{{n - 1} \cr {l - 1} \cr } } \right)$$\end{document}, then |A|+c|ℬ|≤max{(nk)−(n−rk)+c(n−rl−r),(n−1k−1)+c(n−1l−1)}.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left| {\cal A} \right| + c\left| {\cal B} \right| \le \max \left\{ {\left( {\matrix{n \cr k \cr } } \right) - \left( {\matrix{{n - r} \cr k \cr } } \right) + c\left( {\matrix{{n - r} \cr {l - r} \cr } } \right),\left( {\matrix{{n - 1} \cr {k - 1} \cr } } \right) + c\left( {\matrix{{n - 1} \cr {l - 1} \cr } } \right)} \right\}.$$\end{document} This implies a result of Tokushige and the second author (Theorem 3.1) and also yields that, for n ≥ 2k, if A1,A2,…,At⊆([n]k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\cal A}_1},{{\cal A}_2}, \ldots ,{{\cal A}_t} \subseteq \left( {\matrix{{\left[ n \right]} \cr k \cr } } \right)$$\end{document} are non-empty cross-intersecting, then ∑i=1t|Ai|≤max{(nk)−(n−kk)+t−1,t(n−1k−1)},\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum\limits_{i = 1}^t {\left| {{{\cal A}_i}} \right| \le \max \left\{ {\left( {\matrix{n \cr k \cr } } \right) - \left( {\matrix{{n - k} \cr k \cr } } \right) + t - 1,\,\,t\left( {\matrix{{n - 1} \cr {k - 1} \cr } } \right)} \right\},} $$\end{document} which generalizes the corresponding result of Hilton and Milner for t = 2. Moreover, the extremal families attaining the two upper bounds above are also characterized.
Zitieren
APA
Shi, C., Frankl, P., & Qian, J. (2022). On Non-Empty Cross-Intersecting Families. Combinatorica, 42(S2), 1513-1525. https://doi.org/10.1007/s00493-021-4839-4
Vancouver
Shi C, Frankl P, Qian J. On Non-Empty Cross-Intersecting Families. Combinatorica. 2022;42(S2):1513-1525. doi:10.1007/s00493-021-4839-4
BibTeX
@article{Shi2022,
author = {Shi, Chao and Frankl, Peter and Qian, Jianguo},
title = {On Non-Empty Cross-Intersecting Families},
journal = {Combinatorica},
year = {2022},
volume = {42},
number = {S2},
pages = {1513--1525},
doi = {10.1007/s00493-021-4839-4}
}
EUVIMED