An Erdős-Ko-Rado theorem for permutations with fixed number of cycles

zbMATH Open1300.05014arXiv1402.0668MaRDI QIDQ405301FDOQ405301

Cheng Yeaw Ku, K. B. Wong

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $S_n$ denote the set of permutations of $[n]=1,2,dots,n$. For a positive integer $k$, define $S_{n,k}$ to be the set of all permutations of $[n]$ with exactly $k$ disjoint cycles, i.e., [ S_{n,k} = {pi in S_{n}: pi = c_{1}c_{2} cdots c_{k}},] where $c_1,c_2,dots,c_k$ are disjoint cycles. The size of $S_{n,k}$ is given by $$, where $s(n,k)$ is the Stirling number of the first kind. A family $mathcalAsubseteq{S}_{n,k}$ is said to be $t$-{em intersecting} if any two elements of $mathcalA$ have at least $t$ common cycles. In this paper, we show that, given any positive integers $k,t$ with $kgeqt+1$, there exists an integer $n_0=n_0(k,t)$, such that for all $ngeq{n}_0$, if $mathcalAsubseteq{S}_{n,k}$ is $t$-intersecting, then [ |mathcal{A}| le left [ �egin{matrix}n-t\ k-t end{matrix} ight],] with equality if and only if $mathcalA$ is the stabiliser of $t$ fixed points.

Full work available at URL: https://arxiv.org/abs/1402.0668

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A non-trivial intersection theorem for permutations with fixed number of cycles
• Erdős-Ko-Rado theorems for permutations and set partitions
• Intersecting generalised permutations
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations

zbMATH Keywords

permutations\(t\)-intersecting familyStirling number of the first kindErdős-Ko-Rado

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• The diametric theorem in Hamming spaces---optimal anticodes
• Stable sets of maximal size in Kneser-type graphs
• Title not available (Why is that?)
• An Erdős-Ko-Rado theorem for multisets
• Intersecting families of permutations
• The exact bound in the Erdős-Ko-Rado theorem
• An Erdős--Ko--Rado theorem for partial permutations
• Erdős-Ko-Rado-type theorems for colored sets
• Intersecting families in the alternating group and direct product of symmetric groups
• An Erdős-Ko-Rado-type theorem in Coxeter groups.
• On \(t\)-intersecting families of signed sets and permutations
• An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
• Some Erdős-Ko-Rado theorems for injections
• Shadows and intersections: Stability and new proofs
• Concavity properties and a generating function for stirling numbers
• The Erdős-Ko-Rado theorem for vector spaces
• Shadows and intersections in vector spaces
• Intersecting families of permutations
• The Erdős-Ko-Rado properties of various graphs containing singletons
• Compression and Erdős-Ko-Rado graphs
• Graphs with the Erdős-Ko-Rado property
• Erdős-Ko-Rado theorems for chordal graphs and trees
• Erdős-Ko-Rado theorems for simplicial complexes
• Title not available (Why is that?)
• Extremal t -intersecting sub-families of hereditary families
• On cross-intersecting families of set partitions
• An analogue of the Hilton-Milner theorem for set partitions
• An analogue of the Erdős-Ko-Rado theorem for weak compositions
• Stability for \(t\)-intersecting families of permutations
• Erdős-Ko-Rado theorems for permutations and set partitions
• A generalization of the Erdős-Ko-Rado theorem on finite set systems
• Erdős-Ko-Rado theorems for uniform set-partition systems
• On \(r\)-cross intersecting families of set

Cited In (8)

• An Erdős-Ko-Rado theorem for integer sequences of given rank
• Erdős-Ko-Rado theorems for permutations and set partitions
• Title not available (Why is that?)
• On \(r\)-cross \(t\)-intersecting families for weak compositions
• An Erdős--Ko--Rado theorem for partial permutations
• A Deza-Frankl type theorem for set partitions
• Erdős-Ko-Rado theorems for set partitions with certain block size
• A non-trivial intersection theorem for permutations with fixed number of cycles

This page was built for publication: An Erdős-Ko-Rado theorem for permutations with fixed number of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405301)