Zobrazeno 1 - 10
of 901
pro vyhledávání: '"Pach, János"'
Autor:
Pach, János, Zakharov, Dmitrii
A subset $S$ of real numbers is called bi-Sidon if it is a Sidon set with respect to both addition and multiplication, i.e., if all pairwise sums and all pairwise products of elements of $S$ are distinct. Imre Ruzsa asked the following question: What
Externí odkaz:
http://arxiv.org/abs/2409.03128
A curve in the plane is $x$-monotone if every vertical line intersects it at most once. A family of curves are called pseudo-segments if every pair of them have at most one point in common. We construct $2^{\Omega(n^{4/3})}$ families, each consisting
Externí odkaz:
http://arxiv.org/abs/2405.20547
Autor:
Dumitrescu, Adrian, Pach, János
A \emph{complete geometric graph} consists of a set $P$ of $n$ points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive c
Externí odkaz:
http://arxiv.org/abs/2405.17172
We consider partitions of a point set into two parts, and the lengths of the minimum spanning trees of the original set and of the two parts. If $w(P)$ denotes the length of a minimum spanning tree of $P$, we show that every set $P$ of $n \geq 12$ po
Externí odkaz:
http://arxiv.org/abs/2312.09916
We prove a far-reaching strengthening of Szemer\'edi's regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such a graph can be partitioned into a bounded number of parts of roughly the same size such that almo
Externí odkaz:
http://arxiv.org/abs/2312.01028
Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none of them. It follows from the Erd\H os--Szemer\'edi conjecture, recently
Externí odkaz:
http://arxiv.org/abs/2310.16701
Autor:
Edelsbrunner, Herbert, Pach, János
The Upper Bound Theorem for convex polytopes implies that the $p$-th Betti number of the \v{C}ech complex of any set of $N$ points in $\mathbb R^d$ and any radius satisfies $\beta_{p} = O(N^{m})$, with $m = \min \{ p+1, \lceil d/2 \rceil \}$. We cons
Externí odkaz:
http://arxiv.org/abs/2310.14801
We solve a problem of Dujmovi\'c and Wood (2007) by showing that a complete convex geometric graph on $n$ vertices cannot be decomposed into fewer than $n-1$ star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also dis
Externí odkaz:
http://arxiv.org/abs/2306.13201
Autor:
Pach, János, Tardos, Gábor
Let $P$ be an $N$-element point set in the plane. Consider $N$ (pointlike) grasshoppers sitting at different points of $P$. In a "legal" move, any one of them can jump over another, and land on its other side at exactly the same distance. After a fin
Externí odkaz:
http://arxiv.org/abs/2211.03870