On the geometric Ramsey number of outerplanar graphs (Q2256584): Difference between revisions

The geometric Ramsey number \(n\) of a graph is the smallest integer where every complete geometric graph on \(n\) vertices with edges arbitarily colored by two colors contains a monochromatic non-crossing copy of the original graph. For any integer \(n\), a ladder graph on \(2n\) vertices is the graph composed of two paths \((u_i)_{i=1}^n\) and \((v_i)_{i=1}^n\) together with the set of edges \(\{u_iv_i: i =1,\ldots,n\}\). From the authors' summary:``We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on \(2n\) vertices are bounded by \(O(n^3)\) and \(O(n^{10})\), in the convex and general case, respectively. We then apply similar methods to prove an \(n^{O(\log(n))}\) upper bound on the Ramsey number of a path with \(n\) ordered vertices''.