TIDIER EXAMPLES FOR LOWER BOUNDS ON DIAGONAL RAMSEY NUMBERS

Authors
MCDIARMID C STEGER A
Citation
C. Mcdiarmid et A. Steger, TIDIER EXAMPLES FOR LOWER BOUNDS ON DIAGONAL RAMSEY NUMBERS, J COMB TH A, 74(1), 1996, pp. 147-152
Citations number
4
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN journal
00973165 → ACNP
Volume
74
Issue
1
Year of publication
1996
Pages
147 - 152
Database
ISI
SICI code
0097-3165(1996)74:1<147:TEFLBO>2.0.ZU;2-2
Abstract
There is a family (H-k) of graphs such that H-k has order (1 + o(1))(r oot 2/e)k2(k/2) but has no clique or stable set of order Ic. This resu lt of Spencer provides the best known lower bound for the diagonal Ram sey numbers R(k, k). Here we see that the graphs H-k can be taken to b e regular, self-complementary, and pseudo-random. (C) 1996 Academic Pr ess, Inc.