Constructive bounds for a Ramsey-type problem
type: Item
instance of: scholarly article
title: Constructive bounds for a Ramsey-type problem
zbMATH Open document ID: 0890.05050
DOI: 10.1007/BF03352998
author: Noga Alon
author: Michael Krivelevich
published in: Graphs and Combinatorics
publication date: 1998-06-22T00:00:00Z
review text: Many important bounds for the Ramsey function \(R(s,t)\) are proved using probabilistic techniques. Some additional constructive ideas have been developed in recent years, but they usually give weaker bounds. The authors consider a more general Ramsey type function, and give constructive bounds for this function. In particular, given integers \(r\) and \(s\) with \(2 \leq r < s\), they construct a graph \(H = H_{r,s,n}\) of order \(n\) such that for some \(\varepsilon = \varepsilon(r,s)\), \(H\) contains no clique of order \(s\) and every subset with at least \(n^{1 - \varepsilon}\) vertices contains a clique of size \(r\). These constructions use properties of finite geometries and geometric expanders.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05B25
zbMATH DE Number: 1106797
zbMATH Keywords: Ramsey numbers
zbMATH Keywords: finite geometries
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
cites work: Tough Ramsey graphs without short cycles
cites work: Explicit Ramsey graphs and orthonormal labelings
cites work: An asymptotic isoperimetric inequality
cites work: Explicit construction of linear sized tolerant networks
cites work: Q4004078
cites work: Q3682518
cites work: Graphs without large triangle free subgraphs
cites work: A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\)
cites work: On the construction of certain graphs
cites work: Q3284375
cites work: The Construction of Certain Graphs
cites work: Intersection theorems with geometric consequences
cites work: Q3997075
cites work: Q3715120
cites work: On a combinatorial conjecture of Erdös
cites work: Ks-Free Graphs Without Large Kr-Free Subgraphs
cites work: Bounding Ramsey numbers through large deviation inequalities
cites work: Q3496342
cites work: Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
cites work: Concentration of measure and isoperimetric inequalities in product spaces
full work available at URL: https://doi.org/10.1007/bf03352998
OpenAlex ID: W2015922523
description: scientific article; zbMATH DE number 1106797