On weighted Ramsey numbers

Original · EN

The weighted Ramsey number, wR(n,k), is the minimum q such that there is an assignment of nonnegative real numbers (weights) to the edges of Kₙ with the total sum of the weights equal to n 2 and there is a Red/Blue coloring of edges of the same Kₙ, such that in any complete k-vertex subgraph H, of Kₙ, the sum of the weights on Red edges in H is at most q and the sum of the weights on Blue edges in H is at most q. This concept was introduced recently by Fujisawa and Ota. We provide new bounds on wR(n,k), for k≥ 4 and n large enough and show that determining wR(n,3) is asymptotically equivalent to the problem of finding the fractional packing number of monochromatic triangles in colorings of edges of complete graphs with two colors.