Publications by Gábor Tardos | EPFL Graph Search

Edge Ordered Turan Problems

Doemoetoer Palvoelgyi, Gábor Tardos, Abhishek Methuku

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...

COMENIUS UNIV2019

On the Turan number of ordered forests

Gábor Tardos, Istvan Tomon, Dániel József Korándi

An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex(

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

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

A Crossing Lemma for Jordan curves

János Pach, Gábor Tardos

2018

CONTROLLING LIPSCHITZ FUNCTIONS

János Pach, Andrei Kupavskii, Gábor Tardos

2018

Improved bounds on the Hadwiger-Debrunner numbers

Gábor Tardos, Shakhar Smorodinsky

2018

Tilings of the plane with unit area triangles of bounded diameter

János Pach, Andrei Kupavskii, Gábor Tardos

2018

Tilings with noncongruent triangles

János Pach, Gábor Tardos

2018

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

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

Cross-Intersecting Families of Vectors

János Pach, Gábor Tardos

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

The visible perimeter of an arrangement of disks

János Pach, Gabriel Nivasch, Gábor Tardos

Given a collection of n opaque unit disks in the plane, we want to find a stacking order for them that maximizes their visible perimeter, the total length of all pieces of their boundaries visible from above. We prove that if the centers of the disks form ...

Elsevier Science Bv2014

The Range of a Random Walk on a Comb

János Pach, Gábor Tardos

The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of ...

Electronic Journal Of Combinatorics2013

The Visible Perimeter of an Arrangement of Disks

János Pach, Gabriel Nivasch, Gábor Tardos

Given a collection of n opaque unit disks in the plane, we want to find a stacking order for them that maximizes their visible perimeter, the total length of all pieces of their boundaries visible from above. We prove that if the centers of the disks form ...

Springer2013

Tight Lower Bounds For The Size Of Epsilon-Nets

János Pach, Gábor Tardos

Amer Mathematical Soc2013

Piercing quasi-rectangles-On a problem of Danzer and Rogers

János Pach, Gábor Tardos

It is an old problem of Danzer and Rogers to decide whether it is possible to arrange 0(1/epsilon) points in the unit square so that every rectangle of area epsilon > 0 within the unit square contains at least one of them. We show that the answer to this q ...

Elsevier2012

Remarks on a Ramsey theory for trees

János Pach, Gábor Tardos

Springer-Verlag2012

Tight lower bounds for the size of epsilon-nets

János Pach, Gábor Tardos

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

Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers

János Pach, Gábor Tardos

It is an old problem of Danzer and Rogers to decide whether it is possible arrange O(1/epsilon) points in the unit square so that every rectangle of area epsilon contains at least one of them. We show that the answer to this question is in the negative if ...

Springer-Verlag Berlin2011

Coloring axis-parallel rectangles

János Pach, Gábor Tardos

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r = 2, th ...

2010