Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $Ω$?

share|improve this question
    
BTW are you sure you did not want to write $\operatorname{card} (\,\{\,x_1,x_2,\dots,x_n\}\cap s), s\in C $ instead of $\operatorname{card} \{\,\{\,x_1,x_2,\dots,x_n\}\cap s, s\in C \}$? I.e. are the outermost brackets supposed to mean set notation? (Originally I understood your question as the first notation, where the maximum is taken over $s\in C$.) –  Martin Sleziak Mar 29 '12 at 11:28
1  
@Martin Yeah, I'm pretty sure. I took the formula from Wikipedia. en.wikipedia.org/wiki/… –  Matt Munson Mar 30 '12 at 8:05
    
I believe it is always useful to include information such as the source of the formula in the question. –  Martin Sleziak Mar 31 '12 at 11:34

1 Answer 1

up vote 2 down vote accepted

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$.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.