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