A Note on the Number of General 4-holes in (Perturbed) Grids

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10333360" target="_blank" >RIV/00216208:11320/16:10333360 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-48532-4_1" target="_blank" >http://dx.doi.org/10.1007/978-3-319-48532-4_1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-48532-4_1" target="_blank" >10.1007/978-3-319-48532-4_1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Note on the Number of General 4-holes in (Perturbed) Grids

Popis výsledku v původním jazyce

Considering a variation of the classical Erdos-Szekeres type problems, we count the number of general 4-holes ( not necessarily convex, empty 4-gons) in squared Horton sets of size root nx root n. Improving on previous upper and lower bounds we show that this number is Theta(n(2) log n), which constitutes the currently best upper bound on minimizing the number of general 4-holes for any set of n points in the plane. To obtain the improved bounds, we prove a result of independent interest. We show that Sigma(n)(d=1) phi(d)/d(2) = Theta(log n), where phi(d) is Euler's phifunction, the number of positive integers less than d which are relatively prime to d. This arithmetic function is also called Euler's totient function and plays a role in number theory and cryptography.

Název v anglickém jazyce

A Note on the Number of General 4-holes in (Perturbed) Grids

Popis výsledku anglicky

Considering a variation of the classical Erdos-Szekeres type problems, we count the number of general 4-holes ( not necessarily convex, empty 4-gons) in squared Horton sets of size root nx root n. Improving on previous upper and lower bounds we show that this number is Theta(n(2) log n), which constitutes the currently best upper bound on minimizing the number of general 4-holes for any set of n points in the plane. To obtain the improved bounds, we prove a result of independent interest. We show that Sigma(n)(d=1) phi(d)/d(2) = Theta(log n), where phi(d) is Euler's phifunction, the number of positive integers less than d which are relatively prime to d. This arithmetic function is also called Euler's totient function and plays a role in number theory and cryptography.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

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 statě ve sborníku

DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015

ISBN

978-3-319-48532-4

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

1-12

Název nakladatele

SPRINGER INT PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Kyoto Univ, Kyoto

Datum konání akce

14. 9. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000389794000001