Explicit Ramsey graphs and orthonormal labelings
type: Item
instance of: scholarly article
title: Explicit Ramsey graphs and orthonormal labelings
zbMATH Open document ID: 0814.05056
author: Noga Alon
published in: The Electronic Journal of Combinatorics
publication date: 1995-04-06T00:00:00Z
full work available at URL: https://eudml.org/doc/118590
full work available at URL: R12
review text: Summary: We describe an explicit construction of triangle-free graphs with no independent sets of size \(m\) and with \(\Omega(m^{3/2})\) vertices, improving a sequence of previous constructions by various authors. As a byproduct we show that the maximum possible value of the Lovász \(\theta\)-function of a graph of \(n\) vertices with no independent set of size 3 is \(\Theta(n^{1/3})\), slightly improving a result of Kashin and Konyagin who showed that this maximum is at least \(\Omega(n^{1/3}/\log n)\) and at most \(O(n^{1/3})\). Our results imply that the maximum possible Euclidean norm of a sum of \(n\) unit vectors in \(\mathbb{R}^ n\), so that among any three of them some two are orthogonal, is \(\Theta(n^{2/3})\).
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 741553
zbMATH Keywords: Ramsey graphs
zbMATH Keywords: orthonormal labelings
zbMATH Keywords: Lovász function
zbMATH Keywords: triangle-free graphs
zbMATH Keywords: independent sets
MaRDI profile type: Publication
Recommended article: Ramsey properties of orientations of graphs
Recommended article: Q4004437
Recommended article: Q4100120
Recommended article: Q4105701
Recommended article: Q4100121
Recommended article: Q3054758
Recommended article: On the Ramsey multiplicity of complete graphs
Recommended article: On graphs with linear Ramsey numbers
Recommended article: Q3680868
Recommended article: On the Ramsey-Turán numbers of graphs and hypergraphs
description: scientific article; zbMATH DE number 741553