Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651266 | Discrete Mathematics | 2006 | 13 Pages |
Abstract
Let [n][n] denote the set of positive integers {1,2,…,n}{1,2,…,n}. An r-partial permutation of [n][n] is a pair (A,f)(A,f) where A⊆[n]A⊆[n], |A|=r|A|=r and f:A→[n]f:A→[n] is an injective map. A set AA of r-partial permutations is intersecting if for any (A,f)(A,f), (B,g)∈A(B,g)∈A, there exists x∈A∩Bx∈A∩B such that f(x)=g(x)f(x)=g(x). We prove that for any intersecting family AA of r -partial permutations, we have |A|⩽n-1r-1((n-1)!/(n-r)!).It seems rather hard to characterize the case of equality. For 8⩽r⩽n-38⩽r⩽n-3, we show that equality holds if and only if there exist x0x0 and ε0ε0 such that AA consists of all (A,f)(A,f) for which x0∈Ax0∈A and f(x0)=ε0f(x0)=ε0.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
C.Y. Ku, I. Leader,