A non-trivial intersection theorem for permutations with fixed number of cycles

详细信息    查看全文

• 作者：Cheng Yeaw Ku^a ; ^{matkcy@nus.edu.sg" class="auth_mail" title="E-mail the corresponding author} ; Kok Bin Wong^b ; ^{kbwong@um.edu.my" class="auth_mail" title="E-mail the corresponding author}
• 关键词：tt-intersecting family ; Frankl&ndash ; Hilton&ndash ; Milner ; Erdős&ndash ; Ko&ndash ; Rado ; Permutations
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：646-657
• 全文大小：402 K

文摘

Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=d2003ff42ff32fb97c36010b77da6302" title="Click to view the MathML source">S_nclass="mathContainer hidden">class="mathCode">$S_n$ denote the set of permutations of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=64faeaccf5d84375f90741c8eaf76c56" title="Click to view the MathML source">[n]={1,2,…,n}class="mathContainer hidden">class="mathCode">$\left[n\right]=\{1,2,\dots ,n\}$. For a positive integer class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si3.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=1a5bf36b71a1b1ba2bcbc8b5e1121840" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$, define class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=1a347d2d52d9c56e8c037d165d26acd7" title="Click to view the MathML source">S_n,kclass="mathContainer hidden">class="mathCode">$S_{n,k}$ to be the set of all permutations of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=12b2f8e53d7685521151fb6ed3404e2d" title="Click to view the MathML source">[n]class="mathContainer hidden">class="mathCode">$\left[n\right]$ with exactly class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si3.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=1a5bf36b71a1b1ba2bcbc8b5e1121840" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ disjoint cycles, i.e., where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=456682b4992ad0a18617267e1f2008b6" title="Click to view the MathML source">c₁,c₂,…,c_kclass="mathContainer hidden">class="mathCode">$c_1,c_2,\dots ,c_k$ are disjoint cycles. The size of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=1a347d2d52d9c56e8c037d165d26acd7" title="Click to view the MathML source">S_n,kclass="mathContainer hidden">class="mathCode">$S_{n,k}$ is given by class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si10.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=da73f17cbd6c2b1a8cf7477bf1470424">class="imgLazyJSB inlineImage" height="20" width="137" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003623-si10.gif">class="mathContainer hidden">class="mathCode">$\left[\begin{array}{c}\hfill n\hfill \\ \hfill k\hfill \end{array}\right]={(-1)}^{n-k}s(n,k)$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si11.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ef647eb0b09b411e869b90010185fa41" title="Click to view the MathML source">s(n,k)class="mathContainer hidden">class="mathCode">$s(n,k)$ is the Stirling number of the first kind. A family class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si12.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=8ac7cd2b2c161b88ff9ed5580d0b6b82" title="Click to view the MathML source">A⊆S_n,kclass="mathContainer hidden">class="mathCode">$\mathcal{A}\subseteq S_{n,k}$ is said to be class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ebbaf7c620583342e6391ef65bfd1b03" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-cycle-intersecting if any two elements of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si14.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ecde62cae59304416b0c143daf55fdd7" title="Click to view the MathML source">Aclass="mathContainer hidden">class="mathCode">$\mathcal{A}$ have at least class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ebbaf7c620583342e6391ef65bfd1b03" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$ common cycles. A family class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si12.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=8ac7cd2b2c161b88ff9ed5580d0b6b82" title="Click to view the MathML source">A⊆S_n,kclass="mathContainer hidden">class="mathCode">$\mathcal{A}\subseteq S_{n,k}$ is said to be trivially class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ebbaf7c620583342e6391ef65bfd1b03" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-cycle-intersecting if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si14.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ecde62cae59304416b0c143daf55fdd7" title="Click to view the MathML source">Aclass="mathContainer hidden">class="mathCode">$\mathcal{A}$ is the stabiliser of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ebbaf7c620583342e6391ef65bfd1b03" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$ fixed points, i.e., class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si14.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ecde62cae59304416b0c143daf55fdd7" title="Click to view the MathML source">Aclass="mathContainer hidden">class="mathCode">$\mathcal{A}$ consists of all permutations in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=1a347d2d52d9c56e8c037d165d26acd7" title="Click to view the MathML source">S_n,kclass="mathContainer hidden">class="mathCode">$S_{n,k}$ with some class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ebbaf7c620583342e6391ef65bfd1b03" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$ fixed cycles of length one. For class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si23.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=68f849392fb52554ff8b0b24be204ab2" title="Click to view the MathML source">1≤j≤tclass="mathContainer hidden">class="mathCode">$1\le j\le t$, let For class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si25.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=05f616d8844e5a7d49fd5b680b84e89b" title="Click to view the MathML source">t+1≤s≤kclass="mathContainer hidden">class="mathCode">$t+1\le s\le k$, let In this paper, we show that, given any positive integers class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si27.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=3ba9a04d498d6f48f4603697f001261d" title="Click to view the MathML source">k,tclass="mathContainer hidden">class="mathCode">$k,t$ with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si28.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=926186f1093301bed3490525798ba5cb" title="Click to view the MathML source">k≥2t+3class="mathContainer hidden">class="mathCode">$k\ge 2t+3$, there exists an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si29.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=3177290ee5ffd6debfd291f638d3f749" title="Click to view the MathML source">n₀=n₀(k,t)class="mathContainer hidden">class="mathCode">$n_0=n_0(k,t)$, such that for all class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si30.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=c9138f7a405718dc62db7f3470e76730" title="Click to view the MathML source">n≥n₀class="mathContainer hidden">class="mathCode">$n\ge n_0$, if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si12.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=8ac7cd2b2c161b88ff9ed5580d0b6b82" title="Click to view the MathML source">A⊆S_n,kclass="mathContainer hidden">class="mathCode">$\mathcal{A}\subseteq S_{n,k}$ is non-trivially class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ebbaf7c620583342e6391ef65bfd1b03" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">$t$-cycle-intersecting, then where class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si34.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=aad6297e9e7f8f9d8795f51dd7b45b7f">class="imgLazyJSB inlineImage" height="24" width="177" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003623-si34.gif">class="mathContainer hidden">class="mathCode">$\mathcal{B}={\bigcup }_{s=t+1}^k{\mathcal{B}}_s\cup {\bigcup }_{j=1}^t{\mathcal{Q}}_j$. Furthermore, equality holds if and only if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si14.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=ecde62cae59304416b0c143daf55fdd7" title="Click to view the MathML source">Aclass="mathContainer hidden">class="mathCode">$\mathcal{A}$ is a conjugate of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si36.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=390c380029d594224e1cba3595b24648" title="Click to view the MathML source">Bclass="mathContainer hidden">class="mathCode">$\mathcal{B}$, i.e., class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si37.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=f6985e1f3cc0f20df963b485c034940d" title="Click to view the MathML source">A=β⁻¹Bβclass="mathContainer hidden">class="mathCode">$\mathcal{A}={\beta }^{-1}\mathcal{B}\beta$ for some class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003623&_mathId=si38.gif&_user=111111111&_pii=S0012365X15003623&_rdoc=1&_issn=0012365X&md5=c07d6813d921c52d64ff5001d461827e" title="Click to view the MathML source">β∈S_nclass="mathContainer hidden">class="mathCode">$\beta \in S_n$.