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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.