Cross-intersecting sub-families of hereditary families

Details Cross-intersecting sub-families of hereditary families Cross-intersecting sub-families of hereditary families

2011-03-20

arxiv.org/abs/1103.3858v1

Mathematics

Combinatorics

13 pages

Scientific paper

Families $\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k$ of sets are said to be \emph{cross-intersecting} if for any $i$ and $j$ in $\{1, 2, ..., k\}$ with $i \neq j$, any set in $\mathcal{A}_i$ intersects any set in $\mathcal{A}_j$. For a finite set $X$, let $2^X$ denote the \emph{power set of $X$} (the family of all subsets of $X$). A family $\mathcal{H}$ is said to be \emph{hereditary} if all subsets of any set in $\mathcal{H}$ are in $\mathcal{H}$; so $\mathcal{H}$ is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family $\mathcal{H} \neq \{\emptyset\}$ of $2^X$ and any $k \geq |X|+1$, both the sum and product of sizes of $k$ cross-intersecting sub-families $\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k$ (not necessarily distinct or non-empty) of $\mathcal{H}$ are maxima if $\mathcal{A}_1 = \mathcal{A}_2 = ... = \mathcal{A}_k = \mathcal{S}$ for some largest \emph{star $\mathcal{S}$ of $\mathcal{H}$} (a sub-family of $\mathcal{H}$ whose sets have a common element). We prove this for the case when $\mathcal{H}$ is \emph{compressed with respect to an element $x$ of $X$}, and for this purpose we establish new properties of the usual \emph{compression operation}. For the product, we actually conjecture that the configuration $\mathcal{A}_1 = \mathcal{A}_2 = ... = \mathcal{A}_k = \mathcal{S}$ is optimal for any hereditary $\mathcal{H}$ and any $k \geq 2$, and we prove this for a special case too.

Affiliated with

Also associated with

No associations

Rating

Cross-intersecting sub-families of hereditary families does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cross-intersecting sub-families of hereditary families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cross-intersecting sub-families of hereditary families will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-695766