Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/75630
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Borg, Peter | - |
dc.date.accessioned | 2021-05-17T07:03:26Z | - |
dc.date.available | 2021-05-17T07:03:26Z | - |
dc.date.issued | 2011 | - |
dc.identifier.citation | Borg, P. (2011). Maximum hitting of a set by compressed intersecting families. Graphs and Combinatorics, 27, 785-797. | en_GB |
dc.identifier.uri | https://www.um.edu.mt/library/oar/handle/123456789/75630 | - |
dc.description.abstract | For a family A and a set Z, denote {A∈A:A∩Z≠∅} by A(Z). For positive integers n and r, let Sn,r be the trivial compressed intersecting family {A∈([n]r):1∈A}, where [n]:={1,…,n} and ([n]r):={A⊂[n]:|A|=r}. The following problem is considered: For r ≤ n/2, which sets Z⊆[n] have the property that |A(Z)|≤|Sn,r(Z)| for any compressed intersecting family A⊂([n]r)? (The answer for the case 1∈Z is given by the Erdős–Ko–Rado Theorem.) We give a complete answer for the case |Z| ≥ r and a partial answer for the much harder case |Z| < r. This paper is motivated by the observation that certain interesting results in extremal set theory can be proved by answering the question above for particular sets Z. Using our result for the special case when Z is the r-segment {2,…,r+1}, we obtain new short proofs of two well-known Hilton–Milner theorems. At the other extreme end, by establishing that |A(Z)|≤|Sn,r(Z)| when Z is a final segment, we provide a new short proof of a Holroyd–Talbot extension of the Erdős-Ko-Rado Theorem. | en_GB |
dc.language.iso | en | en_GB |
dc.publisher | Springer Japan KK | en_GB |
dc.rights | info:eu-repo/semantics/restrictedAccess | en_GB |
dc.subject | Mathematics | en_GB |
dc.subject | Logic, Symbolic and mathematical | en_GB |
dc.subject | Set theory | en_GB |
dc.subject | Hypergraphs | en_GB |
dc.subject | Intersection graph theory | en_GB |
dc.title | Maximum hitting of a set by compressed intersecting families | en_GB |
dc.type | article | en_GB |
dc.rights.holder | The copyright of this work belongs to the author(s)/publisher. The rights of this work are as defined by the appropriate Copyright Legislation or as modified by any successive legislation. Users may access this work and can make use of the information contained in accordance with the Copyright Legislation provided that the author must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the prior permission of the copyright holder. | en_GB |
dc.description.reviewed | peer-reviewed | en_GB |
dc.identifier.doi | 10.1007/s00373-010-1001-2 | - |
dc.publication.title | Graphs and Combinatorics | en_GB |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Maximum_hitting_of_a_set_by_compressed_intersecting_families_2011.pdf Restricted Access | 193.01 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.