A Note on the Number of General 4-holes in (Perturbed) Grids
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
A Note on the Number of General 4-holes in (Perturbed) Grids
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015
ISBN
978-3-319-48532-4
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
1-12
Publisher name
SPRINGER INT PUBLISHING AG
Place of publication
CHAM
Event location
Kyoto Univ, Kyoto
Event date
Sep 14, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000389794000001