Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/75629
Title: | Cross-intersecting families of partial permutations |
Authors: | Borg, Peter |
Keywords: | Mathematics Logic, Symbolic and mathematical Set theory Hypergraphs |
Issue Date: | 2010 |
Publisher: | Society for Industrial and Applied Mathematics |
Citation: | Borg, P. (2010). Cross-intersecting families of partial permutations. SIAM Journal on Discrete Mathematics, 24(2), 600-608. |
Abstract: | For positive integers r and n with r ≤ n, let Pn, r be the family of all sets {(x1, y1), ⋯, (xr, yr)} such that x1, ⋯, xr are distinct elements of [n]:= {1, ⋯, n} and y1, ⋯, yr are also distinct elements of [n]. Pn, n describes permutations of [n]. For r < n, Pn, r describes r-partial permutations of [n]. Families A1, ⋯, Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. A sharp bound for the sum of sizes of cross-intersecting subfamilies of P n, n has recently been established by the author. We generalize this bound by showing that, if A1, ⋯, Ak are cross-intersecting subfamilies of Pn, rthen (i) ∑ i=1k|Ai| ≤ (n/r) n!/(n-r)! if k ≤ n/r and (ii) ∑ i=1k|Ai| ≤ k(n-1/n-1) (n-1)!/(n-1)! if k < n2/r. We also determine the structures for which the bound is attained when r< n. Our main tool is an extension of Katona's cyclic permutation method. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/75629 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Cross-intersecting_families_of_partial_permutations_2010.pdf | 212.29 kB | Adobe PDF | View/Open |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.