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

Cabello, Sergio (author), Czabarka, Éva (author), Fabila-Monroy, Ruy (author), Higashikawa, Yuya (author), Seidel, Raimund (author), Székely, László (author), Tkadlec, Josef (author), Wesolek, Alexandra (author)

Let $S$ be a set of four points chosen independently, uniformly at random from a square. Join every pair of points of $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$ defines a pair of crossing edges of the same color is equal to $1/4$. This is connected to a recent result of Aichholzer et al. 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 ${1 \over 2} - {7 \over 50}$ of the total number of crossings.

• Language: English
• Keywords: arrangement of points, flat, hyperplane
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.06.2024
• Year: 2024
• Number of pages: Str. 214-226
• Numbering: Vol. 173, iss. 1
• PID: 20.500.12556/RUL-163170
• UDC: 514.17
• ISSN on article: 0236-5294
• DOI: 10.1007/s10474-024-01436-9
• COBISS.SI-ID: 206428931
• Publication date in RUL: 03.10.2024

Record is a part of a journal

• Title: Acta mathematica Hungarica
• Shortened title: Acta math. Hung.
• Publisher: Akadémiai Kiadó, Springer
• ISSN: 0236-5294
• COBISS.SI-ID: 27704576

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.