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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název periodika

Acta Mathematica Hungarica

ISSN

0236-5294

e-ISSN

1588-2632

Svazek periodika

173

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

HU - Maďarsko

Počet stran výsledku

13

Strana od-do

214-226

Kód UT WoS článku

001249545300001

EID výsledku v databázi Scopus

2-s2.0-85196221907