4
$\begingroup$

Motivation. An intersecting family is a collection of subsets ${\cal S}\subseteq {\cal P}(X)$ of a set $X\neq \emptyset$ such that $A\cap B\neq \emptyset$ for all $A,B\in {\cal S}$. The intersections of members of ${\cal S}$ can be quite large. I was wondering whether it is always possible to "shrink" ${\cal S}$ such that a lot of intersections between $2$ sets become singletons.

Shrinkings. If ${\cal S}\subseteq {\cal P}(X)$ is intersecting, we say that ${\cal S}^*\subseteq {\cal P}(X)$ is a shrinking of ${\cal S}$ if ${\cal S}^*$ is intersecting and there is a bijection $\varphi:{\cal S} \to {\cal S^*}$ such that for all $A \in {\cal S}$ we have that $\varphi(A)\subseteq A$.

For any set $Z$, let $[Z]^2=\big\{\{a,b\}:a\neq b\in Z\big\}$. Moreover, we set $[{\cal S}]^2_1:=\big\{\{A,B\} \in [{\cal S}]^2: |A\cap B|=1\big\}$. We say ${\cal S}$ is intersection-efficient if $$\big|[{\cal S}]^2_1\big| \geq \big|[{\cal S}]^2 \setminus [{\cal S}]^2_1\big|.$$

Question. If ${\cal S}\subseteq {\cal P}(X)$ is intersecting, is there a shrinking ${\cal S}^*\subseteq {\cal P}(X)$ of ${\cal S}$ such that ${\cal S}^*$ is intersection-efficient?

$\endgroup$

1 Answer 1

6
$\begingroup$

Counterexample. Let $X=\{1,2,3,\dots,n\}$ where $n\ge8$, and let $$\mathcal S=\{\{1,2\},\ \{1,3\},\ \{2,3\}\}\cup\{\{2,3,x\}:3\lt x\le n\}\subset\mathcal P(X).$$ Then $\mathcal S$ is an intersecting family with no proper shrinking, and $\mathcal S$ is not intersection-efficient, since $$|[\mathcal S]^2_1|=2n-3\lt\binom{n-2}2=|[\mathcal S]^2\setminus[\mathcal S]^2_1|.$$

Another counterexample. Let $X=\{0,1,2,\dots,n\}$ where $n\ge3$, and let $$\mathcal S=\{A\subseteq X:0\in A\}\subset\mathcal P(X).$$ Then $\mathcal S$ is an intersecting family with no proper shrinking, and $\mathcal S$ is not intersection-efficient, since $$|[\mathcal S]^2_1|=\frac{3^n-1}2\lt\binom{2^n}2-\frac{3^n-1}2=|[\mathcal S]^2\setminus[\mathcal S]^2_1|.$$

$\endgroup$

You must log in to answer this question.

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