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

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

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.

• Jezik: Angleški jezik
• Ključne besede: arrangement of points, flat, hyperplane
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.06.2024
• Leto izida: 2024
• Št. strani: Str. 214-226
• Številčenje: Vol. 173, iss. 1
• PID: 20.500.12556/RUL-163170
• UDK: 514.17
• ISSN pri članku: 0236-5294
• DOI: 10.1007/s10474-024-01436-9
• COBISS.SI-ID: 206428931
• Datum objave v RUL: 03.10.2024

CABELLO, Sergio, CZABARKA, Éva, FABILA-MONROY, Ruy, HIGASHIKAWA, Yuya, SEIDEL, Raimund, SZÉKELY, László, TKADLEC, Josef in WESOLEK, Alexandra, 2024, A note on the 2-colored rectilinear crossing number of random point sets in the unit square. Acta mathematica Hungarica [na spletu]. 2024. Vol. 173, no. 1, p. 214–226. [Dostopano 26 april 2025]. DOI 10.1007/s10474-024-01436-9. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=163170

Gradivo je del revije

• Naslov: Acta mathematica Hungarica
• Skrajšan naslov: Acta math. Hung.
• Založnik: Akadémiai Kiadó, Springer
• ISSN: 0236-5294
• COBISS.SI-ID: 27704576

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.