Search Results

Documents authored by Zeng, Ji

Document
DOI: 10.4230/LIPIcs.SoCG.2024.46
Saturation Results Around the Erdős-Szekeres Problem

Authors: Gábor Damásdi, Zichao Dong, Manfred Scheucher, and Ji Zeng

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
In this paper, we consider saturation problems related to the celebrated Erdős-Szekeres convex polygon problem. For each n ≥ 7, we construct a planar point set of size (7/8) ⋅ 2^{n-2} which is saturated for convex n-gons. That is, the set contains no n points in convex position while the addition of any new point creates such a configuration. This demonstrates that the saturation number is smaller than the Ramsey number for the Erdős-Szekeres problem. The proof also shows that the original Erdős-Szekeres construction is indeed saturated. Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number.
Cite as

Gábor Damásdi, Zichao Dong, Manfred Scheucher, and Ji Zeng. Saturation Results Around the Erdős-Szekeres Problem. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{damasdi_et_al:LIPIcs.SoCG.2024.46,
  author =	{Dam\'{a}sdi, G\'{a}bor and Dong, Zichao and Scheucher, Manfred and Zeng, Ji},
  title =	{{Saturation Results Around the Erd\H{o}s-Szekeres Problem}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.46},
  URN =		{urn:nbn:de:0030-drops-199919},
  doi =		{10.4230/LIPIcs.SoCG.2024.46},
  annote =	{Keywords: Convex polygon, Cups-versus-caps, Monotone path, Saturation problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.59
On Higher Dimensional Point Sets in General Position

Authors: Andrew Suk and Ji Zeng

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

Abstract
A finite point set in ℝ^d is in general position if no d + 1 points lie on a common hyperplane. Let α_d(N) be the largest integer such that any set of N points in ℝ^d with no d + 2 members on a common hyperplane, contains a subset of size α_d(N) in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that α₂(N) < N^{5/6 + o(1)}. In this paper, we also use the container method to obtain new upper bounds for α_d(N) when d ≥ 3. More precisely, we show that if d is odd, then α_d(N) < N^{1/2 + 1/(2d) + o(1)}, and if d is even, we have α_d(N) < N^{1/2 + 1/(d-1) + o(1)}. We also study the classical problem of determining the maximum number a(d,k,n) of points selected from the grid [n]^d such that no k + 2 members lie on a k-flat. For fixed d and k, we show that a(d,k,n)≤ O(n^{d/{2⌊(k+2)/4⌋}(1- 1/{2⌊(k+2)/4⌋d+1})}), which improves the previously best known bound of O(n^{d/⌊(k + 2)/2⌋}) due to Lefmann when k+2 is congruent to 0 or 1 mod 4.
Cite as

Andrew Suk and Ji Zeng. On Higher Dimensional Point Sets in General Position. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{suk_et_al:LIPIcs.SoCG.2023.59,
  author =	{Suk, Andrew and Zeng, Ji},
  title =	{{On Higher Dimensional Point Sets in General Position}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{59:1--59:13},
  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.59},
  URN =		{urn:nbn:de:0030-drops-179097},
  doi =		{10.4230/LIPIcs.SoCG.2023.59},
  annote =	{Keywords: independent sets, hypergraph container method, generalised Sidon sets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.62
A Positive Fraction Erdős-Szekeres Theorem and Its Applications

Authors: Andrew Suk and Ji Zeng

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
A famous theorem of Erdős and Szekeres states that any sequence of n distinct real numbers contains a monotone subsequence of length at least √n. Here, we prove a positive fraction version of this theorem. For n > (k-1)², any sequence A of n distinct real numbers contains a collection of subsets A_1,…, A_k ⊂ A, appearing sequentially, all of size s = Ω(n/k²), such that every subsequence (a_1,…, a_k), with a_i ∈ A_i, is increasing, or every such subsequence is decreasing. The subsequence S = (A_1,…, A_k) described above is called block-monotone of depth k and block-size s. Our theorem is asymptotically best possible and follows from a more general Ramsey-type result for monotone paths, which we find of independent interest. We also show that for any positive integer k, any finite sequence of distinct real numbers can be partitioned into O(k²log k) block-monotone subsequences of depth at least k, upon deleting at most (k-1)² entries. We apply our results to mutually avoiding planar point sets and biarc diagrams in graph drawing.
Cite as

Andrew Suk and Ji Zeng. A Positive Fraction Erdős-Szekeres Theorem and Its Applications. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{suk_et_al:LIPIcs.SoCG.2022.62,
  author =	{Suk, Andrew and Zeng, Ji},
  title =	{{A Positive Fraction Erd\H{o}s-Szekeres Theorem and Its Applications}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.62},
  URN =		{urn:nbn:de:0030-drops-160703},
  doi =		{10.4230/LIPIcs.SoCG.2022.62},
  annote =	{Keywords: Erd\H{o}s-Szekeres, block-monotone, monotone biarc diagrams, mutually avoiding sets}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact