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

MaRDI QIDQ405301zbMATH OpenFDO

Authors Cheng Yeaw Ku, K. B. Wong

Publication date 4 September 2014

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

Full work available at URL https://arxiv.org/abs/1402.0668, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p16

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

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)

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.

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

Cites work

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

Cited in

(8)

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

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)