Publications by János Pach | EPFL Graph Search

Related publications (96)

Erdos-Szekeres-type theorems for monotone paths and convex bodies

For any sequence of positive integers j(1)< j(2)= 2 and q >= 2, what is the s ...

London Math Soc2012

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

Coloring K-k-free intersection graphs of geometric objects in the plane

János Pach

The intersection graph of a collection C of sets is the graph on the vertex set C, in which C-1 . C-2 is an element of C are joined by an edge if and only if C-1 boolean AND C-2 not equal empty set. Erdos conjectured that the chromatic number of triangle-f ...

2012

Approximating the rectilinear crossing number

János Pach

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019

Delaunay Graphs of Point Sets in the Plane With Respect to Axis-Parallel Rectangles

János Pach

Given a point set P in the plane, the Delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set P, whose two points p, q is an element of P are connected by an edge if and only if there is a rectangle parallel to the coor ...

Wiley-Blackwell2009

A Precise Threshold For Quasi-Ramsey Numbers

János Pach

We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...

SIAM Publications2015

A semi-algebraic version of Zarankiewicz's problem

János Pach

A bipartite graph G is semi-algebraic in R-d if its vertices are represented by point sets P,Q subset of R-d and its edges are defined as pairs of points (p,q) epsilon P x Q that satisfy a Boolean combination of a fixed number of polynomial equations and i ...

European Mathematical Soc2017

Unsplittable coverings in the plane

János Pach, Doemoetoer Palvoelgyi

A system of sets forms an m-fold covering of a set X if every point of X belongs to at least m of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density est ...

Academic Press Inc Elsevier Science2016

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

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

Ordered graphs and large bi-cliques in intersection graphs of curves

János Pach, Istvan Tomon

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

Remarks on Schur's conjecture

János Pach, Filip Moric

Let P be a set of n > d points in for d >= 2. It was conjectured by Zvi Schur that the maximum number of (d-1)-dimensional regular simplices of edge length diam(P), whose every vertex belongs to P, is n. We prove this statement under the condition that any ...

Elsevier Science Bv2015

A note on coloring line arrangements

János Pach, Rom Pinchasi

We show that the lines of every arrangement of n lines in the plane can be colored with O(root n/log n) colors such that no face of the arrangement is monochromatic. This improves a bound of Bose et al. by a circle minus(root/log n) factor. Any further imp ...

Electronic Journal Of Combinatorics2014

Tight lower bounds for the size of epsilon-nets

János Pach

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an epsilon-net of size O (1/epsilon log 1/epsilon). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range space ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

A separator theorem for string graphs and its applications

János Pach

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with in edges can be separated into two parts of roughly equal size by the removal of O(m(3/4)root log m) vertices. This result is then ...

Springer2009

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-Verlag2019

Cross-Intersecting Families of Vectors

János Pach

Given a sequence of positive integers , let denote the family of all sequences of positive integers such that for all . Two families of sequences (or vectors), , are said to be -cross-intersecting if no matter how we select and , there are at least distinc ...

Springer Japan Kk2015

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

The number of distinct distances from a vertex of a convex polygon

János Pach, Rom Pinchasi, Gabriel Nivasch

Erd\H{o}s conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). I ...

2013