Person

János Pach

Related publications (79)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Sphere-of-Influence Graphs in Normed Spaces

János Pach, Márton Naszódi

We showthat any k-th closed sphere-of-influence graph in a d-dimensional normed space has a vertex of degree less than 5dk, thus obtaining a common generalization of results of Furedi and Loeb (Proc AmMath Soc 121(4): 1063-1073, 1994 [1]) and Guibas et al. ...

SPRINGER2018

Note on k-planar crossing numbers

János Pach

The crossing number CR(G) of a graph G = (V, E) is the smallest number of edge crossings over all drawings of G in the plane. For any k >= 1, the k-planar crossing number of G, CRk(G), is defined as the minimum of CR(G(0)) + CR(G(1)) + ... + CR(G(k-i)) ove ...

Elsevier Science Bv2018

A Stability Theorem On Cube Tessellations

János Pach

It is shown that if a d-dimensional cube is decomposed into n cubes, the side lengths of which belong to the interval (1 - n1/d+1; 1], then n is a perfect d-th power and all cubes are of the same size. This result is essentially tight. ...

CARLETON UNIV, DEPT MATHEMATICS & STATISTICS2018

Ramsey-Turan numbers for semi-algebraic graphs

János Pach

A semi-algebraic graph G = (V, E) is a graph where the vertices are points in R-d, and the edge set E is defined by a semi-algebraic relation of constant complexity on V. In this note, we establish the following Ramsey-Turan theorem: for every integer p >= ...

ELECTRONIC JOURNAL OF COMBINATORICS2018

Distinct Distances on Algebraic Curves in the Plane

János Pach, Frank de Zeeuw

Let S be a set of n points in R-2 contained in an algebraic curve C of degree d. We prove that the number of distinct distances determined by S is at least c(d)n(4/3), unless C contains a line or a circle. We also prove the lower bound c(d)' min{m(2/3)n(2/ ...

Cambridge Univ Press2017

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

From Tarski's Plank Problem to Simultaneous Approximation

János Pach, Andrei Kupavskii

A slab (or plank) is the part of the d-dimensional Euclidean space that lies between two parallel hyperplanes. The distance between the these hyperplanes is called the width of the slab. It is conjectured that the members of any infinite family of slabs wi ...

Mathematical Assoc Amer2017

Decomposition of a Cube into Nearly Equal Smaller Cubes

János Pach

Let d be a fixed positive integer and let epsilon > 0. It is shown that for every sufficiently large n >= n(0)( d, e), the d-dimensional unit cube can be decomposed into exactly n smaller cubes such that the ratio of the side length of the largest cube to ...

Mathematical Assoc Amer2017

Separation with restricted families of sets

János Pach, Gábor Tardos, Márton Naszódi, Zsolt Langi

Given a finite n-element set X, a family of subsets F subset of 2(X) is said to separate X if any two elements of X are separated by at least one member of F. It is shown that if vertical bar F vertical bar > 2(n-1), then one can select vertical bar log n ...

Academic Press Inc Elsevier Science2016

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves

János Pach, Gábor Tardos

A long-standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed Jordan curves in the plane, so that any pair of them intersect and no three curves pass through the same point, is at least ...

Cambridge Univ Press2016