错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A note on the 2-colored rectilinear crossing number of random point sets in the unit square

  • S. Cabello,
  • É Czabarka,
  • R. Fabila-Monroy,
  • Y. Higashikawa,
  • R. Seidel,
  • L. Székely,
  • J. Tkadlec,
  • A. Wesolek

摘要

Let \(S\) S be a set of four points chosen independently, uniformly at random from a square. Join every pair of points of \(S\) S with a straight line segment. Color these edges red if they have positive slope and blue, otherwise. We show that the probability that \(S\) S defines a pair of crossing edges of the same color is equal to \(1/4\) 1 / 4 . This is connected to a recent result of Aichholzer et al. [1] who showed that by 2-colouring the edges of a geometric graph and counting monochromatic crossings instead of crossings, the number of crossings can be more than halved. Our result shows that for the described random drawings, there is a coloring of the edges such that the number of monochromatic crossings is in expectation \(\frac{1}{2}-\frac{7}{50}\) 1 2 - 7 50 of the total number of crossings.