Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs (Q1586354)

From MaRDI portal
Revision as of 14:14, 23 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references