7 papers · 1 filter
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…