Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
type: Item
instance of: scholarly article
title: Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
zbMATH Open document ID: 0949.05083
author: Vince Grolmusz
published in: Combinatorica
publication date: 2000-11-13T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1528648
zbMATH Keywords: Ramsey graphs
zbMATH Keywords: intersection systems
reviewed by: Sergej L. Bezrukov
MaRDI profile type: Publication
full work available at URL: s004930070032
OpenAlex ID: W2069582894
DOI: 10.1007/S004930070032
Recommended article: Supersaturation for Ramsey-Turán problems
Recommended article: Restricted size Ramsey number for P3 versus dense connected graphs of order six
Recommended article: Q4293771
Recommended article: On the Size‐Ramsey Number of Hypergraphs
Recommended article: Q5202212
Recommended article: Q4326638
Recommended article: Ramsey numbers of semi-algebraic and semi-linear hypergraphs
Recommended article: Supereulerian graphs, independent sets, and degree-sum conditions
Recommended article: Set-coloring of edges and multigraph Ramsey numbers
Recommended article: Ramsey numbers of Berge-hypergraphs and related structures
description: scientific article; zbMATH DE number 1528648