Erd(?)s-Ko-Rado定理相关问题研究
|
摘要
Erdos-Ko-Rado(简称EKR)定理涉及子集格的交的性质,是研究有限集的交族的最早结果,也是组合极值理论中最经典的结论之一。在过去的几十年间,许多学者研究了EKR定理及其各种推广,给出了EKR定理在其他偏序集上的模拟和极值结构的刻画。本文中我们讨论了EKR定理的一些推广,研究了多重集上的EKR定理。此外,利用所得结果我们给出了极值理论中一些已知结果的简洁证明。
全文共分为五章,具体内容概括如下。
第一章我们介绍了与EKR定理相关的一些基本结果,包括定理的内容及发展历史。
第二章我们着重阐述了EKR定理的若干经典证明方法：移位算子法、投影法、圈序法等其他经典方法。
第三章我们研究了EKR定理在反链和多重集上的推广。利用所得结果我们给出了极值理论中一些著名定理的简洁证明。
第四章我们讨论了EKR定理在单射集上的模拟。
第五章我们介绍了EKR定理的应用和研究方向。
The Erdos-Ko-Rado (EKR) theorem, which deals with the intersecting property in the lattice of subset, is the earliest result in researching the intersecting families of a finite set. It is also one of the most famous results in extreme set theory. In the past fifty years, The EKR theorem has been extended, simulated and refined.
In this thesis, we present some other extensions of the EKR theorem under certain conditions, and study the theorem on multisets. Moreover, we give simple proofs for several famous theorems in extreme set theory by using our results. The main content of this thesis is arranged as follows.
In Chapter1, we present some basic results about the EKR theorem, including background of the theorem.
In Chapter2, we focus describing several proving methods of the EKR theorem.
In Chapter3, we investigate the extension of the EKR theorem on antichains and multisets. At the same time, we give simple proofs for several famous theorems in extreme set theory by using the obtained results.
In Chapter4, we explore simulations of the EKR theorem on the injection collection.
In Chapter5, we present some applications of the EKR theorem.
全文共分为五章,具体内容概括如下。
第一章我们介绍了与EKR定理相关的一些基本结果,包括定理的内容及发展历史。
第二章我们着重阐述了EKR定理的若干经典证明方法：移位算子法、投影法、圈序法等其他经典方法。
第三章我们研究了EKR定理在反链和多重集上的推广。利用所得结果我们给出了极值理论中一些著名定理的简洁证明。
第四章我们讨论了EKR定理在单射集上的模拟。
第五章我们介绍了EKR定理的应用和研究方向。
The Erdos-Ko-Rado (EKR) theorem, which deals with the intersecting property in the lattice of subset, is the earliest result in researching the intersecting families of a finite set. It is also one of the most famous results in extreme set theory. In the past fifty years, The EKR theorem has been extended, simulated and refined.
In this thesis, we present some other extensions of the EKR theorem under certain conditions, and study the theorem on multisets. Moreover, we give simple proofs for several famous theorems in extreme set theory by using our results. The main content of this thesis is arranged as follows.
In Chapter1, we present some basic results about the EKR theorem, including background of the theorem.
In Chapter2, we focus describing several proving methods of the EKR theorem.
In Chapter3, we investigate the extension of the EKR theorem on antichains and multisets. At the same time, we give simple proofs for several famous theorems in extreme set theory by using the obtained results.
In Chapter4, we explore simulations of the EKR theorem on the injection collection.
In Chapter5, we present some applications of the EKR theorem.
引文
[1]I. Anderson. Combinatorics of Finite Sets [M]. New York:Oxford University Press, 1987.
[2]E. Sperner. Ein Satz uber Untermengen einer endlichen Menge [J]. Math. Z.,1928, 27:327-330.
[3]P. Erdos, C. Ko and R. Rado. Intersection theorems for systems of finite sets, Quart. [J]. Math Oxford Ser,1961,2:313-318.
[4]R. M. Wilson. The exact bound in the Erdos-Ko-Rado theorem [J]. Combinatorica,1984, 4:247-257.
[5]R. Ahlswede, L. H. Khachatrian. The complete intersection theorem for systems of finite sets [J]. European J. Combin.1997,18:125-136.
[6]W. N. Hsieh. Intersection theorems for systems of finite vector spaces [J]. Discrete Math.,1975,12:1-16.
[7]M. L. Livingston. An ordered version of Erdos-Ko-Rado theorem [J]. Combin. Theory Ser. A,1979,26:162-165.
[8]J. Wang. Erdos-Ko-Rado-type theorems for colored sets [J]. Electron. J. Combin. 2007,14.
[9]J. H. Sperner. Agereralized Rota conjecture for partitions [J]. Stud. Appl. Math. 1974,53:239-241.
[10]P. Erdos. My joint work with Richard Rado [R]. Surveys in combinatorics 1987, London Math. Soc. Lecture Note Ser.,123,53-80, Cambridge Univ. Press, Cambridge,1987.
[11]G.O. H. Katona. A simple proof of the Erdos-Ko-Rado theorem [J]. J. Combin Theory Ser. B,1972,13,183-184.
[12]R. Ahlswede, L. H. Khachatrian. The complete nontrivial-intersection theorem for systems of finite sets [J]. Combin. Theory Ser. A,1996,76:121-138.
[13]A. J. W. Hilton, E. C. Milner. Some intersection theorems for systems of finite sets. Quart. [J]. Math. Oxford,1967,18:369-384.
[14]J. B. Kruskal. The number of simplices in a complex [J]. Mathematical Optimization Techniques,1963:251-278
[15]G.O. H. Katona. A theorem of finite set [J]. Theory of Graphs,1966:187-207
[16]L. Lovasz. Combinatorial problem and exercises [M]. Amsterdam-New York: North-Holland Publishing Co.,1979.
[17]P. Frankl. A new short proof for the Kruskal-Katona theorem [J]. Discrete Math, 1984,48:327-329.
[18]D. E. Daykin. Erd6s-Ko-Rado from Kruskal-Katona [J]. Combin. Theory Ser. A,1974, 17:254-255.
[19]G.O. H. Katona. Intersection theorems for systems of finite sets [J]. Acta Math. Acad. Sci. Hungar,1964,15:329-337.
[20]P. Frankl, Z. Furedi. A new short proof of the EKR theorem [J].arXiv:1108.2179.
[21]E. C. Milner. A combinatorial theorem on systems of sets [J]. J. London Math. Soc. 1968,43:204-206.
[22]B. Bollobas. Sperner systems consisting of pairs of complementary subsets[J]. Combin. Theory Ser. A.1973,15:363-366.
[23]Brace, Alan and D. E. Daykin, A finite set covering theorem [J]. Bull. Austral. Math. Soc.1972,6:417-433.
[24]K. Meagher, A. Purdy. An Erdos-Ko-Rado theorem for multisets [J]. Electron. J. Combin.,2011,18:#P220.
[25]P. Delsarte. An algebraic approach to the association schemes of coding theory [R]. Philips Res.Reports Suppl.1973,10.
[26]W. Haemers. Eigenvalue methods, in:Packing and Covering in Combinatorics (A. Schrijver, ed.) [J]. Tract 106, Mathematical Centre, Amsterdam 1979.
[27]A. Schrijver. Association schemes and the Shannon capacity:Eberlein polynomials and the Erdos-Ko-Rado Theorem [J]. Algebraic Methods in Graph Theory, Proc. Sixth Hungarian Coll. Combinatorics, Szeged,1978, Colloquia Mathematica Societatis, Janos Bolyai,671-688.
[28]P. Frankl, R. M. Wilson. The Erdos-Ko-Rado theorem for vector spaces [J]. Combin Theory Ser. A,1986,43(2):228-236.
[29]M. Deza, P. Frankl. On the maximum number of permutations with given maximal or minimal distance [J]. Combin. Theory Ser. A,1977,22:352-362.
[30]P. J. Cameron, C. Y. Ku. Intersecting families of permutations [J]. European J. Combin.,2003,24:881-890.
[31]P. Frankl, Z. Furedi. The Erdos-Ko-Rado theorem for integer sequences [J]. SIAM J. Algebraic Discrete Nlath,1980,1:376-381.
[32]P. Frankl, N. Tokushige, The Erd6s-Ko-R. ado theorem for integer sequences[J], Combinatorica,1999,19:55-63.
[33]C. Berce. Nombres de coloration de 1'hypergraphe h-parti complet [J]. (French) Hypergraph seminar, Columbus, Ohio,1972, Springer-Verlag, New York,1974, pp.13-20.
[34]M. L. Livingston. An ordered version of the Erd6s-Ko-Rado theorem [J]. Combin. Theory, Ser. A,1979,26:162-165.
[35]A. Moon. An analogue of the Erdos-Ko-Rado theorem for the hamming schemes h(n, q) [J]. Combin. Theory Ser. A,1982,32:386-390.
[36]B. M. I. Rands. An extension of the Erdos-Ko-Rado theorem to t-designs [J]. Combin. Theory Ser. A,1982,32:391-395.
[37]B. Bollobas, Imre Leader. Matchings and Paths in the Cube [J]. Discrete Applied Mathematics,1997,75(1):1-8.
[38]R. Ahlswede, H. Aydinian, L. H. Khachatrian. The intersection theorem for direct products, European [J]. Combin,1998,19:649-661.
[39]C. Bey. The Erdos-Ko-Rado bound for the function lattice [J]. Discrete,4ppl. Math.,1999,95:115-125.
[40]C. Bey. An intersection theorem for weighted sets [J]. Discrete Math.,2001,235: 145-150.
[41]C. Y. Ku. Intersecting families of permutations and partial permutations [J]. Ph. D. Thesis Queen Mary, University of London, London,2004.
[42]K. Meagher, L. Mourn. Erdos-Ko-Rado theorems for uniform set-partition systems [J]. Combin,2005,12:#R40.
[43]M. Deza, P. Frankl. Erdos-Ko-Rado theorem-22 years later [J]. SIAM J. Algebraic Discrete Methods,1983,4:419-431.
[44]F. Holroyd, J. Talbot. Graphs with the Erdos-Ko-Rado property [J]. Discrete Math., 2005,293:165-176.
[45]C. Y. Ku, D. Renshaw. Erdos-Ko-Rado theorems for permutations and set partitions [J]. Journal of Combinatorial Theory, Series A 2008,115:1008-1020.
[46]张俊.偏序集的Erdos-Ko-Rado性质及相关问题[D].大连：大连理工大学,2008.
[2]E. Sperner. Ein Satz uber Untermengen einer endlichen Menge [J]. Math. Z.,1928, 27:327-330.
[3]P. Erdos, C. Ko and R. Rado. Intersection theorems for systems of finite sets, Quart. [J]. Math Oxford Ser,1961,2:313-318.
[4]R. M. Wilson. The exact bound in the Erdos-Ko-Rado theorem [J]. Combinatorica,1984, 4:247-257.
[5]R. Ahlswede, L. H. Khachatrian. The complete intersection theorem for systems of finite sets [J]. European J. Combin.1997,18:125-136.
[6]W. N. Hsieh. Intersection theorems for systems of finite vector spaces [J]. Discrete Math.,1975,12:1-16.
[7]M. L. Livingston. An ordered version of Erdos-Ko-Rado theorem [J]. Combin. Theory Ser. A,1979,26:162-165.
[8]J. Wang. Erdos-Ko-Rado-type theorems for colored sets [J]. Electron. J. Combin. 2007,14.
[9]J. H. Sperner. Agereralized Rota conjecture for partitions [J]. Stud. Appl. Math. 1974,53:239-241.
[10]P. Erdos. My joint work with Richard Rado [R]. Surveys in combinatorics 1987, London Math. Soc. Lecture Note Ser.,123,53-80, Cambridge Univ. Press, Cambridge,1987.
[11]G.O. H. Katona. A simple proof of the Erdos-Ko-Rado theorem [J]. J. Combin Theory Ser. B,1972,13,183-184.
[12]R. Ahlswede, L. H. Khachatrian. The complete nontrivial-intersection theorem for systems of finite sets [J]. Combin. Theory Ser. A,1996,76:121-138.
[13]A. J. W. Hilton, E. C. Milner. Some intersection theorems for systems of finite sets. Quart. [J]. Math. Oxford,1967,18:369-384.
[14]J. B. Kruskal. The number of simplices in a complex [J]. Mathematical Optimization Techniques,1963:251-278
[15]G.O. H. Katona. A theorem of finite set [J]. Theory of Graphs,1966:187-207
[16]L. Lovasz. Combinatorial problem and exercises [M]. Amsterdam-New York: North-Holland Publishing Co.,1979.
[17]P. Frankl. A new short proof for the Kruskal-Katona theorem [J]. Discrete Math, 1984,48:327-329.
[18]D. E. Daykin. Erd6s-Ko-Rado from Kruskal-Katona [J]. Combin. Theory Ser. A,1974, 17:254-255.
[19]G.O. H. Katona. Intersection theorems for systems of finite sets [J]. Acta Math. Acad. Sci. Hungar,1964,15:329-337.
[20]P. Frankl, Z. Furedi. A new short proof of the EKR theorem [J].arXiv:1108.2179.
[21]E. C. Milner. A combinatorial theorem on systems of sets [J]. J. London Math. Soc. 1968,43:204-206.
[22]B. Bollobas. Sperner systems consisting of pairs of complementary subsets[J]. Combin. Theory Ser. A.1973,15:363-366.
[23]Brace, Alan and D. E. Daykin, A finite set covering theorem [J]. Bull. Austral. Math. Soc.1972,6:417-433.
[24]K. Meagher, A. Purdy. An Erdos-Ko-Rado theorem for multisets [J]. Electron. J. Combin.,2011,18:#P220.
[25]P. Delsarte. An algebraic approach to the association schemes of coding theory [R]. Philips Res.Reports Suppl.1973,10.
[26]W. Haemers. Eigenvalue methods, in:Packing and Covering in Combinatorics (A. Schrijver, ed.) [J]. Tract 106, Mathematical Centre, Amsterdam 1979.
[27]A. Schrijver. Association schemes and the Shannon capacity:Eberlein polynomials and the Erdos-Ko-Rado Theorem [J]. Algebraic Methods in Graph Theory, Proc. Sixth Hungarian Coll. Combinatorics, Szeged,1978, Colloquia Mathematica Societatis, Janos Bolyai,671-688.
[28]P. Frankl, R. M. Wilson. The Erdos-Ko-Rado theorem for vector spaces [J]. Combin Theory Ser. A,1986,43(2):228-236.
[29]M. Deza, P. Frankl. On the maximum number of permutations with given maximal or minimal distance [J]. Combin. Theory Ser. A,1977,22:352-362.
[30]P. J. Cameron, C. Y. Ku. Intersecting families of permutations [J]. European J. Combin.,2003,24:881-890.
[31]P. Frankl, Z. Furedi. The Erdos-Ko-Rado theorem for integer sequences [J]. SIAM J. Algebraic Discrete Nlath,1980,1:376-381.
[32]P. Frankl, N. Tokushige, The Erd6s-Ko-R. ado theorem for integer sequences[J], Combinatorica,1999,19:55-63.
[33]C. Berce. Nombres de coloration de 1'hypergraphe h-parti complet [J]. (French) Hypergraph seminar, Columbus, Ohio,1972, Springer-Verlag, New York,1974, pp.13-20.
[34]M. L. Livingston. An ordered version of the Erd6s-Ko-Rado theorem [J]. Combin. Theory, Ser. A,1979,26:162-165.
[35]A. Moon. An analogue of the Erdos-Ko-Rado theorem for the hamming schemes h(n, q) [J]. Combin. Theory Ser. A,1982,32:386-390.
[36]B. M. I. Rands. An extension of the Erdos-Ko-Rado theorem to t-designs [J]. Combin. Theory Ser. A,1982,32:391-395.
[37]B. Bollobas, Imre Leader. Matchings and Paths in the Cube [J]. Discrete Applied Mathematics,1997,75(1):1-8.
[38]R. Ahlswede, H. Aydinian, L. H. Khachatrian. The intersection theorem for direct products, European [J]. Combin,1998,19:649-661.
[39]C. Bey. The Erdos-Ko-Rado bound for the function lattice [J]. Discrete,4ppl. Math.,1999,95:115-125.
[40]C. Bey. An intersection theorem for weighted sets [J]. Discrete Math.,2001,235: 145-150.
[41]C. Y. Ku. Intersecting families of permutations and partial permutations [J]. Ph. D. Thesis Queen Mary, University of London, London,2004.
[42]K. Meagher, L. Mourn. Erdos-Ko-Rado theorems for uniform set-partition systems [J]. Combin,2005,12:#R40.
[43]M. Deza, P. Frankl. Erdos-Ko-Rado theorem-22 years later [J]. SIAM J. Algebraic Discrete Methods,1983,4:419-431.
[44]F. Holroyd, J. Talbot. Graphs with the Erdos-Ko-Rado property [J]. Discrete Math., 2005,293:165-176.
[45]C. Y. Ku, D. Renshaw. Erdos-Ko-Rado theorems for permutations and set partitions [J]. Journal of Combinatorial Theory, Series A 2008,115:1008-1020.
[46]张俊.偏序集的Erdos-Ko-Rado性质及相关问题[D].大连：大连理工大学,2008.