Arrow Research search

Author name cluster

Vojtech Rödl

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
1 author row

Possible papers

13

STOC Conference 2007 Conference Paper

Property testing in hypergraphs and the removal lemma

  • Vojtech Rödl
  • Mathias Schacht

Property testers are efficient, randomized algorithms which recognize if an input graph (or other combinatorial structure) satisfies a given property or if it is "far" from exhibiting it.Generalizing several earlier results, Alon and Shapira showed thathereditary graph properties are testable (with one-sided error). In this paper we prove the analogous result for hypergraphs.This result is an immediate consequence of a (hyper)graph theoretic statement, which is an extension of the so-called removal lemma. The proof of this generalization relies on the regularity method for hypergraphs.

Details

FOCS Conference 2005 Conference Paper

An Algorithmic Version of the Hypergraph Regularity Method

  • Penny Haxell
  • Brendan Nagle
  • Vojtech Rödl

Extending the Szemeredi Regularity Lemma for graphs, P. Frank and Rodl [2002] stablished a 3-graph Regularity Lemma guaranteeing that all large triple systems admit partitions of their edge sets into constantly many classes where most classes consist of regularly distributed edges. Many applications of this lemma require a companion Counting Lemma [Nagle and Rodl, 2003] allowing one to estimate the number of copies of K/sub k//sup 3/ in a "dense and regular" environment created by the 3-graph Regularity Lemma. Combined applications of these lemmas are known as the 3-graph Regularity Method. In this paper, we provide an algorithmic version of the 3-graph Regularity Lemma which, as we show, is compatible with a Counting Lemma. We also discuss some applications. For general k-uniform hypergraphs, Regularity and Counting Lemmas were recently established by Gowers [2005] and by Nagle et al. , [2005]. We believe the arguments here provide a basis toward a general algorithmic hypergraph regularity method.

Details

MFCS Conference 2005 Invited Paper

The Generalization of Dirac's Theorem for Hypergraphs

  • Endre Szemerédi
  • Andrzej Rucinski 0001
  • Vojtech Rödl

Abstract A substantial amount of research in graph theory continues to concentrate on the existence of hamiltonian cycles and perfect matchings. A classic theorem of Dirac states that a sufficient condition for an n -vertex graph to be hamiltonian, and thus, for n even, to have a perfect matching, is that the minimum degree is at least n /2. Moreover, there are obvious counterexamples showing that this is best possible.

Details

FOCS Conference 2000 Conference Paper

Universality and Tolerance

  • Noga Alon
  • Michael R. Capalbo
  • Yoshiharu Kohayakawa
  • Vojtech Rödl
  • Andrzej Rucinski 0001
  • Endre Szemerédi

For any positive integers r and n, let H(r, n) denote the family of graphs on n vertices with maximum degree r, and let H(r, n, n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r, n)-universal graph must have /spl Omega/(n/sup 2-2/r/) edges. On the other hand, for any n/spl ges/n/sub 0/(r), we explicitly construct H(r, n)-universal graphs G and /spl Lambda/ on n and 2n vertices, and with O(n/sup 2-/spl Omega//(1/r log r)) and O(n/sup 2-1/r/ log/sup 1/r/ n) edges, respectively, such that we can efficiently find a copy of any H /spl epsiv/ H (r, n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G=G(n, n, p), with p=cn/sup -1/2r/ log/sup 1/2r/ n is fault-tolerant; for a large enough constant c, even after deleting any /spl alpha/-fraction of the edges of G, the resulting graph is still H(r, /spl alpha/(/spl alpha/)n, /spl alpha/(/spl alpha/)n)-universal for some /spl alpha/: [0, 1)/spl rarr/(0, 1].

Details

FOCS Conference 1992 Conference Paper

The Algorithmic Aspects of the Regularity Lemma (Extended Abstract)

  • Noga Alon
  • Richard A. Duke
  • Hanno Lefmann
  • Vojtech Rödl
  • Raphael Yuster

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2. 376/) is the time needed to multiply two n by n matrices with 0, 1-entries over the integers. The algorithm can be parallelized and implemented in NC/sup 1/. >

Details

FOCS Conference 1985 Conference Paper

Geometrical Realization of Set Systems and Probabilistic Communication Complexity

  • Noga Alon
  • Peter Frankl
  • Vojtech Rödl

Let d = d(n) be the minimum d such that for every sequence of n subsets F1, F2, .. ., Fn of {1, 2, .. ., n} there exist n points P1, P2, .. ., Pn and n hyperplanes H1, H2. .. ., Hn in Rd such that Pj lies in the positive side of Hi iff j ∈ Fi. Then n/32 ≤ d(n) ≤ (1/2 + 0(1)) · n. This implies that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon. The proof of (1) combines some known geometric facts with certain probabilistic arguments and a theorem of Milnor from real algebraic geometry.

Details