Publications de Gábor Tardos | EPFL Graph Search

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

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, Gábor Tardos, Gabriel Nivasch

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, Gábor Tardos, Gabriel Nivasch

Springer2013

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

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

János Pach, Gábor Tardos

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

Gábor Tardos

Graph Chatbot

Chattez avec Graph Search

On the Turan number of ordered forests

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves

Separation with restricted families of sets

Cross-Intersecting Families of Vectors

The visible perimeter of an arrangement of disks

The Range of a Random Walk on a Comb

The Visible Perimeter of an Arrangement of Disks

Tight lower bounds for the size of epsilon-nets

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

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

On the Turan number of ordered forests

Cross-Intersecting Families of Vectors

The Range of a Random Walk on a Comb

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves

The visible perimeter of an arrangement of disks

The Visible Perimeter of an Arrangement of Disks

Separation with restricted families of sets

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

Tight lower bounds for the size of epsilon-nets

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