On Well-Connected Sets of Strings

SUMMARY

Given nn sets X1,…,XnX_1,\ldots, X_n, we call the elements of S=X1×?×XnS=X_1\times\cdots\times X_n strings. A nonempty set of strings W?SW\subseteq S is said to be well-connected if for every v?Wv\in W and for every i(1=i=n)i\, (1\le i\le n), there is another element v'?Wv'\in W which differs from vv only in its iith coordinate. We prove a conjecture of Yaokun Wu and Yanzhen Xiong by showing that every set of more than ?ni=1|Xi|-?ni=1(|Xi|-1)\prod_{i=1}^n|X_i|-\prod_{i=1}^n(|X_i|-1) strings has a well-connected subset. This bound is tight.