본문 바로가기
KERD
논문KCI 등재

AN ANALOGUE OF THE HILTON-MILNER THEOREM FOR WEAK COMPOSITIONS

Kok Bin Wong|Cheng Yeaw Ku
대한수학회 (The Korean Mathematical Society)|2015.05|대한수학회보 (Bulletin of the KMS)|제52권 제3호|pp. 1007-1025

0

조회

0

다운로드

2

인용

0

참고문헌

키워드

weak compositionscross-intersecting familyHilton-MilnerErd˝os-Ko-Rado
주제분류수학

초록

Let N0 be the set of non-negative integers, and let P(n, l) denote the set of all weak compositions of n with l parts, i.e., P(n, l) = {(x1, x2, . . . , xl) ∈ Nl 0 : x1 + x2 + · · · + xl = n}. For any element u = (u1, u2, . . . , ul) ∈ P(n, l), denote its ith-coordinate by u(i), i.e., u(i) = ui. A family A ⊆ P(n, l) is said to be t-intersecting if |{i : u(i) = v(i)}| ≥ t for all u, v ∈ A. A family A ⊆ P(n, l) is said to be trivially t-intersecting if there is a t-set T of [l] = {1, 2, . . . , l} and elements ys ∈ N0 (s ∈ T) such that A = {u ∈ P(n, l) : u(j) = yj for all j ∈ T}. We prove that given any positive integers l, t with l ≥ 2t + 3, there exists a constant n0(l, t) depending only on l and t, such that for all n ≥ n0(l, t), if A ⊆ P(n, l) is non-trivially t-intersecting, then |A| ≤ (n + l − t − 1 l − t − 1 ) − ( n − 1 l − t − 1) + t. Moreover, equality holds if and only if there is a t-set T of [l] such that A = [∪ s∈[l]＼T As ∪ {qi : i ∈ T} , where As = {u ∈ P(n, l) : u(j) = 0 for all j ∈ T and u(s) = 0} and qi ∈ P(n, l) with qi(j) = 0 for all j ∈ [l] ＼ {i} and qi(i) = n.

Abstract

Let N0 be the set of non-negative integers, and let P(n, l) denote the set of all weak compositions of n with l parts, i.e., P(n, l) = {(x1, x2, . . . , xl) ∈ Nl 0 : x1 + x2 + · · · + xl = n}. For any element u = (u1, u2, . . . , ul) ∈ P(n, l), denote its ith-coordinate by u(i), i.e., u(i) = ui. A family A ⊆ P(n, l) is said to be t-intersecting if |{i : u(i) = v(i)}| ≥ t for all u, v ∈ A. A family A ⊆ P(n, l) is said to be trivially t-intersecting if there is a t-set T of [l] = {1, 2, . . . , l} and elements ys ∈ N0 (s ∈ T) such that A = {u ∈ P(n, l) : u(j) = yj for all j ∈ T}. We prove that given any positive integers l, t with l ≥ 2t + 3, there exists a constant n0(l, t) depending only on l and t, such that for all n ≥ n0(l, t), if A ⊆ P(n, l) is non-trivially t-intersecting, then |A| ≤ (n + l − t − 1 l − t − 1 ) − ( n − 1 l − t − 1) + t. Moreover, equality holds if and only if there is a t-set T of [l] such that A = [∪ s∈[l]＼T As ∪ {qi : i ∈ T} , where As = {u ∈ P(n, l) : u(j) = 0 for all j ∈ T and u(s) = 0} and qi ∈ P(n, l) with qi(j) = 0 for all j ∈ [l] ＼ {i} and qi(i) = n.

참고문헌 (44)

  1. R. Ahlswede, "The complete intersection theorem for systems of finite sets", European J. Combin, 18(2), pp.125~136 (1997)
  2. R. Ahlswede, "The diametric theorem in Hamming spaces – optimal anticodes", Adv. in Appl. Math, 20(4), pp.429~449 (1998)
  3. C. Bey, "On cross-intersecting families of sets", Graphs Combin, 21(2), pp.161~168 (2005)
  4. P. Borg, "Extremal t-intersecting sub-families of hereditary families", J. London Math. Soc, 79(1), pp.167~185 (2009)
  5. P. Borg, "On t-intersecting families of signed sets and permutations", Discrete Math, 309(10), pp.3310~3317 (2009)
  6. P. Borg, "The Erd˝os-Ko-Rado property of various graphs containing singletons", Discrete Math, 309(9), pp.2877~2885 (2009)
  7. F. Brunk, "Some Erd˝os-Ko-Rado theorems for injections", European J. Combin, 31, pp.839~860 (2010)
  8. P. J. Cameron, "Intersecting families of permutations", European J. Combin, 24(7), pp.881~890 (2003)
  9. A. Chowdhury, "Shadows and intersections in vector spaces", J. Combin. Theory Ser. A, 117(8), pp.1095~1106 (2010)
  10. M. Deza, "On the maximum number of permutations with given maximal or minimal distance", J. Combin. Theory Ser. A, 22(3), pp.352~360 (1977)
  11. D. Ellis, "Stability for t-intersecting families of permutations", J. Combin. Theory Ser. A, 118(1), pp.208~227 (2011)
  12. D. Ellis, "Intersecting families of permutations", J. Amer. Math. Soc, 24(3), pp.649~682 (2011)
  13. K. Engel, "An Erd˝os-Ko-Rado theorem for integer sequences of given rank", European J. Combin, 7(3), pp.215~220 (1986)
  14. P. Erd˝os, "Intersection theorems for systems of finite sets", Quart. J. Math. Oxford Ser. (2), 12, pp.313~320 (1961)
  15. 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
  16. P. Frankl, "Nontrivial intersecting families", J. Combin. Theory Ser. A, 41(1), pp.150~153 (1986)
  17. P. Frankl, "On r-cross intersecting families of sets", Combin. Probab. Comput, 20(5), pp.749~752 (2011)
  18. P. Frankl, "The Erd˝os-Ko-Rado theorem for vector spaces", J. Combin. Theory Ser. A, 43(2), pp.228~236 (1986)
  19. 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)
  20. A. J. W. Hilton, "Some intersection theorems for systems of finite sets", Quart. J. Math. Oxford (2), 18, pp.369~384 (1967)
  21. A. J. W. Hilton, "A graph-theoretical generalisation of Berges analogue of the Erd˝os-Ko-Rado theorem, Trends in Graph Theory", pp.225~242 (2006), Birkhauser Verlag
  22. F. C. Holroyd, "Compression and Erd˝os-Ko-Rado graphs", Discrete Math, 293(1-3), pp.155~164 (2005)
  23. F. C. Holroyd, "Graphs with the Erd˝os-Ko-Rado property", Discrete Math, 293(1-3), pp.165~176 (2005)
  24. G. Hurlbert, "Erd˝os-Ko-Rado theorems for chordal graphs and trees", J. Combin. Theory Ser. A, 118(3), pp.829~841 (2011)
  25. P. Keevash, "Shadows and intersections: Stability and new proofs", Adv.Math, 218(5), pp.1685~1703 (2008)
  26. C. Y. Ku, "An Erd˝os-Ko-Rado theorem for partial permutations", Discrete Math, 306(1), pp.74~86 (2006)
  27. C. Y. Ku, "Erd˝os-Ko-Rado theorems for permutations and set partitions", J. Combin. Theory Ser. A, 115(6), pp.1008~1020 (2008)
  28. C. Y. Ku, "On cross-intersecting families of set partitions", Electron. J. Combin, 19(4), pp.9~ (2012)
  29. C. Y. Ku, "On r-cross intersecting families of sets", Far East J. Math. Sci, 75, pp.295~300 (2013)
  30. C. Y. Ku, "An analogue of the Erd˝os-Ko-Rado theorem for weak compositions", Discrete Math, 313, pp.2463~2468 (2013)
  31. C. Y. Ku, "An analogue of Hilton-Milner theorem for set partitions", J. Combin. Theory Ser. A, 120, pp.1508~1520 (2013)
  32. C. Y. Ku, "On r-cross t-intersecting families for weak compositions", ~
  33. C. Y. Ku, "An Erd˝os-Ko-Rado theorem for permutations with fixed number of cycles", Electron. J. Combin, 21(3), pp.3~16 (2014)
  34. C. Y. Ku, "Intersecting families in the alternating group and direct product of symmetric groups", Electron. J. Combin, 14(3), pp.9~ (2007)
  35. B. Larose, "Stable sets of maximal size in Kneser-type graphs", European J. Combin, 25(5), pp.657~673 (2004)
  36. Y.-S. Li, "Erd˝os-Ko-Rado-type theorems for colored sets", Electron. J. Combin, 14(1), pp.9~ (2007)
  37. 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)
  38. 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)
  39. L. Pyber, "A new generalization of the Erd˝os-Ko-Rado theorem", J. Combin. Theory Ser. A, 43(1), pp.85~90 (1986)
  40. N. Tokushige, "A product version of the Erd˝os-Ko-Rado theorem", J. Combin. Theory Ser. A, 118(5), pp.1575~1587 (2011)
  41. J. Wang, "Cross-intersecting families and primitivity of symmetric sys-tems", J. Combin. Theory Ser. A, 118(2), pp.455~462 (2011)
  42. J. Wang, "An Erd˝os-Ko-Rado-type theorem in Coxeter groups", European J. Combin, 29(5), pp.1112~1115 (2008)
  43. R. M. Wilson, "The exact bound in the Erd˝os-Ko-Rado theorem", Combinatorica, 4(2-3), pp.247~257 (1984)
  44. R. Woodroofe, "Erd˝os-Ko-Rado theorems for simplicial complexes", J. Combin. Theory Ser. A, 118(4), pp.1218~1227 (2011)

관련 논문AI추천

An analogue of the Erd{\H o}s matching conjecture for weak compositionsCheng Yeaw Ku, Kok Bin Wong대한수학회 · 대한수학회보2025 · 제62권 제5호An Erdos-Ko-Rado theorem for minimal coversCheng Yeaw Ku, Kok Bin Wong대한수학회 · 대한수학회보2017 · 제54권 제3호On diversity of certain t-intersecting familiesCheng Yeaw Ku, Kok Bin Wong대한수학회 · 대한수학회보2020 · 제57권 제4호A note on Snevily's conjecture in set systems김연진, 황경원, Rudy X. J. Liu장전수학회 · Advanced Studies in Contemporary Mathematics2017 · 제27권 제1호2-COLOR RADO NUMBER FOR x1 + x2 + · · · + xn = y1 + y2 = z김병문, 송병철, 황운재강원경기수학회 · 한국수학논문집2020 · 제28권 제2호Some remarks on sumsets and restricted sumsetsMin Tang, Wenhui Wang대한수학회 · 대한수학회보2019 · 제56권 제3호

이 간행물의 다른 논문 (28건)

THE FUNDAMENTAL THEOREM OF ALGEBRA AND THE DIVERGENCE OF RECIPROCALS OF PRIMES LOOKED AT THROUGH BERGMAN SPACESYunus E. Zeytuncupp. 699-705GENERALIZATION OF INEQUALITIES ANALOGOUS TO HERMITE–HADAMARD INEQUALITY VIA FRACTIONAL INTEGRALSKiran Nazeer, Muhammad Iqbal, Muhammad Iqbal Bhattipp. 707-716CLASSIFICATION ON ARITHMETIC FUNCTIONS AND CORRESPONDING FREE-MOMENT L-FUNCTIONS조일우pp. 717-734AN ESTIMATE OF HEMPEL DISTANCE FOR BRIDGE SPHERESAyako Idopp. 735-740THE n-TH TWISTED CHANGHEE POLYNOMIALS AND NUMBERS권종겸, 표성수, 박진우, 임석훈pp. 741-749
원문 보기