An intersection problem for codes (Q922561)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An intersection problem for codes
scientific article

    Statements

    An intersection problem for codes (English)
    0 references
    1990
    0 references
    Let \([s]^ n\) denote the set of sequences \((a_ 1,...,a_ n)\) with \(1\leq a_ i\leq s\). Let A be a subset of \([s]^ n\). It is called \((t_ 1,...,t_ s)\)-intersecting if for all \b{a} and ḇ in A and for every \(1\leq i\leq s\) there are at least \(t_ i\) positions j such that \(a_ j=b_ j=i\). Let \(m(n,(t_ 1,...,t_ s))\) be defined as the maximum size of such a set A. In the introduction the author states the conjecture of Winkler: \[ m(n,(t_ 1,...,t_ s))=\max_{n_ 1+...+n_ s=n}\prod^{s}_{i=1}m(n_ i,(0,...,t_ i,...,0)). \] He claims to have proved this conjecture in case \(t_ i<s\) for all i. Moreover he claims to have proved the following theorem: if \(t_ i<s\) for all i then \(m(n,(t_ 1,...,t_ s))=s^{n-t_ 1-...-t_ s}\) for all \(n\geq t_ 1+...+t_ s.\) According to me what he really proves is: \(P((t_ 1,...,t_ s))=\lim m(n,(t_ 1,...,t_ s))/s^ n\) exists and is equal to \(\prod^{s}_{i=1}p((0,...,t_ i,...,0)).\) Of course this is a strong indication for the truth of the conjecture of Winkler, but is not a proof. Furthermore he proves \(m(n,(t,0,...,0))=s^{n-t}\) if \(s\geq t+1\) and \(n\geq t\), which together with the conjecture would prove the theorem.
    0 references
    intersecting sets
    0 references
    0 references

    Identifiers