The Open UniversitySkip to content
 

The Erdös-Ko-Rado properties of set systems defined by double partitions

Borg, Peter and Holroyd, Fred (2009). The Erdös-Ko-Rado properties of set systems defined by double partitions. Discrete Mathematics, 309(14) pp. 4754–4761.

Full text available as:
Full text not publicly available
Due to copyright restrictions, this file is not available for public download
Click here to request a copy from the OU Author.
DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/j.disc.2008.05.052
Google Scholar: Look up in Google Scholar

Abstract

Let $F$ be a family of subsets of a finite set $V$. The star of $F$ at $v \in V$ is the sub-family $[\{A \in F: v \in A\}$. We denote the sub-family $\{A \in F: |A| = r\}$ by $F^{(r)}$.
A double partition P of a finite set V is a partition of $V$ into 'large sets' that are in turn partitioned into 'small sets'. Given such a partition, the family $F(P)$ induced by $P$ is the family of subsets of $V$ whose intersection with each large set is either contained in just one small set or empty.
Our main result is that, if one of the large sets is trivially partitioned (that is, into just one small set) and $2r$ is not greater than the least cardinality of any maximal set of $F(P)$, then no intersecting sub-family of $F(P)^{(r)}$ is larger than the largest star of $F(P)^{(r)}$. We also characterise the case when every extremal intersecting sub-family of $F(P)^{(r)}$ is a star of $F(P)^{(r)}$.

Item Type: Journal Article
Copyright Holders: 2008 Elsevier B.V.
ISSN: 0012-365X
Keywords: Erdös-Ko-Rado; intersecting family; double partition
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 24682
Depositing User: Fred Holroyd
Date Deposited: 16 Nov 2010 17:14
Last Modified: 19 Dec 2012 09:54
URI: http://oro.open.ac.uk/id/eprint/24682
Share this page:

Altmetrics

Scopus Citations

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk