Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs (Q1586354)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs |
scientific article |
Statements
Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs (English)
0 references
13 November 2000
0 references
It is shown that for any integer \(m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\) (represented as a product of prime powers) there exists \(c=c(m)>0\), such that for any \(h\) there exists a system \(\mathcal H\) of subsets of an \(h\)-element set satisfying the folowing three conditions: (a) \(|{\mathcal H}|\geq \exp(c{(\log h)^r\over (\log\log h)^{r-1}})\), (b) \(|H|\equiv 0\pmod m\) for each \(H\in{\mathcal H}\), (c) \(|G\cap H|\neq 0\pmod m\), for all distinct \(G,H\in{\mathcal H}\). This result, in particular, answers in the negative some long-standing questions of \textit{P. Frankl} and \textit{R. M. Wilson} [Combinatorica 1, 357-368 (1981; Zbl 0498.05048)] and \textit{L. Babai} and \textit{P. Frankl} [Linear algebra methods in combinatorics, University of Chicago, preprint]. Another application is an alternative construction of explicit Ramsey graphs of size \(\exp(c\log^2n/\log\log n)\).
0 references
Ramsey graphs
0 references
intersection systems
0 references