Sperner理论中的交、反链的极值问题
|
摘要
组合数学是数学的一个分支,它用来按一定的规则选择和安排事物。极值集合论研究的是有限集上的组合问题,它是组合数学中的一个重要分支。极值集合论是从1928年Sperner给出的著名的Sperner定理发展起来的,此后许多著名数学家如Dilworth、Katona、Kleitman等对此类问题进行了大量的研究,并给出了许多经典的结果。1961年Erdos,Ko和Rado得到的关于交反链的E-K-R定理就是其中最重要的结果之一。到目前为止已有大量的文献涉及了E-K-R定理的模拟、推广及应用。1968年Milner对交反链的交性质通过引入一个参数,得到了一个经典的结果;1980年Lih又给出了限制在子集上的Sperner定理。
本文结合Milner和Lih的结果,通过引入两个参数考察了一般的限制在子集上的交反链的极值问题,并且给出了几个相关的推论。此外,还将限制在子集上的交反链的极值应用到限制在子集上的互补的Sperner簇中,并得到了相应的结果。
本文安排如下:
第一章简要介绍了极值集合论(Sperner理论)的相关概念及术语,并概述了Sperner理论的研究意义及相关进展。
第二章首先介绍了对子集簇中的子集的模有所限制的交反链的极值的研究结果;接着是对模不加限制的交反链极值的研究;而后介绍对限制在子集上的交反链的极值的研究;最后,基于限制在子集上的一般交反链的研究所得结果,得出了几个限制在子集上的特殊交反链和两类限制在子集上的Sperner簇的极值。
第三章用超图的语言描述了一些典型的极值问题。
The research of extremal set theory is devoted to combinatorical problems of finite sets, and it is one of the most important branches in Combinatorics. Extremal set theory can be traced back to the famous Sperner theory which was given by the well known mathematician Sperner in the year 1928. From then on, many mathematicians such as Dilworth, Katona, Kleitman etc spent much time on this kind of problems and gave many classical results. The E-K-R theorem on intersecting Sperner families which was given by Erdos, Ko and Rado in 1961 is one of the most important results. Later on, there are a lot of references on the anolog, generalization and application of the E-K-R theorem. In 1968, Milner gave a classical result by drawing a prameter into intersecting Sperner families ; in 1980, Lih gave Sperner theorem over a subset.In this thesis we combine the results of Milner and Lih, led into two parameters and investigated the general intersecting Sperner families over a subset and several corollaries related to the problem as well. Besides, we apply the above results to complemented Sperner families over a subset.The first section of this thesis simply introduces some conceptions of extremal set theory and states the research meaning and developments of Sperner theory.In the second section, we mainly introduce all kinds of extremal problems of intersecting Sperner families.In the last section we state some typical extremal problems in hypergraph language.
本文结合Milner和Lih的结果,通过引入两个参数考察了一般的限制在子集上的交反链的极值问题,并且给出了几个相关的推论。此外,还将限制在子集上的交反链的极值应用到限制在子集上的互补的Sperner簇中,并得到了相应的结果。
本文安排如下:
第一章简要介绍了极值集合论(Sperner理论)的相关概念及术语,并概述了Sperner理论的研究意义及相关进展。
第二章首先介绍了对子集簇中的子集的模有所限制的交反链的极值的研究结果;接着是对模不加限制的交反链极值的研究;而后介绍对限制在子集上的交反链的极值的研究;最后,基于限制在子集上的一般交反链的研究所得结果,得出了几个限制在子集上的特殊交反链和两类限制在子集上的Sperner簇的极值。
第三章用超图的语言描述了一些典型的极值问题。
The research of extremal set theory is devoted to combinatorical problems of finite sets, and it is one of the most important branches in Combinatorics. Extremal set theory can be traced back to the famous Sperner theory which was given by the well known mathematician Sperner in the year 1928. From then on, many mathematicians such as Dilworth, Katona, Kleitman etc spent much time on this kind of problems and gave many classical results. The E-K-R theorem on intersecting Sperner families which was given by Erdos, Ko and Rado in 1961 is one of the most important results. Later on, there are a lot of references on the anolog, generalization and application of the E-K-R theorem. In 1968, Milner gave a classical result by drawing a prameter into intersecting Sperner families ; in 1980, Lih gave Sperner theorem over a subset.In this thesis we combine the results of Milner and Lih, led into two parameters and investigated the general intersecting Sperner families over a subset and several corollaries related to the problem as well. Besides, we apply the above results to complemented Sperner families over a subset.The first section of this thesis simply introduces some conceptions of extremal set theory and states the research meaning and developments of Sperner theory.In the second section, we mainly introduce all kinds of extremal problems of intersecting Sperner families.In the last section we state some typical extremal problems in hypergraph language.
引文
[1] I. Anderson. Combinatorics of Finite Sets(Oxford University Press, Oxford, 1989).
[2] B. Bollobas. On general graaphs. Acta Math. Aead. Sci. Hung. 16,447-452, 1965.
[3] B. Bollobas. Sperner systems consisting of pairs of complementary subsets. J. Combin. Theory Set. A 15(1973), 363-366.
[4] A. Brace, D. E. Daykin. Sperner type theorems for finite sets. Proc. Br. Combin. Conf.,Oxford, 1972.pp.18-37. Institute of Mathematics and its Applications. Southend-On-Sea.
[5] E. R. Canfield. Matching in the partition lattice. SIAM J. Discrete Math., 6(1993), 100-109.
[6] G. F. Clements. Intersection theorems for sets of subsets of a finite sets. Q. J. Math. Oxf. (2)27(1976), 325-337
[7] Crapo, G. C. Rota. "Combinatorial Geometries". M. I. T. Press, Cambridge, 1971.
[8] D. E. Daykin, L. Lovasz. On the number of values of a Boolean function.——
[9] EHRENFEUCHT, A. and J. MYCIELSKI.——
[10] P. Erdos. On a lemma of littlewood and offord. Bull. Amer. Math. Soci. 51(1945), 898-902.
[11] P. Erdos, Chao Ko, R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford (2)12(1961), 313-318.
[12] P. L. Erdos, G. O. H. Katona. Convex hulls of more part Sperner families. Graphs Combin. 2(1986), 123-134.
[13] P. L. Erdos, G. O. H. Katona. An maximum 2-part Sperner families. J. Combin. Theory A 43(1986), 58-69.
[14] P. Frankl. On Sperner families satisfying an additional conditions, J. Combin. Theory A 20(1976), 1-11.
[15] P. Frankl. An extremal problems for two families of sets. Eur. J. Combin. 3,125-127,1982.
[16] P. Frankl, Z. Puredi. The Erdos-Ko-Rado theorem for integer sequences. SIAM J. Algebraic Discrete Math. 1(1980), 376-381.
[17] Z. Furedi, J. R. Griggs, A. M. Odlyzko, J.B. Shearer. Ramsey-Sperner theory. Discrete Math. 63(1987), 145-152.
[18] C. Greene, A. J. W. Hilton. Some results on Sperner families. J. Combin. Theory Ser. A 26(1979), 202-209.
[19] C. Greene, D. J. Kleitman. Proof techniques in the theory of finite sets. in: G. Rota, ed.,studies in Combinatorics (The Mathematical Association of America, 1978), 22-28.
[20] C. Greene, G. Katona, D. J. Kleitman. Extensions of the Erdos, Ko, Rado theorem." Recent Advances in Graph Theory" (Proc. Symposium in Prague, 1974 ),pp. 223-237, Academica Praha, 1975.
[21] C. Greene, G. Katona, D. J. Kleitman. Extensions of the Erdos, Ko, Rado theorem. Stud. Appl. Math. 55(1976),l-8.
[22] J. R. Griggs. Collections of subsets with the Sperner property. Trans, Am. Math. Soc. (2)209,(1982), 575-591.
[23] A. Hajnal, B. L. Rothschild. A generalization of the Erdos-Ko-Rado theorem of finite set systems. J. Combin. Theory, 15(1973),359-362.
[24] G. Hansel. Sur le nombre des functions Booleejjes monotones de n variables. C. R. Acad. Sci. Paris 262, 1088-1090.
[25] A. J. W. Hilton. Analogues of a theorem of Erdos, Ko and Rado on a family of finite sets. Quart. J. Math. Oxford (2)-
[26] A. J. W. Hilton. An intersection theorem for two families of finite sets. in:Combinatorial Mathe matics and its applications , Proe.Conf. Oxford 1969, Academic Press, London, 1971, pp.137-148.
[27] A. J. W. Hilton, E. C. Milner. Some intersection theorems for systems of finite sets. Q. J. Math. Oxford.(2)18(1967), 369-384.
[28] W. N. Hsieh. Intersection theorems for systems of finite vector spaces. Discrete Math. 12(1975), 1-16.
[29] M. Huber. 2-part Sperner families of multisets. 1994,-.
[30] G. Kalai. Intersection patterns of convex sets. Isr. J. Math. 48,161-174, 1984.
[31] G. O. H. Katona. A three part Sperner theorem. Stud. Sci. Math. Hung. 8(1973), 379-390.
[32] G. O. H. Katona. On a conjecture of Erdos and strong form of Sperners theorem. Stud. Sci. Hung. 15(1966), 329-337.
[33] G. O. H. Katona. A three part Sperner theorem. Stud. Sci. Math. Hung. 8(1973), 379-390.
[34] G. O. H. Katona. A simple proof of the Erdos-Ko-Rado theorem. J. Combin. Theory B 13(1972), 183-184.
[35] G. O. H. Katona. Intersection theorems for systems of finite sets. Acta. Math. Acad. Sci. Hungar. 15(1964), 329-337.
[36] G. O. H. Katona. A simple proof of a Theorem of Milner. J. Combin. Theory Ser. A 83(1998), 138-140.
[37] G. O. H. Katona. Extremal problems for hypergraphs. Mathematical Centre Tracts, 56(1974), 13-42.
[38] G. O. H. Katona. Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hung 15(1964), 329-337.
[39] G. O. H. Katona. Extremal problems for hypergraphs. Mathematical Centre Tracts, 56(1974), 13-42.
[40] G. O. H. Katona. Two applications of Sperner type theorems ( for search theory and truth functions). Period. Math. Hunger. ,3(1973), 19-26.
[41] G. O. H. Katona. Families of subsets having no subset containing another with small difference. Nieuw Arch. Wisk.(3),20(1972), 54-67.
[42] G. 0. H. Katona. On a conjecture of Ehrenfeucht and Mycielski. J. Combin. Theory A —
[43] D. J. Kleitman. On an extremal property of antichains in partial orders. In Combinatorics (eds.M. Hall and J. H. Van. Lint), Math. Centre Traces 55, 77-90(1974).Mathematics Centre, Amsterdam.
[44] D. J. Kleitman. On a lemma of Littlewood and Offord on the distribution of certain sums. Math. 2. 90(1965), 251-259.
[45] D. J. Kleitman, J. Sperner. Families of k-independent sets. Discrete Math., 6(1973), 255-262.
[46] D. J. Kleitman. Max number of subsets of a finite set no k of which are pairwise disjoint. J. Combin. Theory, 5(1968), 157-163.
[47] D. J. Kleitman. On a conjecture of Milner on K-graphs with nondisjoint edges. J. Combin. Theory, 5(1968), 153-156.
[48] K.-W. Lih. Sperner families over a subset. J. Combin. Theory Ser. A 29(1980), 182-185.
[49] M. L. Livingston. An ordered version of the Erdos-Ko-Roda theorem. J. Combin. Theory A 26(1979), 162-165.
[50] L. Lovasz. Flats in matroids and geometric graphs. In Combinatorics surveys (ed.P.J.Cameron), pp. 45-86, 1977, Academic press, New York.
[51] D. Lubell.A short proof of Sperner's theorem. J. Combin. Th. 1(1966),299.
[52] E. C. Milner. A combinatorial theorem on systems of sets. J. Lond. Math. Soc. 43(1986), 204-206.
[53] A. Moon. An analogue of The Erdos-Ko-Rado theorem for the Hamming Schemes H(n,q). J. Combin. Theory A 32(1982), 386-390.
[54] G. Purdy. A result on Sperner collections. Utilitas Math. 12(1977), 95-99.
[55] B. M. I. Rands. An extension of the Erdos-Ko-Rado theorem to t-designs. J. Combin. Theory A 32(1982), 391-395.
[56] A. Sali. A note on convex hulls of more-pare Sperner families. J. Combin. Theory A 49(1)(1988), 188-190.
[57] N. Sauer. On the density of families of sets. J. Combin. Theory A, 13(1972), 145-147.
[58] J. Schonheim. On a problem of Purdy related to Sperner systems. Can. Math. Bull 17(1974), 135-136.
[59] S. Shahriar. On the structure of maximum 2-part Sperner families. Discrete Mathematics 162(1966), 229-238.
[60] E. Sperner. Ein Satziiber Untermengen ciner endlichen Menge. Math. Z. 27(1928),544-548.
[61] R. P. Stanley. Some applications to algebra to combinarics. Discrete Appl. Math.,34(1991),241-277.
[62] D. Stanton. Some Erdos-Ko-Rodo theorems for chevalley groups. SIAM J. Algebraic Discrete Math. 1(1980),160.
[63] T. Tarjan. Private Communication.
[64] Changyu Wang, Huishan Zhou. A family of inequalities for intersecting antichains of subsets of an n-set. Europ. J. Combinatorics, 17(1996), 89-86.
[65] Y. Wang. On a class of subspace Lattice. J. Math. Research and Exposition, (2)19(1999), 341-348.
[66] H. S. Wilf. Generating functionology. Academic Press, 1990.
[67] R. M. Wilson. The exact bound in the Erdos-Ko-Rado theorem. Combinatorics 4(198), 247-257.
[2] B. Bollobas. On general graaphs. Acta Math. Aead. Sci. Hung. 16,447-452, 1965.
[3] B. Bollobas. Sperner systems consisting of pairs of complementary subsets. J. Combin. Theory Set. A 15(1973), 363-366.
[4] A. Brace, D. E. Daykin. Sperner type theorems for finite sets. Proc. Br. Combin. Conf.,Oxford, 1972.pp.18-37. Institute of Mathematics and its Applications. Southend-On-Sea.
[5] E. R. Canfield. Matching in the partition lattice. SIAM J. Discrete Math., 6(1993), 100-109.
[6] G. F. Clements. Intersection theorems for sets of subsets of a finite sets. Q. J. Math. Oxf. (2)27(1976), 325-337
[7] Crapo, G. C. Rota. "Combinatorial Geometries". M. I. T. Press, Cambridge, 1971.
[8] D. E. Daykin, L. Lovasz. On the number of values of a Boolean function.——
[9] EHRENFEUCHT, A. and J. MYCIELSKI.——
[10] P. Erdos. On a lemma of littlewood and offord. Bull. Amer. Math. Soci. 51(1945), 898-902.
[11] P. Erdos, Chao Ko, R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford (2)12(1961), 313-318.
[12] P. L. Erdos, G. O. H. Katona. Convex hulls of more part Sperner families. Graphs Combin. 2(1986), 123-134.
[13] P. L. Erdos, G. O. H. Katona. An maximum 2-part Sperner families. J. Combin. Theory A 43(1986), 58-69.
[14] P. Frankl. On Sperner families satisfying an additional conditions, J. Combin. Theory A 20(1976), 1-11.
[15] P. Frankl. An extremal problems for two families of sets. Eur. J. Combin. 3,125-127,1982.
[16] P. Frankl, Z. Puredi. The Erdos-Ko-Rado theorem for integer sequences. SIAM J. Algebraic Discrete Math. 1(1980), 376-381.
[17] Z. Furedi, J. R. Griggs, A. M. Odlyzko, J.B. Shearer. Ramsey-Sperner theory. Discrete Math. 63(1987), 145-152.
[18] C. Greene, A. J. W. Hilton. Some results on Sperner families. J. Combin. Theory Ser. A 26(1979), 202-209.
[19] C. Greene, D. J. Kleitman. Proof techniques in the theory of finite sets. in: G. Rota, ed.,studies in Combinatorics (The Mathematical Association of America, 1978), 22-28.
[20] C. Greene, G. Katona, D. J. Kleitman. Extensions of the Erdos, Ko, Rado theorem." Recent Advances in Graph Theory" (Proc. Symposium in Prague, 1974 ),pp. 223-237, Academica Praha, 1975.
[21] C. Greene, G. Katona, D. J. Kleitman. Extensions of the Erdos, Ko, Rado theorem. Stud. Appl. Math. 55(1976),l-8.
[22] J. R. Griggs. Collections of subsets with the Sperner property. Trans, Am. Math. Soc. (2)209,(1982), 575-591.
[23] A. Hajnal, B. L. Rothschild. A generalization of the Erdos-Ko-Rado theorem of finite set systems. J. Combin. Theory, 15(1973),359-362.
[24] G. Hansel. Sur le nombre des functions Booleejjes monotones de n variables. C. R. Acad. Sci. Paris 262, 1088-1090.
[25] A. J. W. Hilton. Analogues of a theorem of Erdos, Ko and Rado on a family of finite sets. Quart. J. Math. Oxford (2)-
[26] A. J. W. Hilton. An intersection theorem for two families of finite sets. in:Combinatorial Mathe matics and its applications , Proe.Conf. Oxford 1969, Academic Press, London, 1971, pp.137-148.
[27] A. J. W. Hilton, E. C. Milner. Some intersection theorems for systems of finite sets. Q. J. Math. Oxford.(2)18(1967), 369-384.
[28] W. N. Hsieh. Intersection theorems for systems of finite vector spaces. Discrete Math. 12(1975), 1-16.
[29] M. Huber. 2-part Sperner families of multisets. 1994,-.
[30] G. Kalai. Intersection patterns of convex sets. Isr. J. Math. 48,161-174, 1984.
[31] G. O. H. Katona. A three part Sperner theorem. Stud. Sci. Math. Hung. 8(1973), 379-390.
[32] G. O. H. Katona. On a conjecture of Erdos and strong form of Sperners theorem. Stud. Sci. Hung. 15(1966), 329-337.
[33] G. O. H. Katona. A three part Sperner theorem. Stud. Sci. Math. Hung. 8(1973), 379-390.
[34] G. O. H. Katona. A simple proof of the Erdos-Ko-Rado theorem. J. Combin. Theory B 13(1972), 183-184.
[35] G. O. H. Katona. Intersection theorems for systems of finite sets. Acta. Math. Acad. Sci. Hungar. 15(1964), 329-337.
[36] G. O. H. Katona. A simple proof of a Theorem of Milner. J. Combin. Theory Ser. A 83(1998), 138-140.
[37] G. O. H. Katona. Extremal problems for hypergraphs. Mathematical Centre Tracts, 56(1974), 13-42.
[38] G. O. H. Katona. Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hung 15(1964), 329-337.
[39] G. O. H. Katona. Extremal problems for hypergraphs. Mathematical Centre Tracts, 56(1974), 13-42.
[40] G. O. H. Katona. Two applications of Sperner type theorems ( for search theory and truth functions). Period. Math. Hunger. ,3(1973), 19-26.
[41] G. O. H. Katona. Families of subsets having no subset containing another with small difference. Nieuw Arch. Wisk.(3),20(1972), 54-67.
[42] G. 0. H. Katona. On a conjecture of Ehrenfeucht and Mycielski. J. Combin. Theory A —
[43] D. J. Kleitman. On an extremal property of antichains in partial orders. In Combinatorics (eds.M. Hall and J. H. Van. Lint), Math. Centre Traces 55, 77-90(1974).Mathematics Centre, Amsterdam.
[44] D. J. Kleitman. On a lemma of Littlewood and Offord on the distribution of certain sums. Math. 2. 90(1965), 251-259.
[45] D. J. Kleitman, J. Sperner. Families of k-independent sets. Discrete Math., 6(1973), 255-262.
[46] D. J. Kleitman. Max number of subsets of a finite set no k of which are pairwise disjoint. J. Combin. Theory, 5(1968), 157-163.
[47] D. J. Kleitman. On a conjecture of Milner on K-graphs with nondisjoint edges. J. Combin. Theory, 5(1968), 153-156.
[48] K.-W. Lih. Sperner families over a subset. J. Combin. Theory Ser. A 29(1980), 182-185.
[49] M. L. Livingston. An ordered version of the Erdos-Ko-Roda theorem. J. Combin. Theory A 26(1979), 162-165.
[50] L. Lovasz. Flats in matroids and geometric graphs. In Combinatorics surveys (ed.P.J.Cameron), pp. 45-86, 1977, Academic press, New York.
[51] D. Lubell.A short proof of Sperner's theorem. J. Combin. Th. 1(1966),299.
[52] E. C. Milner. A combinatorial theorem on systems of sets. J. Lond. Math. Soc. 43(1986), 204-206.
[53] A. Moon. An analogue of The Erdos-Ko-Rado theorem for the Hamming Schemes H(n,q). J. Combin. Theory A 32(1982), 386-390.
[54] G. Purdy. A result on Sperner collections. Utilitas Math. 12(1977), 95-99.
[55] B. M. I. Rands. An extension of the Erdos-Ko-Rado theorem to t-designs. J. Combin. Theory A 32(1982), 391-395.
[56] A. Sali. A note on convex hulls of more-pare Sperner families. J. Combin. Theory A 49(1)(1988), 188-190.
[57] N. Sauer. On the density of families of sets. J. Combin. Theory A, 13(1972), 145-147.
[58] J. Schonheim. On a problem of Purdy related to Sperner systems. Can. Math. Bull 17(1974), 135-136.
[59] S. Shahriar. On the structure of maximum 2-part Sperner families. Discrete Mathematics 162(1966), 229-238.
[60] E. Sperner. Ein Satziiber Untermengen ciner endlichen Menge. Math. Z. 27(1928),544-548.
[61] R. P. Stanley. Some applications to algebra to combinarics. Discrete Appl. Math.,34(1991),241-277.
[62] D. Stanton. Some Erdos-Ko-Rodo theorems for chevalley groups. SIAM J. Algebraic Discrete Math. 1(1980),160.
[63] T. Tarjan. Private Communication.
[64] Changyu Wang, Huishan Zhou. A family of inequalities for intersecting antichains of subsets of an n-set. Europ. J. Combinatorics, 17(1996), 89-86.
[65] Y. Wang. On a class of subspace Lattice. J. Math. Research and Exposition, (2)19(1999), 341-348.
[66] H. S. Wilf. Generating functionology. Academic Press, 1990.
[67] R. M. Wilson. The exact bound in the Erdos-Ko-Rado theorem. Combinatorics 4(198), 247-257.