Large sets of nearly orthogonal vectors

Noga Alon; Mario Szegedy

Large sets of nearly orthogonal vectors

Noga Alon
, Mario Szegedy

Research output: Contribution to journal › Article › peer-review

Abstract

It is shown that there is an absolute positive constant δ > 0, so that for all positive integers k and d, there are sets of at least d^{δ log2(k+2)/log2 log2(k+2)} nonzero vectors in R^d, in which any k + 1 members contain an orthogonal pair. This settles a problem of Füredi and Stanley.

Original language	English (US)
Pages (from-to)	1-4
Number of pages	4
Journal	Graphs and Combinatorics
Volume	15
Issue number	1
State	Published - 1999
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Cite this

@article{38516e4e4b2d4610bcad96caaddaa970,

title = "Large sets of nearly orthogonal vectors",

abstract = "It is shown that there is an absolute positive constant δ > 0, so that for all positive integers k and d, there are sets of at least dδ log2(k+2)/log2 log2(k+2) nonzero vectors in Rd, in which any k + 1 members contain an orthogonal pair. This settles a problem of F{\"u}redi and Stanley.",

author = "Noga Alon and Mario Szegedy",

year = "1999",

language = "English (US)",

volume = "15",

pages = "1--4",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Large sets of nearly orthogonal vectors

AU - Alon, Noga

AU - Szegedy, Mario

PY - 1999

Y1 - 1999

N2 - It is shown that there is an absolute positive constant δ > 0, so that for all positive integers k and d, there are sets of at least dδ log2(k+2)/log2 log2(k+2) nonzero vectors in Rd, in which any k + 1 members contain an orthogonal pair. This settles a problem of Füredi and Stanley.

AB - It is shown that there is an absolute positive constant δ > 0, so that for all positive integers k and d, there are sets of at least dδ log2(k+2)/log2 log2(k+2) nonzero vectors in Rd, in which any k + 1 members contain an orthogonal pair. This settles a problem of Füredi and Stanley.

UR - https://www.scopus.com/pages/publications/0009920986

UR - https://www.scopus.com/pages/publications/0009920986#tab=citedBy

M3 - Article

AN - SCOPUS:0009920986

SN - 0911-0119

VL - 15

SP - 1

EP - 4

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Large sets of nearly orthogonal vectors

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this