Intersecting generalised permutations

MaRDI QIDQ5245537zbMATH OpenFDO

Authors Peter Borg, K. Meagher

Publication date 9 April 2015

Full work available at URL https://arxiv.org/abs/1403.2344, http://ajc.maths.uq.edu.au//pdf/61/ajc_v61_p147.pdf

zbMATH Keywords

Erdős-Ko-Rado theoremKatona's cycle method

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: For any positive integers $k,r,n$ with $rleqmink,n$, let $mathcal{P}_{k,r,n}$ be the family of all sets $(x_1,y_1),dots,(x_r,y_r)$ such that $x_1,dots,x_r$ are distinct elements of $[k]=1,dots,k$ and $y_1,dots,y_r$ are distinct elements of $[n]$. The families $mathcal{P}_{n,n,n}$ and $mathcal{P}_{n,r,n}$ describe permutations of $[n]$ and $r$-partial permutations of $[n]$, respectively. If $kleqn$, then $mathcal{P}_{k,k,n}$ describes permutations of $k$-element subsets of $[n]$. A family $mathcalA$ of sets is said to be intersecting if every two members of $mathcalA$ intersect. In this note we use Katona's elegant cycle method to show that a number of important ErdH{o}s-Ko-Rado-type results by various authors generalise as follows: the size of any intersecting subfamily $mathcalA$ of $mathcal{P}_{k,r,n}$ is at most $k-1chooser-1frac(n-1)!(n-r)!$, and the bound is attained if and only if $mathcalA=Ainmathcal{P}_{k,r,n}colon(a,b)inA$ for some $ain[k]$ and $bin[n]$.

Recommendations

• Intersecting families of permutations
• Intersecting families of permutations
• Cross-intersecting families of permutations
• Setwise intersecting families of permutations
• Intersection theorem for finite permutations
• Cross-Intersecting Families of Partial Permutations
• On the generalized permutations
• Complete intersection problems for finite permutations
• Intersection theorems in permutation groups
• Generalized alternating subsets with permutations

Cited in

(13)

• An Erdős-Ko-Rado theorem for integer sequences of given rank
• An Erdős-Ko-Rado theorem for restricted signed sets
• The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities
• An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
• INTERSECTING FAMILIES OF SEPARATED SETS
• Interlocked Permutations
• Common intervals of multiple permutations
• On Disjoint Cross Intersecting Families of Permutations
• Intersecting families of permutations
• Intersecting families of permutations
• Intersection theorems for families of matchings of complete k-partite k-graphs
• A non-trivial intersection theorem for permutations with fixed number of cycles
• Cross-intersecting families of permutations

This page was built for publication: Intersecting generalised permutations

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