Random Structures and Algorithms

The tremendous success of the probabilistic method in combinatorics and the development of randomized algorithms in computer science naturally brought along the independent study of random graphs (or other finite structures). The papers below are a somewhat random selection from the topics above.

• The Local Lemma is tight for SAT (with H. Gebauer, G. Tardos), 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)(2011), 664-674.


• On conflict-free coloring of graphs (with R. Glebov, G. Tardos), submitted.


• On the Concentration of the Domination Number of the Random Graph (with R. Glebov, A. Liebenau), submitted.


• On covering expander graphs with Hamilton cycles (with R. Glebov, M. Krivelevich), Random Structures and Algorithms, to appear.


• Sharp threshold for the appearance of certain spanning trees in random graphs (with D. Hefetz, M. Krivelevich), Random Structures and Algorithms 41(2012), 391-412.


• A sharp threshold for the Hamilton cycle Maker-Breaker game (with D. Hefetz, M. Krivelevich, M. Stojaković), Random Structures and Algorithms, 34 (2009) 112-122.


• Hamilton cycles in highly connected and expanding graphs (with D. Hefetz, M. Krivelevich), Combinatorica ,29 (2009), 547-568.


• RANDOM EDGE can be exponential on abstract cubes, (with J. Matoušek) Advances in Mathematics, 204(2006) 262-277.
  An extended abstract appeared in Proc. 45nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), (2004), 92-100.
  We study the behavior of RANDOMEDGE (the random simplex algorithm which proceeds on an improving edge selected uniformly at random) on abstract cubes. An abstract cube is defined by a function on the vertices of the usual cube polytope, such that there is exactly one local minimum on any face of the cube. Obviously any linear objective function on a cube-like polytope has this property. It was conjectured that RANDOMEDGE is quadratic on any abstract cube. In the paper an abstract cube is constructed on which RANDOMEDGE performs a mildly exponential number of steps in expectation.
  We do not know the behaviour of RANDOMEDGE in realizable cubes or even in cubes satisfying the Holt-Klee condition in every three dimensional subcube.


• Positional games on random graphs, (with M. Stojaković) Random Structures & Algorithms, 26 (2005) 204--223.
  We initiate the study of positional games on random graphs. In the traditional setup of Maker/Breaker games two players alternately pick edges of the complete graph. Maker's goal is to create a subgraph which contains a "nice" graph theoretical structure, say a Hamiltonian cycle. This is usually not very hard to achieve, so the classical theory (initiated by Erdős and Selfridge and developed by Beck) was aiming to determine the smallest bias b such that Breaker playing b moves against one move of Maker can prevent Maker from achieving his goal. In this paper we investigate a different way to reduce Maker's power: the random thinning of the board. The threshold probability where a Breaker's win suddenly turns into a Maker's win is determined or estimated for several basic games. Sometimes there is a remarkable connection to the corresponding threshold bias of the biased games.


• Turán's theorem in sparse random graphs, (with V.H. Vu) Random Structures & Algorithms, 23 no.3. (2003) 225-234.
  A major open problem in the theory of random graphs is searching for the threshold probability from where the asymptotic version of Turán's theorem is a.s. true for the random graph G(n,p). Obviously for p=1, Turán's Theorem is true, while for p=cn^-2/(k+1) a relatively easy argument shows that even the asymptotic version fails for k-cliques. This is the conjectured threshold probability, which is known to be true for k=3,4,5. Here we give an inductive argument which gives the best known result for arbitrary k; roughly the square-root of the conjectured threshold. (A slightly weaker but comparable result using a completely different technique was found by Kohayakawa, Rödl and Schacht.)


• Unique sink orientations of cubes, (with E. Welzl), Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), (2001) 547-555.
  The main goal of the paper is to introduce the model of unique sink orientations of cubes as a general framework for several optimization problems in geometry, like linear programming or smallest enclosing ball. Among others, we also deal with randomized algorithms to find the sink of a unique sink orientation. Unfortunately every known algorithm is exponential. We improve on the base by introducing a product-type algorithm. It would be extremely interesting to find any non-trivial randomized algorithm which works not in a product-like fashion. Another challenge is to say something nontrivial (= nonlinear currently) lower bound.