Forbidden Intersections (Q3751579)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3987280
Language Label Description Also known as
default for all languages
No label defined
    English
    Forbidden Intersections
    scientific article; zbMATH DE number 3987280

      Statements

      0 references
      0 references
      1987
      0 references
      family of subsets
      0 references
      intersection pattern
      0 references
      Forbidden Intersections (English)
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      About ten years ago P. Erdős conjectured that if \({\mathcal F}\) is a family of subsets of \{1,2,...,n\} without \(F,F'\in {\mathcal F}\), \(| F\cap F'| =[n/4]\), then \(| {\mathcal F}| <(2-\epsilon)^ n\) holds for some positive absolute constant \(\epsilon\). Here this conjecture is proved in a stronger form (Theorem 1.1), which solves a {\$} 250 problem of Erdős. Suppose \({\mathcal C}\) is a code (i.e., a collection of sequences of length n) over an alphabet of q elements, where \(>\delta >0\) is arbitrary. Suppose further that there are no two codewords at Hamming distance d where d is a fixed integer, \(\delta n<d<(1-\delta)n\), and d is even if \(q=2\). Then \(| {\mathcal C}| <(q-\epsilon)^ n\), where \(\epsilon >0\) depends only on q and \(\delta\). The following conjecture of Erdős and Szemerédi is also proved: If \({\mathcal F}\) is a family of subsets of \(\{1,2,...,n\}\) not containing a weak \(\Delta\)-system of size r (cf. definition 1.8), then \(| {\mathcal F}| <(2-\epsilon_ r)^ n\), \(\epsilon_ r>0\) holds. An old conjecture of Larman and Rogers is established in the following stronger form: Let \({\mathcal A}\) be a collection of 4n-dimensional \((\pm 1)\)-vectors, \(r\geq 2\) is a fixed integer. Suppose that A does not contain r pairwise orthogonal vectors. Then \(| {\mathcal A}| <(2- \epsilon)^{4n}.\) All these results can be deduced from our most general result (Theorem 1.16) which concerns the intersection pattern of families of partitions. This result has further implications in Euclidean Ramsey theory as well as for isometric embeddings into the Hamming space \(H(n,q)\) (cf. Theorem 9.1).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references