Personne

János Pach

Decomposition of geometric graphs into star-forests

We solve a problem of Dujmović 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 discuss similar ...

2025

A Farewell to Eli Goodman

János Pach

SPRINGER2024

A Crossing Lemma for Multigraphs

János Pach

Let G be a drawing of a graph with n vertices and e > 4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the nu ...

SPRINGER2020

The Schur-Erdos problem for sesmi-algebraic colorings

János Pach

We considerm-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The casem= 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type resul ...

HEBREW UNIV MAGNES PRESS2020

Planar Point Sets Determine Many Pairwise Crossing Segments

János Pach, Gábor Tardos

We show that any set of n points in general position in the plane determines n(1-o(1)) pairwise crossing segments. The best previously known lower bound, Omega(root n), was proved more than 25 years ago by Aronov, Erdos, Goddard, Kreitman, Krugerman, Pach, ...

ASSOC COMPUTING MACHINERY2019

Thrackles: An improved upper bound

János Pach, Radoslav Fulek

A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...

ELSEVIER SCIENCE BV2019

Many touchings force many crossings

János Pach

Given n continuous open curves in the plane, we say that a pair is touching if they have finitely many interior points in common and at these points the first curve does not get from one side of the second curve to its other side. Otherwise, if the two cur ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

On the Size of K-Cross-Free Families

János Pach, Andrei Kupavskii, Istvan Tomon

Two subsets A,B of an n-element ground set X are said to be crossing, if none of the four sets AB, A\B, B\A and X(AB) are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family F of subsets of X does not contain k pairwise cr ...

SPRINGER HEIDELBERG2019

A lower bound on opaque sets

János Pach

It is proved that the total length of any set of countably many rectifiable curves whose union meets all straight lines that intersect the unit square U is at least 2.00002. This is the first improvement on the lower bound of 2 known since 1964. A similar ...

ELSEVIER SCIENCE BV2019

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

János Pach, Istvan Tomon

An ordered graph G(

COMENIUS UNIV2019