<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 9 Issue 2" %>
Non-Trivial t-Intersection in the Function Lattice
Péter L. Erdős1, Ákos Seress2 and László A. Székely3
1A. Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, P.O. Box 127 1364, Hungary
elp@renyi.hu
2Department of Mathematics, The Ohio State University, Columbus, OH 43210, USA
akos@math.ohio-state.edu
3Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA
szekely@math.sc.edu
Annals of Combinatorics 9 (2) p.177-187 June, 2005
AMS Subject Classification: 05D05
Abstract:
The function lattice, or generalized Boolean algebra, is the set of -tuples with the ith coordinate an integer between 0 and a bound ni. Two -tuples t-intersect if they have at least t common nonzero coordinates. We prove a Hilton-Milner type theorem for systems of t-intersecting -tuples.
Keywords: generalized Boolean algebra, intersecting chains, Erdős-Ko-Rado theorem, Hilton- Milner theorem, kernel method

References:

1. R. Ahlswede and L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121--138.

2. R. Ahlswede and L.H. Khachatrian, The complete intersection theorem for systems of finite sets, Europ. J. Combin. 18 (1997) 125--136.

3. R. Ahlswede and L.H. Khachatrian, The diametric theorem in hamming spaces-optimal anticodes, Adv. Appl. Math. 20 (1998) 429--449.

4. C. Berge, Nombres de coloration de l'hypergraphe h-parti complet, Hypergraph Seminar, In: Proceedings of the First Working Seminar on Hypergraphs, 1972, C. Berge and D. Ray- Chaudhuri, Eds., Lect. Notes in Math. Vol. 411. Springer-Verlag, Berlin-New York (1974) pp. 13--20.

5. C. Bey, The Erdős-Ko-Rado bound for the function lattice, Discrete Appl. Math. 95 (1999) 115--125.

6. C. Bey, An intersection theorem for weighted sets, Discrete Math. 235 (2001) 145--150.

7. C. Bey and K. Engel, Old and new results for the weighted t-intersection problem via AKmethods, In: Numbers, Information and Complexity, Althöfer, Ingo, Eds. et al., Dordrecht: Kluwer Academic Publishers (2000) pp. 45--74.

8. B. Bollobás, Sperner systems consisting of pairs of complementary subsets, J. Combin. Theory Ser. A 15 (1973) 363--366.

9. M. Deza and P. Frankl, Erdős-Ko-Rado theorem -- 22 years later, SIAM J. Alg. Disc. Methods 4 (1983) 419--431.

10. K. Engel, An Erdős-Ko-Rado theorem for the subcubes of a cube, Combinatorica 4 (1984) 133--140.

11. P. Erdős, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961) 313--320.

12. P.L. Erdős, U. Faigle, and W. Kern, A group-theoretic setting for some intersecting Sperner families, Combin. Probab. Comput. 1 (1992) 323--334.

13. P.L. Erdős, Á. Seress, and L.A. Székely, Erdős-Ko-Rado and Hilton-Milner type theorems for intersecting chains in posets, Combinatorica 20 (2000) 27--45.

14. P. Frankl and Z. Füredi, The Erdős-Ko-Rado theorem for integer sequences, SIAM J. Alg. Disc. Methods 1 (1980) 376--381.

15. P. Frankl and N. Tokushige, The Erdős-Ko-Rado theorem for integer sequence, Combinatorica 19 (1999) 55--63.

16. H-D.O.F. Gronau, More on the EKR theorem for integer sequences, J. Combin. Theory Ser. A 35 (1983) 279--288.

17. A. Hajnal and B. Rothschild, A generalization of the Erdős-Ko-Rado theorem on finite set systems, J. Combin. Theory Ser. A 15 (1973) 359--362.

18. A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 18 (1967) 369--384.

19. W.N. Hsieh, Systems of finite vector spaces, Discrete Math. 12 (1975) 1--16.

20. D. Kleitman, On a combinatorial conjecture of Erdős, J. Combin. Theory 1 (1966) 209--214.

21. M.L. Livingston, An ordered version of the Erdős-Ko-Rado theorem, J. Combin. Theory Ser. A 26 (1979) 162--165.

22. A. Moon, An analogue of Erdős-Ko-Rado theorem for hamming schemes H(n,q), J. Combin. Theory Ser. A 32 (1982) 386--390.