Search Results

Documents authored by Frankl, Nóra

Document
DOI: 10.4230/LIPIcs.SoCG.2023.8
On Helly Numbers of Exponential Lattices

Authors: Gergely Ambrus, Martin Balko, Nóra Frankl, Attila Jung, and Márton Naszódi

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Given a set S ⊆ ℝ², define the Helly number of S, denoted by H(S), as the smallest positive integer N, if it exists, for which the following statement is true: for any finite family ℱ of convex sets in ℝ² such that the intersection of any N or fewer members of ℱ contains at least one point of S, there is a point of S common to all members of ℱ. We prove that the Helly numbers of exponential lattices {αⁿ : n ∈ ℕ₀}² are finite for every α > 1 and we determine their exact values in some instances. In particular, we obtain H({2ⁿ : n ∈ ℕ₀}²) = 5, solving a problem posed by Dillon (2021). For real numbers α, β > 1, we also fully characterize exponential lattices L(α,β) = {αⁿ : n ∈ ℕ₀} × {βⁿ : n ∈ ℕ₀} with finite Helly numbers by showing that H(L(α,β)) is finite if and only if log_α(β) is rational.
Cite as

Gergely Ambrus, Martin Balko, Nóra Frankl, Attila Jung, and Márton Naszódi. On Helly Numbers of Exponential Lattices. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ambrus_et_al:LIPIcs.SoCG.2023.8,
  author =	{Ambrus, Gergely and Balko, Martin and Frankl, N\'{o}ra and Jung, Attila and Nasz\'{o}di, M\'{a}rton},
  title =	{{On Helly Numbers of Exponential Lattices}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.8},
  URN =		{urn:nbn:de:0030-drops-178584},
  doi =		{10.4230/LIPIcs.SoCG.2023.8},
  annote =	{Keywords: Helly numbers, exponential lattices, Diophantine approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.47
Almost-Monochromatic Sets and the Chromatic Number of the Plane

Authors: Nóra Frankl, Tamás Hubai, and Dömötör Pálvölgyi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
In a colouring of ℝ^d a pair (S,s₀) with S ⊆ ℝ^d and with s₀ ∈ S is almost-monochromatic if S⧵{s₀} is monochromatic but S is not. We consider questions about finding almost-monochromatic similar copies of pairs (S,s₀) in colourings of ℝ^d, ℤ^d, and of ℚ under some restrictions on the colouring. Among other results, we characterise those (S,s₀) with S ⊆ ℤ for which every finite colouring of ℝ without an infinite monochromatic arithmetic progression contains an almost-monochromatic similar copy of (S,s₀). We also show that if S ⊆ ℤ^d and s₀ is outside of the convex hull of S⧵{s₀}, then every finite colouring of ℝ^d without a monochromatic similar copy of ℤ^d contains an almost-monochromatic similar copy of (S,s₀). Further, we propose an approach based on finding almost-monochromatic sets that might lead to a human-verifiable proof of χ(ℝ²) ≥ 5.
Cite as

Nóra Frankl, Tamás Hubai, and Dömötör Pálvölgyi. Almost-Monochromatic Sets and the Chromatic Number of the Plane. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{frankl_et_al:LIPIcs.SoCG.2020.47,
  author =	{Frankl, N\'{o}ra and Hubai, Tam\'{a}s and P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
  title =	{{Almost-Monochromatic Sets and the Chromatic Number of the Plane}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.47},
  URN =		{urn:nbn:de:0030-drops-122054},
  doi =		{10.4230/LIPIcs.SoCG.2020.47},
  annote =	{Keywords: discrete geometry, Hadwiger-Nelson problem, Euclidean Ramsey theory}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.48
Almost Sharp Bounds on the Number of Discrete Chains in the Plane

Authors: Nóra Frankl and Andrey Kupavskii

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
The following generalisation of the Erdős unit distance problem was recently suggested by Palsson, Senger and Sheffer. For a sequence δ=(δ₁,… ,δ_k) of k distances, a (k+1)-tuple (p₁,… ,p_{k+1}) of distinct points in ℝ^d is called a (k,δ)-chain if ‖p_j-p_{j+1}‖ = δ_j for every 1 ≤ j ≤ k. What is the maximum number C_k^d(n) of (k,δ)-chains in a set of n points in ℝ^d, where the maximum is taken over all δ? Improving the results of Palsson, Senger and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k ≡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3.
Cite as

Nóra Frankl and Andrey Kupavskii. Almost Sharp Bounds on the Number of Discrete Chains in the Plane. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{frankl_et_al:LIPIcs.SoCG.2020.48,
  author =	{Frankl, N\'{o}ra and Kupavskii, Andrey},
  title =	{{Almost Sharp Bounds on the Number of Discrete Chains in the Plane}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.48},
  URN =		{urn:nbn:de:0030-drops-122064},
  doi =		{10.4230/LIPIcs.SoCG.2020.48},
  annote =	{Keywords: unit distance problem, unit distance graphs, discrete chains}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact