TAILIEUCHUNG - Báo cáo toán học: "Explicit Ramsey graphs and orthonormal labelings"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Explicit Ramsey graphs and orthonormal labelings. | Explicit Ramsey graphs and orthonormal labelings Noga Alon Submitted August 22 1994 Accepted October 29 1994 Abstract We describe an explicit construction of triangle-free graphs with no independent sets of size m and with - m3 2 vertices improving a sequence of previous constructions by various authors. As a byproduct we show that the maximum possible value of the Lovasz -function of a graph on n vertices with no independent set of size 3 is 0 n1 3 slightly improving a result of Kashin and Konyagin who showed that this maximum is at least - n1 3 logn and at most O nl 3f. Our results imply that the maximum possible Euclidean norm of a sum of n unit vectors in Rn so that among any three of them some two are orthogonal is 0 n2 3 . 1 Introduction Let R 3 m denote the maximum number of vertices of a triangle-free graph whose independence number is at most m. The problem of determining or estimating R 3 m is a well studied Ramsey type problem. Ajtai Komlós and Szemeredi proved in 1 that R 3 m O m2 log m see also 17 for an estimate with a better constant . Improving a result of Erdos who showed in 7 that R 3 m - m logm 2 see also 18 13 or 4 for a simpler proof Kim 10 proved very recently that the upper bound is tight up to a constant factor that is R 3 m 0 m2 logm . His proof as well as that of Erdos is probabilistic and does not supply any explicit construction of such a graph. The problem of finding an explicit construction of triangle-free graphs of independence number m and many vertices has also received a considerable amount of attention. Erdos 8 gave an explicit construction of such graphs with - m 2log2 3 log3-log2 - m1 13 vertices. This has been improved by Cleve and Dagum 6 and improved further by Chung Cleve and Dagum in 5 where the authors present a construction with - mlog6 log4 - m1 29 AT T Bell Labs Murray Hill NJ 07974 USA and Department of Mathematics Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv Israel. Research .

• Báo cáo khoa học
• tài liệu báo cáo nghiện cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội