On directed local chromatic number, shift graphs, and Borsuk-like graphs (2009)
We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented...
A constructive proof of the general Lovasz Local Lemma (2009)
Moser, Robin A., Tardos, Gábor
The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Bec91],...
János Pach, Gábor Tardos, Géza Tóth
Abstract. Twenty years ago, Ajtai et al. and, independently, Leighton discovered that the crossing number of any graph with v vertices and e> 4v edges is at least ce3 /v2, where c> 0 is an...
Partitioning multi-dimensional sets in a small number of “uniform ” parts (2008)
Noga Alon, Ilan Newman Alex, Er Shen, Gábor Tardos, Nikolai Vereshchagin
Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so that all the resulting bipartite...
The maximum number of edges in quasi-planar graphs, manuscript (2008)
A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [2] proved that these graphs have a linear number of edges. We give a simple proof for this...
Covering lattice points by subspaces (2007)
Imre Bárány, Gergely Harcos, János Pach, Gábor Tardos
Abstract. We find tight estimates for the minimum number of proper subspaces needed to cover all lattice points in an n-dimensional convex body C, symmetric about the origin 0. This enables us to...
Isosceles Triangles Determined By a Planar Point Set (2007)
It is proved that, for any " > 0 and n > n 0 ("), every set of n points in the plane has at most n 5e 1 + triples that induce isosceles triangles. (Here e denotes the base of the...
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Gábor Tardos
The research of P. Bro Miltersen was supported by the ESPRIT Long Term Research Programme of
Nathan Linial, Or Sheffet, Gábor Tardos
For a graph G and an integer t we let mcct(G) be the smallest m such that there exists a coloring of the vertices of G by t colors with no monochromatic connected subgraph having more than m...
Deterministic random walks on the integers (2007)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gábor
Jim Propp’s P-machine, also known as the ‘rotor router model’, is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen...
Deterministic Random Walks (2006)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gábor, Raman, Rajeev, Sedwgewick, Robert, ...
Jim Propp’s P-machine, also known as ‘rotor router model’ is a simple deterministic process that simulates random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it...
Colorful subgraphs in Kneser-like graphs (2005)
Combining Ky Fan's theorem with ideas of Greene and Matousek we prove a generalization of Dol'nikov's theorem. Using another variant of the Borsuk-Ulam theorem due to Bacon and Tucker, we also prove...
Local chromatic number and distinguishing the strength of topological obstructions (2005)
Simonyi, Gábor, Tardos, Gábor, Vrećica, Siniša T.
The local chromatic number of a graph G is the number of colors appearing in the most colorful closed neighborhood of a vertex minimized over all proper colorings of G. We show that two specific...
Intersection Reverse Sequences and Geometric Applications (2004)
Pinchasi and Radoicic [1] used the following observation to bound the number of edges in a topological graph with no self-intersecting cycles of length 4: if we make a list of the neighbors for every...
Intersection Reverse Sequences and Geometric Applications (2004)
Pinchasi and Radoicic [1] used the following observation to bound the number of edges in a topological graph with no self-intersecting cycles of length 4: if we make a list of the neighbors for every...
Intersection Reverse Sequences and Geometric Applications (2004)
Pinchasi and Radoicic [1] used the following observation to bound the number of edges in a topological graph with no self-intersecting cycles of length 4: if we make a list of the neighbors for every...
Excluded permutation matrices and the Stanley-Wilf conjecture (2004)
This paper examines the extremal problem of how many 1-entries an n × n 0–1 matrix can have that avoids a certain fixed submatrix P. For any permutation matrix P we prove a linear bound, settling...
Improving the Crossing Lemma by finding more crossings (2004)
János Pach, Gábor Tardos, Géza Tóth
in sparse graphs
Improving the Crossing Lemma by finding more crossings (2004)
János Pach, Gábor Tardos, Géza Tóth
in sparse graphs
Geometric Graphs with No Self-intersecting Path of Length Three (2003)
Pach, János, Pinchasi, Rom, Tardos, Gábor, Tóth, Géza
Let G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straight-line edges. It is shown that if G has no self-intersecting path of length 3, then its number of edges is O(n...
Geometric Graphs with No Self-intersecting Path of Length Three (2003)
Pach, János, Pinchasi, Rom, Tardos, Gábor, Tóth, Géza
Let G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straight-line edges. It is shown that if G has no self-intersecting path of length 3, then its number of edges is O(n...
Geometric Graphs with No Self-intersecting Path of Length Three (2003)
Pach, János, Pinchasi, Rom, Tardos, Gábor, Tóth, Géza
Let G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straight-line edges. It is shown that if G has no self-intersecting path of length 3, then its number of edges is O(n...
Distinct distances in three and higher dimensions (2003)
Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n 77/141−ε) = Ω(n 0.546), for any...
Distinct distances in three and higher dimensions (2003)
Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n 77/141−ε) = Ω(n 0.546), for any...
The following problem was raised by M. Watanabe. Let $P$ be a self-intersecting closed polygon with $n$ vertices in general position. How manys steps does it take to untangle $P$, i.e., to turn it...
The following problem was raised by M. Watanabe. Let $P$ be a self-intersecting closed polygon with $n$ vertices in general position. How manys steps does it take to untangle $P$, i.e., to turn it...
The following problem was raised by M. Watanabe. Let $P$ be a self-intersecting closed polygon with $n$ vertices in general position. How manys steps does it take to untangle $P$, i.e., to turn it...
Covering lattice points by subspaces (2001)
Bárány, Imre, Harcos, Gergely, Pach, János, Tardos, Gábor
We find tight estimates for the minimum number of proper subspaces needed to cover all lattice points in an n-dimensional convex body symmetric about the origin. We also find the order of magnitude...
An Improved Bound for k-Sets in Three Dimensions (2000)
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk 3=2 ). This improves substantially the previous best known upper bound of O(nk 5=3 ) (see [7] and [1]). 1...
Noga Alon, Martin Dietzfelbinger, Peter Bro, Miltersen Erez Petrank, Gábor Tardos
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S...
Lower Bounds for (MOD p - MOD m) Circuits (1998)
Modular gates are known to be immune for the random restriction techniques of Ajtai [Ajt83], Furst, Saxe, Sipser [FSS84], Yao [Yao85] and Hastad [Has86]. We demonstrate here a random clustering...
Arthur-Merlin Games in Boolean Decision Trees (1997)
Arthur-merlin Games, Gábor Tardos, Ran Raz, Nikolai Vereshagin
It is well known that probabilistic boolean decision trees cannot be much more powerful than deterministic ones (N. Nisan, SIAM Journal on Computing, 20(6):999--1007, 1991). Motivated by a question...
The Communication Complexity of the Universal Relation (1997)
Gábor Tardos, G Abor Tardos, Uri Zwick
Consider the following communication problem. Alice gets a word x 2 f0; 1g n and Bob gets a word y 2 f0; 1g n . Alice and Bob are told that x 6= y. Their goal is to find an index 1 i n such that x i...
Probabilistically Checkable Proofs with Zero Knowledge (1997)
Joe Kilian, Erez Petrank, Gábor Tardos
We construct PCPs with strong zero-knowledge properties. First, we construct polynomially bounded (in size) PCP's for NP which can be checked using poly-logarithmic queries, with polynomially...
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good H is as a class of hash functions, namely we consider hashing a set S...
On Point Covers of Multiple Intervals and Axis-Parallel Rectangles (1995)
Gyula Karolyi, Gábor Tardos, G Abor Tardosy
this paper we study hypergraphs related to multiple intervals and axis-parallel rectangles, respectively. Essential improvements of former established upper bounds are presented here. We explore the...
This document in subdirectoryRS/97/16/ Linear Hashing
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos, Noga Alon, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...