Explicit Ramsey graphs and orthonormal labelings
Explicit Ramsey graphs and orthonormal labelings
复制标题
显式拉姆齐图和正交标记
DOI：
--
复制
发表时间：
1994
影响因子：
0.7
通讯作者：
N. Alon
中科院分区：
文献类型：
--
作者：
N. Alon
我们描述了无独立的大小M和›（m 3 = 2）顶点的无独立图的显式结构，从而改善了各种作者的先前构造序列。 lovasz µ函数在n个顶点上没有独立的3个尺寸3的函数是£（n 1 = 3），略微改善了Kashin和Konyagin的结果，Kanyagin和Konyagin表明该最大值至少为›（n 1 = 3 = logn）和最多O（n 1 = 3）。 £（n 2 = 3）。
We describe an explicit construction of triangle-free graphs with no independent sets of size m and with ›(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 Lovasz µ-function of a graph on n vertices with no independent set of size 3 is £(n 1=3 ), slightly improving a result of Kashin and Konyagin who showed that this maximum is at least ›(n 1=3 = logn) and at most O(n 1=3 ). Our results imply that the maximum possible Euclidean norm of a sum of n unit vectors in R n , so that among any three of them some two are orthogonal, is £(n 2=3 ).