기초과학연구원 이산수학그룹
On January 23, 2024, Zichao Dong from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on a d-dimensional analog of a variation of the Erdős-Szekeres problem among n points of bounded pairwise distances. The title of his talk was “Convex polytopes in non-elongated point sets in R^d“.
The IBS Discrete Mathematics Group welcomes Zichao Dong and Ander Lamaison, two new research fellows at the IBS Extremal Combinatorics and Probability Group and welcomes Qiang Zhou, a new visiting student of the IBS Extremal Combinatorics and Probability Group.
Dr. Zichao Dong received his Ph.D. from the Carnegie Mellon University in 2023 under the supervision of Prof. Boris Bukh.
Dr. Ander Lamaison received his Ph.D. from the Freie Universität Berlin in 2021 under the supervision of Prof. Tibor Szabó.
Qiang Zhou is a graduate student from the Chinese Academy of Sciences. He will stay until the end of June 2024.
For any finite point set $P \subset \mathbb{R}^d$, we denote by $\text{diam}(P)$ the ratio of the largest to the smallest distances between pairs of points in $P$. Let $c_{d, \alpha}(n)$ be the largest integer $c$ such that any $n$-point set $P \subset \mathbb{R}^d$ in general position, satisfying $\text{diam}(P) < \alpha\sqrt[d]{n}$ (informally speaking, `non-elongated’), contains a convex $c$-polytope. Valtr proved that $c_{2, \alpha}(n) \approx \sqrt[3]{n}$, which is asymptotically tight in the plane. We generalize the results by establishing $c_{d, \alpha}(n) \approx n^{\frac{d-1}{d+1}}$. Along the way we generalize the definitions and analysis of convex cups and caps to higher dimensions, which may be of independent interest. Joint work with Boris Bukh.