An Erdos-Ko-Rado theorem for minimal covers
3
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Let $[n]=\{1,2,\dots, n\}$. A set $\mathbf A=\{A_1,A_2,\dots ,A_l\}$ is a minimal cover of $[n]$ if $\bigcup_{1\leq i\leq l} A_i =[n]$ and \[ \bigcup_{\substack{1\leq i\leq l,\\ i\neq j_0}} A_i \neq [n] \quad\textnormal{for all $j_0\in [l]$}. \] Let $\mathcal{C}(n)$ denote the collection of all minimal covers of $[n]$, and write $C_{n} = \vert \mathcal{C}(n)\vert$. Let $\mathbf A \in \mathcal{C}(n)$. An element $u \in [n]$ is critical in $\mathbf A$ if it appears exactly once in $\mathbf A$. Two minimal covers $\mathbf A$, $\mathbf B \in \mathcal{C}(n)$ are said to be restricted $t$-intersecting if they share at least $t$ sets each containing an element which is critical in both $\mathbf A$ and $\mathbf B$. A family $\A \subseteq \mathcal{C}(n)$ is said to be restricted $t$-intersecting if every pair of distinct elements in $\A$ are restricted $t$-intersecting. In this paper, we prove that there exists a constant $n_{0}=n_{0}(t)$ depending on $t$, such that for all $n \ge n_{0}$, if $\A \subseteq \mathcal{C}(n)$ is restricted $t$-intersecting, then $|\A| \le C_{n-t}$. Moreover, the bound is attained if and only if $\A$ is isomorphic to the family $\mathcal{D}_{0}(t)$ consisting of all minimal covers which contain the singleton parts $\{1\}$, $\ldots$, $\{t\}$. A similar result also holds for restricted $r$-cross intersecting families of minimal covers.
Abstract
Let $[n]=\{1,2,\dots, n\}$. A set $\mathbf A=\{A_1,A_2,\dots ,A_l\}$ is a minimal cover of $[n]$ if $\bigcup_{1\leq i\leq l} A_i =[n]$ and \[ \bigcup_{\substack{1\leq i\leq l,\\ i\neq j_0}} A_i \neq [n] \quad\textnormal{for all $j_0\in [l]$}. \] Let $\mathcal{C}(n)$ denote the collection of all minimal covers of $[n]$, and write $C_{n} = \vert \mathcal{C}(n)\vert$. Let $\mathbf A \in \mathcal{C}(n)$. An element $u \in [n]$ is critical in $\mathbf A$ if it appears exactly once in $\mathbf A$. Two minimal covers $\mathbf A$, $\mathbf B \in \mathcal{C}(n)$ are said to be restricted $t$-intersecting if they share at least $t$ sets each containing an element which is critical in both $\mathbf A$ and $\mathbf B$. A family $\A \subseteq \mathcal{C}(n)$ is said to be restricted $t$-intersecting if every pair of distinct elements in $\A$ are restricted $t$-intersecting. In this paper, we prove that there exists a constant $n_{0}=n_{0}(t)$ depending on $t$, such that for all $n \ge n_{0}$, if $\A \subseteq \mathcal{C}(n)$ is restricted $t$-intersecting, then $|\A| \le C_{n-t}$. Moreover, the bound is attained if and only if $\A$ is isomorphic to the family $\mathcal{D}_{0}(t)$ consisting of all minimal covers which contain the singleton parts $\{1\}$, $\ldots$, $\{t\}$. A similar result also holds for restricted $r$-cross intersecting families of minimal covers.
참고문헌 (38)
- R. Ahlswede, "The complete intersection theorem for systems of finite sets", European J. Combin, 18(2), pp.125~136 (1997)
- R. Ahlswede, "The diametric theorem in Hamming spaces – Optimal anticodes", Adv. in Appl. Math, 20(4), pp.429~449 (1998)
- C. Bey, "On cross-intersecting families of sets", Graphs Combin, 21(2), pp.161~168 (2005)
- P. Borg, "The maximum sum and the maximum product of sizes of cross-intersecting families", European J. Combin, 35, pp.117~130 (2014)
- F. Brunk, "Some Erdos-Ko-Rado theorems for injections", European J. Combin, 31(3), pp.839~860 (2010)
- P. J. Cameron, "Intersecting families of permutations", European J. Combin, 24(7), pp.881~890 (2003)
- A. Chowdhury, "Shadows and intersections in vector spaces", J. Combin. Theory Ser. A, 117(8), pp.1095~1106 (2010)
- D. Ellis, "Stability for t-intersecting families of permutations", J. Combin. Theory Ser. A, 118(1), pp.208~227 (2011)
- D. Ellis, "Forbidding just one intersection, for permutations", J. Combin. Theory Ser. A, 126, pp.136~165 (2014)
- D. Ellis, "Intersecting families of permutations", J. Amer. Math. Soc, 24(3), pp.649~682 (2011)
- P. Erd˝os, "Intersection theorems for systems of finite sets", Quart. J. Math. Oxford Ser. (2), 12, pp.313~318 (1961)
- P. Frankl, "On intersecting families of finite sets", J. Combin. Theory Ser. A, 24(2), pp.146~161 (1978)
- P. Frankl, "The Erd˝os-Ko-Rado theorem is true for n = ckt, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I", Colloq. Math. Soc. Jnos Bolyai, 18, pp.365~375 (1978), North-Holland
- P. Frankl, "Nontrivial intersecting families", J. Combin. Theory Ser. A, 41(1), pp.150~153 (1986)
- P. Frankl, "An Erd˝os-Ko-Rado theorem for cross t-intersecting families", J. Combin. Theory Ser. A, 128, pp.207~249 (2014)
- P. Frankl, "On r-cross intersecting families of sets", Combin. Probab. Comput, 20(5), pp.749~752 (2011)
- P. Frankl, "The Erd˝os-Ko-Rado theorem for vector spaces", J. Combin. Theory Ser. A, 43(2), pp.228~236 (1986)
- C. Godsil, "A new proof of the Erd˝os-Ko-Rado theorem for intersecting families of permutations", European J. Combin, 30(2), pp.404~414 (2009)
- C. Y. Ku, "An Erd˝os-Ko-Rado theorem for partial permutations", Discrete Math, 306(1), pp.74~86 (2006)
- C. Y. Ku, "Erd˝os-Ko-Rado theorems for permutations and set partitions", J. Combin. Theory Ser. A, 115(6), pp.1008~1020 (2008)
- C. Y. Ku, "On cross-intersecting families of set partitions", Electron. J. Combin, 19(4), pp.49~ (2012)
- C. Y. Ku, "An analogue of Hilton-Milner theorem for set partitions", J. Combin. Theory Ser. A, 120(7), pp.1508~1520 (2013)
- C. Y. Ku, "An analogue of the Erd˝os-Ko-Rado theorem for weak compositions", Discrete Math, 313(21), pp.2463~2468 (2013)
- C. Y. Ku, "On r-cross intersecting families of sets", Far East J. Math. Sci, 75, pp.295~300 (2013)
- C. Y. Ku, "An Erd˝os-Ko-Rado theorem for permutations with fixed number of cycles", Electron. J. Combin, 21(3), pp.9~ (2014)
- C. Y. Ku, "A Deza-Frankl type theorem for set partitions", Electron. J. Combin, 22(1), pp.11~ (2015)
- Cheng Yeaw Ku, "AN ANALOGUE OF THE HILTON-MILNER THEOREM FOR WEAK COMPOSITIONS", 대한수학회보, 52(3), pp.1007~1025 (2015), 대한수학회
- C. Y. Ku, "On r-cross t-intersecting families for weak compositions", Discrete Math, 338(7), pp.1090~1095 (2015)
- C. Y. Ku, "A non-trivial intersection theorem for permutations with fixed number of cycles", Discrete Math, 339(2), pp.646~657 (2016)
- C. Y. Ku, "An intersecting theorem for integer sequence"
- C. Y. Ku, "Intersecting families in the alternating group and direct product of symmetric groups", Electron. J. Combin, 14(1), pp.15~ (2007)
- M. Matsumoto, "The exact bound in the Erd˝os-Ko-Rado theorem for cross-intersecting families", J. Combin. Theory Ser. A, 52(1), pp.90~97 (1989)
- A. Moon, "An analogue of the Erd˝os-Ko-Rado theorem for the Hamming schemes H(n, q)", J. Combin. Theory Ser. A, 32(3), pp.386~390 (1982)
- L. Pyber, "A new generalization of the Erd˝os-Ko-Rado theorem", J. Combin. Theory Ser. A, 43(1), pp.85~90 (1986)
- N. Tokushige, "A product version of the Erd˝os-Ko-Rado theorem", J. Combin. Theory Ser. A, 118(5), pp.1575~1587 (2011)
- J. Wang, "Cross-intersecting families and primitivity of symmetric sys-tems", J. Combin. Theory Ser. A, 118(2), pp.455~462 (2011)
- J. Wang, "An Erd˝os-Ko-Rado-type theorem in Coxeter groups", European J. Combin, 29(5), pp.1112~1115 (2008)
- R. M. Wilson, "The exact bound in the Erd˝os-Ko-Rado theorem", Combinatorica, 4(2-3), pp.247~257 (1984)