偏序集的套链分解
|
摘要
偏序集的Sperner理论,主要研究偏序集的Sperner性质、LYM性质、匹配性质和链分解性质等.对一般偏序集的Sperner型性质,从匹配的观点来看最强的性质是正规匹配,而从链分解的观点看最强的性质是套链分解.有套链分解的偏序集未必具有正规匹配性质,而对秩单峰的偏序集,Griggs于1977年提出正规匹配蕴含套链分解这一猜想.本文主要研究偏序集的套链分解,全文共分四章.
第一章介绍Sperner理论的发展,基本概念以及采用的基本方法和相关结论.
第二章考察Griggs猜想.首先说明秩3偏序集对解决Griggs猜想的重要性,其次综述秩3偏序集套链分解的四种方法,指出“转化二部图法”,“加一层法”和“'Stanley链性质法”在改进中所遇到的问题,并说明“极小NM法”在结构上的优势,最后对两类特殊的偏序集证实了Griggs猜想.
下面两章介绍两类重要偏序集的对称链分解,其并不依赖于正规匹配性质.
第三章考察Young偏序集L(m,n)的对称链分解,当m和n都大于2时,三(m,n)并不具有正规匹配性质,而Stanley猜想其具有对称链分解,目前只有Lindstrom对L(3,n)和West对L(4,n)进行了验证,但对于更大的m还没有进展.本章首先给出一个按字典序排序生成L(m,n)的算法,其次重点考察Lindstrom的方法,并说明“去外壳法”与m的奇偶性有关,最后介绍Wen对L(3,n)和L(4,n)构造对称链分解的一个新算法.
第四章考察项链偏序集Nn的对称链分解.这类偏序集是否具有正规匹配性质尚未定论.不过当n是素数时,Griggs, Killian和Savage于2004年构造出了Nn的一个对称链分解,同时提出对于一般的n也成立的猜想.2010年Jordan给出的算法解决了这一猜想.本章首先给出一个由子集格Bn生成Nn的算法,并说明此算法不能按列形成对称链,最后介绍Jordan的算法.
Sperner theory is a very lively area of combinatorins. The main content of Sperner theory is to investgate the extremal problems on posets. For rank-unimodal posets, Griggs conjectured that normal matching implies nested chain partitions in 1977.In this thesis, we investigate nested chain partitions for posets.
The organization of this paper is as follows:
In the first chapter, we review some basic terminology and methods in Sperner theory.
In the second chapter, we show the importance of rank 3 posets for Griggs conjecture and mainly consider four approaches to nested chain partitions for rank 3 posets. We also verify this conjecture for special posets of two kinds.
In the following two chapters, we investigate symmetric chain partitions for important posets of two kinds.
In the third chapter, we give an algorithm to generate Hasse diagram of poset L(m, n), and mainly investigate symmetric chain partitions for L(3, n).
In the forth chapter, we firstly give an algorithm to generate necklace poset Nn from subset lattice Bn,and then investigate the symmetric chain partitions for Nn.
第一章介绍Sperner理论的发展,基本概念以及采用的基本方法和相关结论.
第二章考察Griggs猜想.首先说明秩3偏序集对解决Griggs猜想的重要性,其次综述秩3偏序集套链分解的四种方法,指出“转化二部图法”,“加一层法”和“'Stanley链性质法”在改进中所遇到的问题,并说明“极小NM法”在结构上的优势,最后对两类特殊的偏序集证实了Griggs猜想.
下面两章介绍两类重要偏序集的对称链分解,其并不依赖于正规匹配性质.
第三章考察Young偏序集L(m,n)的对称链分解,当m和n都大于2时,三(m,n)并不具有正规匹配性质,而Stanley猜想其具有对称链分解,目前只有Lindstrom对L(3,n)和West对L(4,n)进行了验证,但对于更大的m还没有进展.本章首先给出一个按字典序排序生成L(m,n)的算法,其次重点考察Lindstrom的方法,并说明“去外壳法”与m的奇偶性有关,最后介绍Wen对L(3,n)和L(4,n)构造对称链分解的一个新算法.
第四章考察项链偏序集Nn的对称链分解.这类偏序集是否具有正规匹配性质尚未定论.不过当n是素数时,Griggs, Killian和Savage于2004年构造出了Nn的一个对称链分解,同时提出对于一般的n也成立的猜想.2010年Jordan给出的算法解决了这一猜想.本章首先给出一个由子集格Bn生成Nn的算法,并说明此算法不能按列形成对称链,最后介绍Jordan的算法.
Sperner theory is a very lively area of combinatorins. The main content of Sperner theory is to investgate the extremal problems on posets. For rank-unimodal posets, Griggs conjectured that normal matching implies nested chain partitions in 1977.In this thesis, we investigate nested chain partitions for posets.
The organization of this paper is as follows:
In the first chapter, we review some basic terminology and methods in Sperner theory.
In the second chapter, we show the importance of rank 3 posets for Griggs conjecture and mainly consider four approaches to nested chain partitions for rank 3 posets. We also verify this conjecture for special posets of two kinds.
In the following two chapters, we investigate symmetric chain partitions for important posets of two kinds.
In the third chapter, we give an algorithm to generate Hasse diagram of poset L(m, n), and mainly investigate symmetric chain partitions for L(3, n).
In the forth chapter, we firstly give an algorithm to generate necklace poset Nn from subset lattice Bn,and then investigate the symmetric chain partitions for Nn.
引文
[1]A. C.Aitken. Thenormal form of compound and induced matrices. Proc.London Math. Soc.(2), 38(1934),354.
[2]I.Anderson. Some problems in combinatorial number theory. Ph.D.Thesis.university of Nottingham,1967.
[3]I.Anderson. Combinatorics of Finite Sets.Clarendon Press, Oxford,1987.
[4]A. S.Asratian, T. M. J. Denley,R. Haggkvist.Bipartite Graph and Their Applications. Cambridge University Press, NewYork,1998.
[5]B. Bollobas.Sperner systems consisting of pairs of complementary subsets.J. Combinatorial Theory Ser. A,15(1973),362-366.
[6]N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, D. Kruyswijk. On the set of divisors of a number. Nieuw Arch. Wiskunde,23(1951),191-193.
[7]E. R. Canfield. On a problem of Rota.7 Adv. in Math.,29(1978),1-10.
[8]L. Comtet.Advanced Combinatorics.Reidel,Dordrecht,1974.
[9]R. P. Dilworth. A decomposition theorem for partially ordered sets. Ann. Math.,51(1950), 161-165.
[10]K. Engel.Sperner Theory.Cambridge University Press, NewYork,1997.
[11]L. R. Ford, D. R. Fulkerson. Network flow and systems of representatives.Canad. J. Math., 10(1958),78-85.
[12]L. R. Ford, D. R. Fulkerson. Flows in Networks. Princeton University Press,Pinceton, NJ, 1962.
[13]R. Fredrich. A look at matchwebs. http://www.morris.umn.edu/academic/math/Ma4901/F08/fredrich-final.pdf,2008.
[14]R.L.Graham, L. H. Harper. Some results on matching in bipartite graphs.SIAM J.Appl. Math.,17(1969),1017-1022.
[15]C. Greene,D. J. Kleitman. Strong vertions of Sperner's theorem. J. Combinatorial Theory Ser. A,20(1976),80-88.
[16]C.Greene, D. J. Kleitman. Proof techniques in the theory of finite sets. In G. C. Rota, ed.,Studies in Combinatorics,vol.17 of MAA Studies in Math.,22-79.
[17]J. R.Griggs. Sufficient conditions for a symmetric chain order. SIAM J. Appl.Math., 32(1977),807-809.
[18]J. R. Griggs. On chains and Sperner k-families in ranked posets. J. Combinatorial Theory Ser. A,28(1980),156-168.
[19]J. R. Griggs. Collections of subsets with the spemer proper. Trans. Amer.Math.Soc. 269(1982),575-591.
[20]J. R. Griggs. Problems on chain partitions. Discrete Math.,72(1988),157-162.
[21]J. R. Griggs. Matchings, cutsets,and chain partitions in graded posets. Discrete Math. 144(1995),33-46.
[22]J. R. Griggs, C. E. Killian, C. D. Savage. Venn diagrams and symmetric chain decompositions in the Boolean lattice. Electron. J. Combin.,11(2004).
[23]P. Hall.On representative of subsets. J. London Math. Soc.,10(1935),26-30.
[24]W. N. Hsieh, D. J. Kleitman. Normalized matching in direct products of partial orders. Studies in Appl.Math.,52(1973),285-289.
[25]T.Hsu, M. J. Logan, S.Shahriari.Methods for nesting rank 3 normalized matching rank-unimodal posets. Discrete Math.,309(2009),521-531.
[26]Zongliang Jiang. Symmetric chain decompositions and independent families of curves. MS thesis. North Carolina State University, http://www.lib.ncsu.edu/theses/available/etd-07072003-035905/unrestricted/etd.pdf, 2003.
[27]Zongliang Jiang, Carla D. Savage.On the existence of symmetric chain decompositions in a quotient of the Boolean lattice. Discrete Math.,309(2009),5278-5283.
[28]K. K. Jordan. The necklace poset is a symmetric chain order. J. Combinatorial Theory Ser. A, 117(2010),625-641.
[29]D. J.Kleitman. Some combinatorial construction problems. Combinatorial algorithms, 1973,97-108.
[30]D. J. Kteitman. On an extremal property of antichain in partial orders. Combinatorics, 1974,77-90.
[31]K.-W. Lih. Sperner families over a subset.J. Combinatorial Theory Ser. A,29(1980), no.2,182-185.
[32]B. Lindstrom. A partition of L(3,n) into saturated chains. European J. Combin.,1(1980), 61-63.
[33]D. E. Littlewood. The Theory of Group Characters and Matrix Representations of Groups, 2nd ed.. Oxford University Press, Oxford,1950.
[34]M. J.Logan. Sperner theory in a difference of boolean lattices. Discrete Math. 257(2002),501-512.
[35]L. Lovdsz.Combinatorial Problem and Exercises. Amsterdam:North-Holland,1979.
[36]L. Lovasz, M.D. Plummer. Matching Theory. AMS Chelsea Publishing, Providence RI,2009.
[37]D. Lubell.A short proof of Sperner's theorem. J. Combinatorial Theory,1(1966),299.
[38]K. M.O'Hara. Unimodality of Gaussian coefficients:a constructive proof. J. Combinatorial Theory Ser. A,53(1990),29-52.
[39]G. C.Rota. On the foundations of combinatorial theory Ⅰ.Theory of MobiUs functions. Z.Wahrsch. Verw. Gebiete,2(1964),340-368.
[40]G. C. Rota. Research problem 2-1.J. Combinatorial Theory,1967,1-104.
[41]K.Shelley. Matchwebs. MS Thesis. San Jose State University,2007.
[42]E. Sperner. Ein Satz Uber Untermengen einer endlichen Menge(German).Math. Z.,27(1928), no.1,544-548.
[43]R. P. Stanley. Weyl groups,the hard Lsfschetz theorem, and the Sperner property.SIAM J.Algebraic and Discrete Methods,1(1980),168-184.
[44]R.P.Stanley. Some applications of algebra to combinatorics. Discrete'Appl.Math. 34(1991),no.1-3,241-277.
[45]R. P. Stanley. Enumerative Combinatorics,Vol.1.Cambridge University Press,Cambridge, 1997.
[46]Y.Wang. Nested chain partitions of LYM posets. Discrete Appl.Math.,145(2005), 493-497.
[47]D. B. West. A symmetric chain decomposition of L(4, n).European J. Combin.,1(1980), 379-383.
[48]D. B. West,L. H. Harper, D. E. Daykin. Some remarks on normalized matching. J. Combinatorial Theory Ser. A,35(1983),301-308.
[49]X. Wen. Computer-generated symmetric chain decompositions for L(4, n)and L(3, n).Adv. in Appl.Math.,33(2004),409-412.
[2]I.Anderson. Some problems in combinatorial number theory. Ph.D.Thesis.university of Nottingham,1967.
[3]I.Anderson. Combinatorics of Finite Sets.Clarendon Press, Oxford,1987.
[4]A. S.Asratian, T. M. J. Denley,R. Haggkvist.Bipartite Graph and Their Applications. Cambridge University Press, NewYork,1998.
[5]B. Bollobas.Sperner systems consisting of pairs of complementary subsets.J. Combinatorial Theory Ser. A,15(1973),362-366.
[6]N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, D. Kruyswijk. On the set of divisors of a number. Nieuw Arch. Wiskunde,23(1951),191-193.
[7]E. R. Canfield. On a problem of Rota.7 Adv. in Math.,29(1978),1-10.
[8]L. Comtet.Advanced Combinatorics.Reidel,Dordrecht,1974.
[9]R. P. Dilworth. A decomposition theorem for partially ordered sets. Ann. Math.,51(1950), 161-165.
[10]K. Engel.Sperner Theory.Cambridge University Press, NewYork,1997.
[11]L. R. Ford, D. R. Fulkerson. Network flow and systems of representatives.Canad. J. Math., 10(1958),78-85.
[12]L. R. Ford, D. R. Fulkerson. Flows in Networks. Princeton University Press,Pinceton, NJ, 1962.
[13]R. Fredrich. A look at matchwebs. http://www.morris.umn.edu/academic/math/Ma4901/F08/fredrich-final.pdf,2008.
[14]R.L.Graham, L. H. Harper. Some results on matching in bipartite graphs.SIAM J.Appl. Math.,17(1969),1017-1022.
[15]C. Greene,D. J. Kleitman. Strong vertions of Sperner's theorem. J. Combinatorial Theory Ser. A,20(1976),80-88.
[16]C.Greene, D. J. Kleitman. Proof techniques in the theory of finite sets. In G. C. Rota, ed.,Studies in Combinatorics,vol.17 of MAA Studies in Math.,22-79.
[17]J. R.Griggs. Sufficient conditions for a symmetric chain order. SIAM J. Appl.Math., 32(1977),807-809.
[18]J. R. Griggs. On chains and Sperner k-families in ranked posets. J. Combinatorial Theory Ser. A,28(1980),156-168.
[19]J. R. Griggs. Collections of subsets with the spemer proper. Trans. Amer.Math.Soc. 269(1982),575-591.
[20]J. R. Griggs. Problems on chain partitions. Discrete Math.,72(1988),157-162.
[21]J. R. Griggs. Matchings, cutsets,and chain partitions in graded posets. Discrete Math. 144(1995),33-46.
[22]J. R. Griggs, C. E. Killian, C. D. Savage. Venn diagrams and symmetric chain decompositions in the Boolean lattice. Electron. J. Combin.,11(2004).
[23]P. Hall.On representative of subsets. J. London Math. Soc.,10(1935),26-30.
[24]W. N. Hsieh, D. J. Kleitman. Normalized matching in direct products of partial orders. Studies in Appl.Math.,52(1973),285-289.
[25]T.Hsu, M. J. Logan, S.Shahriari.Methods for nesting rank 3 normalized matching rank-unimodal posets. Discrete Math.,309(2009),521-531.
[26]Zongliang Jiang. Symmetric chain decompositions and independent families of curves. MS thesis. North Carolina State University, http://www.lib.ncsu.edu/theses/available/etd-07072003-035905/unrestricted/etd.pdf, 2003.
[27]Zongliang Jiang, Carla D. Savage.On the existence of symmetric chain decompositions in a quotient of the Boolean lattice. Discrete Math.,309(2009),5278-5283.
[28]K. K. Jordan. The necklace poset is a symmetric chain order. J. Combinatorial Theory Ser. A, 117(2010),625-641.
[29]D. J.Kleitman. Some combinatorial construction problems. Combinatorial algorithms, 1973,97-108.
[30]D. J. Kteitman. On an extremal property of antichain in partial orders. Combinatorics, 1974,77-90.
[31]K.-W. Lih. Sperner families over a subset.J. Combinatorial Theory Ser. A,29(1980), no.2,182-185.
[32]B. Lindstrom. A partition of L(3,n) into saturated chains. European J. Combin.,1(1980), 61-63.
[33]D. E. Littlewood. The Theory of Group Characters and Matrix Representations of Groups, 2nd ed.. Oxford University Press, Oxford,1950.
[34]M. J.Logan. Sperner theory in a difference of boolean lattices. Discrete Math. 257(2002),501-512.
[35]L. Lovdsz.Combinatorial Problem and Exercises. Amsterdam:North-Holland,1979.
[36]L. Lovasz, M.D. Plummer. Matching Theory. AMS Chelsea Publishing, Providence RI,2009.
[37]D. Lubell.A short proof of Sperner's theorem. J. Combinatorial Theory,1(1966),299.
[38]K. M.O'Hara. Unimodality of Gaussian coefficients:a constructive proof. J. Combinatorial Theory Ser. A,53(1990),29-52.
[39]G. C.Rota. On the foundations of combinatorial theory Ⅰ.Theory of MobiUs functions. Z.Wahrsch. Verw. Gebiete,2(1964),340-368.
[40]G. C. Rota. Research problem 2-1.J. Combinatorial Theory,1967,1-104.
[41]K.Shelley. Matchwebs. MS Thesis. San Jose State University,2007.
[42]E. Sperner. Ein Satz Uber Untermengen einer endlichen Menge(German).Math. Z.,27(1928), no.1,544-548.
[43]R. P. Stanley. Weyl groups,the hard Lsfschetz theorem, and the Sperner property.SIAM J.Algebraic and Discrete Methods,1(1980),168-184.
[44]R.P.Stanley. Some applications of algebra to combinatorics. Discrete'Appl.Math. 34(1991),no.1-3,241-277.
[45]R. P. Stanley. Enumerative Combinatorics,Vol.1.Cambridge University Press,Cambridge, 1997.
[46]Y.Wang. Nested chain partitions of LYM posets. Discrete Appl.Math.,145(2005), 493-497.
[47]D. B. West. A symmetric chain decomposition of L(4, n).European J. Combin.,1(1980), 379-383.
[48]D. B. West,L. H. Harper, D. E. Daykin. Some remarks on normalized matching. J. Combinatorial Theory Ser. A,35(1983),301-308.
[49]X. Wen. Computer-generated symmetric chain decompositions for L(4, n)and L(3, n).Adv. in Appl.Math.,33(2004),409-412.