Erdős–Ko–Rado theorems for permutations and set partitions

详细信息    查看全文

• 作者：Cheng Yeaw Ku ; David Renshaw
• 关键词：Intersecting families ; Permutations ; Set partitions
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2008
• 出版时间：August 2008
• 年：2008
• 卷：115
• 期：6
• 页码：1008-1020
• 全文大小：159 K

文摘

Let href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml1&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=6424402f7d4791943599076db80e7e69"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">Sym([n]) denote the collection of all permutations of href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml2&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=44d3e333b2a88b49ecb46129c94ef60f"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">[n]={1,…,n}. Suppose href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml3&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=ec20d2232b0f25bca964f51505da445f"">http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4RPVHY6-1-7/0?wchp=dGLbVzb-zSkWb"" alt=""View the MathML source"" title=""View the MathML source"" align=""absbottom"" border=""0"" height=15 width=""94""/> is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, l4"">href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml4&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=a6316e68053b6e5e389e54683ce7987e"">http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4RPVHY6-1-8/0?wchp=dGLbVzb-zSkWb"" alt=""View the MathML source"" title=""View the MathML source"" align=""absbottom"" border=""0"" height=15 width=""91""/> with equality if and only if href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml5&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=e82a19255270e441c5260443fd74fd9a"">http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4RPVHY6-1-9/0?wchp=dGLbVzb-zSkWb"" alt=""View the MathML source"" title=""View the MathML source"" align=""absbottom"" border=""0"" height=13 width=""16""/> is the stabilizer of t fixed points. Similarly, let href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml6&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=a52ee4ed80f9f195e07f59fcbc1612fe"">http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4RPVHY6-1-B/0?wchp=dGLbVzb-zSkWb"" alt=""View the MathML source"" title=""View the MathML source"" align=""absbottom"" border=""0"" height=15 width=""33""/> denote the collection of all set partitions of href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml7&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=5a1b41908309755c941de6b2f34fa5e8"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">[n] and suppose href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml8&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=cf0c85923ed53c4d1d4179082282543f"">http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4RPVHY6-1-D/0?wchp=dGLbVzb-zSkWb"" alt=""View the MathML source"" title=""View the MathML source"" align=""absbottom"" border=""0"" height=15 width=""65""/> is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml9&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=0d12ab6df753eebf9e23874165bc97d4"">http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4RPVHY6-1-F/0?wchp=dGLbVzb-zSkWb"" alt=""View the MathML source"" title=""View the MathML source"" align=""absbottom"" border=""0"" height=15 width=""73""/> with equality if and only if href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml10&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=bfcfaad06267ae6a7090770ed231bef8"">http://www.sciencedirect.com/cache/MiamiImageURL/B6WHS-4RPVHY6-1-3/0?wchp=dGLbVzb-zSkWb"" alt=""View the MathML source"" title=""View the MathML source"" align=""absbottom"" border=""0"" height=13 width=""16""/> consists of all set partitions with t fixed singletons, where href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WHS-4RPVHY6-1&_mathId=mml11&_user=1067359&_cdi=6858&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=0310d9b7e9f3772adccde33c91a00a19"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">B_n is the nth Bell number.