Skip to main content
MathOverflow

Return to Question

corrected typo "lo of" -> "lot of"
Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 162

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 lolot 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?

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 lo 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?

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?

Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 162

How much can we "shrink" intersecting families

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 lo 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?