## How many minimal pair-wise coverings can there be?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Suppose I have a set of finite sets: $X = \{V_1, V_2, V_3\}$ where each set called $V_i$ in $X$ contains a number of symbols (i.e. $V_1 = \{a,b,c\}$). $Z$ contains all of the Cartesian products of pairs of sets chosen from $X$. So in this case $Z = \{V_1 \times V_2, V_1 \times V_3, V_2 \times V_3\}$. A "word" is a set with each character at position $i$ drawn from the corresponding $V_i$. The set of all words is $W = V_1 \times V_2 \times V_3$. A "sentence" is an ordered set of "words" taken from $W$.

How many "sentences" of minimal length can I make such that every pair from $Z$ is in that "sentence" at least once? Minimal means fewest possible number of "words."

-

Are $V_1,V_2,V_3$ disjoint sets? – Hsueh-Yung Lin Jun 16 2011 at 16:24
yes... I wouldn't consider pairs made from elements within a single $V_i$ to be valid. For example if $V_1 = \\{a,b,c\\}$ and $V_2 = \\{1,2,3\\}$, "words" starting with $\\{a,1,...\\}$ would be valid but "words" like ${a,a,...}$ or ${1,1,...}$ would not be since a "word" is an ordered set where each character at position $i$ may only be drawn from the corresponding $V_i$. – Misha Jun 16 2011 at 17:41
It is not clear to me what it means for a pair from $Z$ to be "in" a sentence. Your sentence is an ordered $n$-tuple of ordered triples; what do you mean by asking that a pair be in such an $n$-tuple? Maybe an example of sets $V_1,V_2,V_3$ together with a minimal sentence would help.  – Gerry Myerson Jun 16 2011 at 23:41
Here's an example of what I mean:   $V_1=\{a,b\}$,  $V_2=\{c,d\}$,  $V_3=\{e,f\}$.  $V_1 \times V_2 \times V_3 = \{ace,acf,ade,adf,bce,bcf,bde,bdf\}$  There are 12 total pairs: $Z=\{\{ac,ad,bc,bd\},\{ae,af,be,bf\},\{ce,cf,de,df\}\}$.  A minimal acceptable sentence is:  $S=\{acf,ade,bce,bdf\}$.  ...another is $\{ace,adf,bcf,bde\}$ – Misha Jun 17 2011 at 3:53
@Misha, thanks, now I think I understand the question (but regret I don't have a solution). Can you answer the question of how many minimal sentences there are in your example? – Gerry Myerson Jun 17 2011 at 12:29
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9480363726615906, "perplexity_flag": "head"}