Long alternating paths in bicolored point sets

Result code in IS VaVaI

RIV/00216208:11320/08:00100927 - isvavai.cz

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Long alternating paths in bicolored point sets

Original language description

Given n red and n blue points in convex position in the plane, we show that there exists a noncrossing alternating path of length n + c(n/log n)^{1/2}. We disprove a conjecture of Erdős by constructing an example without any such path of length greater than 4n/3 + c'n^{1/2}.

Czech name

Dlouhé alternující cesty v dvouobarvených množinách bodů

Czech description

Ukážeme, že v každé množině n červených a n modrých bodů v rovině v konvexní poloze existuje nekřížící se alternující cesta délky n + c(n/log n)^{1/2}. Vyvrátítme Erdősovu domněnku sestrojením příkladu, kde není žádná taková cesta délky větsí než 4n/3 +c'n^{1/2}.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

1M0545: Institute for Theoretical Computer Science

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
S - Specificky vyzkum na vysokych skolach

Publication year

2008

Confidentiality

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

Name of the periodical

Discrete Mathematics

ISSN

0012-365X

e-ISSN

—

Volume of the periodical

308

Issue of the periodical within the volume

19

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

7

Pages from-to

—

UT code for WoS article

000257978700003

EID of the result in the Scopus database

—