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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10486573" target="_blank" >RIV/00216208:11320/24:10486573 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1r3YGRGAyD" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1r3YGRGAyD</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10474-024-01436-9" target="_blank" >10.1007/s10474-024-01436-9</a>

Result language

angličtina

Original language name

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

Original language description

Let S documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$S$$end{document} be a set of four points chosen independently, uniformly at random from a square. Join every pair of points of S documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$S$$end{document} with a straight line segment. Color these edges red if they have positive slope and blue, otherwise. We show that the probability that S documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$S$$end{document} defines a pair of crossing edges of the same color is equal to 1 / 4 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$1/4$$end{document} . 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 1 2 - 7 50 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$frac{1}{2}-frac{7}{50}$$end{document} of the total number of crossings.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Acta Mathematica Hungarica

ISSN

0236-5294

e-ISSN

1588-2632

Volume of the periodical

173

Issue of the periodical within the volume

1

Country of publishing house

HU - HUNGARY

Number of pages

13

Pages from-to

214-226

UT code for WoS article

001249545300001

EID of the result in the Scopus database

2-s2.0-85196221907