18 papers
Forbidden stars in multidimensional - matrices and visibility of lattice points
Zoltán Füredi, Balázs Keszegh, Paul Manuel
A -dimensional - matrix of size can be considered as a Boolean function $M: B(n_1\times n_2\times \dots \times n_d) \to \{ 0,1\}…
Piercing all maximum cliques in hypergraphs
Andreas Holmsen, Attila Jung, Balázs Keszegh +5
Graphs whose maximum clique size exceeds half of the total number of vertices satisfy a classical property: the family of their maximum sized cliques can be pierced by a single ver…
On the number of tangencies among -intersecting -monotone curves
Eyal Ackerman, Balázs Keszegh
Let $\cC$ be a set of curves in the plane such that no three curves in $\cC$ intersect at a single point and every pair of curves in $\cC$ intersect at exactly one point which is e…
The Zarankiewicz Problem for Polygon Visibility Graphs
Eyal Ackerman, Balázs Keszegh
We prove a quasi-linear upper bound on the size of -free polygon visibility graphs. For visibility graphs of star-shaped and monotone polygons we show a linear bound. In t…
On the maximum number of tangencies among -intersecting curves
Eyal Ackerman, Balázs Keszegh
According to a conjecture of Pach, there are tangent pairs among any family of Jordan arcs in which every pair of arcs has precisely one common point and no three arcs s…
Unavoidable patterns and plane paths in dense topological graphs
Balázs Keszegh, Andrew Suk, Gábor Tardos +1
Let be the complete bipartite geometric graph, with and vertices on two distinct parallel lines respectively, and all straight-line edges drawn between them…