Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/75636
Title: | Intersecting generalised permutations |
Authors: | Borg, Peter Meagher, Karen |
Keywords: | Mathematics Logic, Symbolic and mathematical Set theory Hypergraphs Permutations |
Issue Date: | 2015 |
Publisher: | Centre for Discrete Mathematics & Computing |
Citation: | Borg, P., & Meagher, K. (2015). Intersecting generalised permutations. The Australasian Journal of Combinatorics, 61(2), 147-155. |
Abstract: | For any positive integers k,r,n with r≤min{k,n}, let Pk,r,n be the family of all sets {(x1,y1),…,(xr,yr)} such that x1,…,xr are distinct elements of [k]={1,…,k} and y1,…,yr are distinct elements of [n]. The families Pn,n,n and Pn,r,n describe permutations of [n] and r-partial permutations of [n], respectively. If k≤n, then Pk,k,n describes permutations of k-element subsets of [n]. A family A of sets is said to be intersecting if every two members of A intersect. In this note we use Katona's elegant cycle method to show that a number of important Erdős-Ko-Rado-type results by various authors generalise as follows: the size of any intersecting subfamily A of Pk,r,n is at most (k−1r−1)(n−1)!(n−r)!, and the bound is attained if and only if A={A∈Pk,r,n:(a,b)∈A} for some a∈[k] and b∈[n]. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/75636 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Intersecting_generalised_permutations_2015.pdf Restricted Access | 253.66 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.