Skip to main content
deleted 2 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}, \{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly interection-free, but does not satisfy my condition.

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}, \{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly interection-free, but does not satisfy my condition.

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}, \{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly interection-free, but does not satisfy my condition.

added 203 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}, \{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly interection-free, but does not satisfy my condition.

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free.

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}, \{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly interection-free, but does not satisfy my condition.

added 174 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Set family $\mathcal{F}$ such that for all $A,B,C \in \mathcal{F}$ eitherboth $A \cap B \not \subseteq C$ orand $C \not \subseteq A \cup B $

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ eitherboth $A \cap B \not \subseteq C$ orand $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}$, $\{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly intersection-free, but does not satisfy my condition.

Set family $\mathcal{F}$ such that for all $A,B,C \in \mathcal{F}$ either $A \cap B \not \subseteq C$ or $C \not \subseteq A \cup B $

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ either $A \cap B \not \subseteq C$ or $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}$, $\{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly intersection-free, but does not satisfy my condition.

Set family $\mathcal{F}$ such that for all $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B $

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set a family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free.

added 174 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading
edited title
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading