1
$\begingroup$

If the set system $(X,S)$ has the $(p,q)$-property does its dual system also have the property? (Possibly, for different $p$ and $q$.)

Explicitly, I am asking about the equivalence of the following two properties:

  • Out of any $p$ sets in $S$ we can find $q$ with nonempty intersection.

  • Out of any $p$ points in $X$ we can find $q$ contained in the same set in $S$.

I guess the answer is no, but do not have a counter-example.

$\endgroup$
1
  • $\begingroup$ By a "set-system", you meant just that $S$ is a collection of subsets of $X$? $\endgroup$ Commented Aug 26, 2014 at 10:25

1 Answer 1

3
$\begingroup$

The properties are not equivalent. Let $S$ consist of (at least two) subsets of $X$, which have one point entirely in common, but which are otherwise disjoint (and which have other points than that common point). This has the $(p,q)$ property, since all sets in $S$ have nonempty intersection. But if $p,q>1$, then you can pick two points other than the common point, from different elements of $S$, and they are not contained in a single set from $S$.

For example, let $S=\{\ \{0,1\}, \{0,2\}\ \{0,3\}\}$. This has the $(p,q)$ property for any positive $p$ and $q$, since $0$ is in the intersection of $S$; but the dual $(3,2)$-property fails, since no two elements of $1, 2, 3$ are contained in a single set of $S$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .