12 papers
Coloring Geometric Hypergraphs: A Survey
Gábor Damásdi, Balázs Keszegh, János Pach +2
The \emph{chromatic number} of a hypergraph is the smallest number of colors needed to color the vertices such that no edge of at least two vertices is monochromatic. Given a famil…
Non-dissective coverings by planks
Andrey Kupavskii, Janos Pach
A plank is the part of space between two parallel planes. The following open problem, posed 45 years ago, can be viwed as the converse of Tarski's plank problem (Bang's theorem): I…
Note on the Number of Almost Ordinary Triangles
Adrian Dumitrescu, János Pach
Let be a set of points in the plane, not all on a line. According to the Gallai-Sylvester theorem, always spans an \emph{ordinary line}, i.e., one that passes through p…
Erdős's unit distance problem and rigidity
János Pach, Orit E. Raz, József Solymosi
According to a classical result of Spencer, Szemerédi, and Trotter (1984), the maximum number of times the unit distance can occur among points in the plane is . Th…
Covering Complete Geometric Graphs by Monotone Paths
Adrian Dumitrescu, János Pach, Morteza Saghafian +1
Given a set of points (vertices) in general position in the plane, the \emph{complete geometric graph} consists of all segments (edges) between the…
On the number of edges of restricted matchstick graphs
Panna Gehér, János Pach, Konrad Swanepoel +1
A graph whose vertices are points in the plane and whose edges are noncrossing straight-line segments of unit length is called a \emph{matchstick graph}. We prove two somewhat coun…
A Purely Geometric Variant of the Gale-Berlekamp Switching Game
Adrian Dumitrescu, Jeck Lim, János Pach +1
We introduce the following variant of the Gale-Berlekamp switching game. Let be a set of n noncollinear points in the plane, each of them having weight or . At each st…
Enumeration of intersection graphs of -monotone curves
Jacob Fox, Janos Pach, Andrew Suk
A curve in the plane is -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 i…
Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs
Adrian Dumitrescu, János Pach
A \emph{complete geometric graph} consists of a set of points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bo…
Two trees are better than one
Adrian Dumitrescu, János Pach, Géza Tóth
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 denotes the length of a mini…
Maximum Betti numbers of Čech complexes
Herbert Edelsbrunner, János Pach
The Upper Bound Theorem for convex polytopes implies that the -th Betti number of the Čech complex of any set of points in and any radius satisfies $β_{p} = O(…
Order-forcing in Neural Codes
R. Amzi Jeffs, Caitlin Lienkaemper, Nora Youngs
Convex neural codes are subsets of the Boolean lattice that record the intersection patterns of convex sets in Euclidean space. Much work in recent years has focused on finding com…