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
1987
0 references
family of subsets
0 references
intersection pattern
0 references
Forbidden Intersections (English)
0 references
0 references
0.8112451434135437
0 references
0.8069881200790405
0 references
0.806937575340271
0 references
0.806588351726532
0 references
0.8035338521003723
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