Acta Mathematicae Applicatae Sinica, English Series 2012, Vol. 28 Issue (1) :127-130    DOI: 10.1007/s10255-012-0128-8
 ARTICLES Adv Search << | >>
Erdos-Ko-Rado Theorems of Labeled Sets
Xing-bo GENG1, Yu-shuang LI2
1. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China;
2. School of Science, Yanshan University, Qinhuangdao 066004, China
 Download: PDF (1KB)   HTML (1KB)   Export: BibTeX or EndNote (RIS)      Supporting Info
Abstract For k = (k1, … , kn) ∈ Nn, 1 ≤ k1 ≤ … ≤ kn, let Lkr be the family of labeled r-sets on k given by Lkr := {{(a1, la1), … , (ar, lar)} : {a1, … , ar} ⊆ [n], lai ∈ [kai], i = 1, … , r}. A family A of labeled r-sets is intersecting if any two sets in A intersect. In this paper we give the sizes and structures of intersecting families of labeled r-sets.
 Service Email this article Add to my bookshelf Add to citation manager Email Alert RSS Articles by authors
KeywordsErdos-Ko-Rado theorem   labeled set   intersecting family
Abstract： For k = (k1, … , kn) ∈ Nn, 1 ≤ k1 ≤ … ≤ kn, let Lkr be the family of labeled r-sets on k given by Lkr := {{(a1, la1), … , (ar, lar)} : {a1, … , ar} ⊆ [n], lai ∈ [kai], i = 1, … , r}. A family A of labeled r-sets is intersecting if any two sets in A intersect. In this paper we give the sizes and structures of intersecting families of labeled r-sets.
  Berge, C. Nombres de coloration de 1’hypegraphe h-parti complet. In: Hypergraph Seminar (Columbus, Ohio 1972), Lecture Notes in Math., Vol. 411, Springer-Verlag, Berlin, 1974 Bollobas, B., Leader I. An Erd?s-Ko-Rado theorem for signed sets. Comput. Math. Appl., 34: 9-13 (1997)  Borg, P. Intersecting and cross-intersecting families of labelled sets. Electron. J. Combin., 15: N9 (2008)  Deza, M., Frankl, P. Erd?s-Ko-Rado theorem-22 years later. SIAM J. Alg. Disc. Methods, 4: 419-431 (1983)  Engel, K. An Erd?s-Ko-Rado theorem for the subcubes of a cube. Combinatorica, 4: 133-140 (1984)  Erd?s, P., Ko, C., Rado, R. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser., 2: 313-318 (1961)  Erd?s, P.L., Faigle, U., Kern, W. A group-theoretic setting for some intersecting Sperner families. Combin. Probab. Comput., 1: 323-334 (1992)  Hilton, A.J.W., Milner, E.C. Some intersection theorems for systems of finite sets. Quart. J. Math. Oxford, 18: 369-384 (1967)  Holroyd, F.C., Spencer, C., Talbot, J. Compression and Erd?s-Ko-Rado graphs. Discrete Math., 293: 155-164 (2005)  Katona, G.O.H. A simple proof of the Erd?s-Ko-Rado theorem. J. Combin. Theory Ser. B, 13: 183-184 (1972)  Livingston, M.L. An ordered version of the Erd?s-Ko-Rado theorem. J. Combin. Theory Ser. A, 26: 162-165 (1979)  Meyer, J.C. Quelques problemes concernant les cliques des hypergraphes k-complets et q-parti h-complets. In: Hypergraph Seminar (Columbus, Ohio 1972), Lecture Notes in Math., Vol.411, Springer-Verlag, Berlin, 1974 