0
$\begingroup$

How do I evaluate the equation:

$S _C(n) = \max_{x_1,x_2,\dots,x_n \in \Omega } \operatorname{card} \{\,\{\,x_1,x_2,\dots,x_n\}\cap s, s\in C \}$

For a collection $C$ of sets $s⊂Ω$

Is $\max_{x_1,x_2,\dots,x_n \in \Omega } \operatorname{card} \{\,x \}$ one single operation, or are max and card two separate operations?

Is $\{\,x_1,x_2,\dots,x_n\}$ just an arbitrary set of cardinality n? Is it implied to be an element of $Ω$?

  • 0
    I believe it is always useful to include information such as the source of the formula in the question.2012-03-31

1 Answers 1

2

Is $\max_{x_1,x_2,\dots,x_n \in \Omega } \operatorname{card} \{\,x \}$ one single operation, or are max and card two separate operations?

They are two operations.

Is $\{\,x_1,x_2,\dots,x_n\}$ just an arbitrary set of cardinality n? Is it implied to be an element of $\Omega$? Note that you wrote above : $x_1,x_2,\dots,x_n \in \Omega $; which means that $\{x_1,x_2,\dots,x_n\}$ is a subset of $\Omega$.

This set does not necessarily have $n$ elements, since some of the elements $x_1,x_2,\dots,x_n$ might be identical, but as you're looking for maximal possible value, you can assume that they are distinct. (If the set $\Omega$ has at least $n$ elements.)


So the above expression is maximal possible number of different sets which can be obtained as the intersection of some set from $C$ and some set, which has at most $n$ elements.

E.g. if $C=\mathcal P(\Omega)$, i.e. all subsets of $\Omega$ are in $C$, then all subsets of $\{x_1,\dots,x_n\}$ can be obtained for any choice of $\{x_1,\dots,x_n\}$, and the maximum is $2^n$.

If $C=\{\emptyset\}$, then the intersection is always $\emptyset$, so the maximum is $1$. (Since $\{\{x_1,x_2,\dots,x_n\}\cap s; s\in C\}=\{\emptyset\}$ for any choice of $x_1,\dots,x_n$.)