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 ACMSIAM Symposium on Discrete Algorithms (SODA)(2011), 664674.

On conflictfree 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), 391412.

A sharp threshold for the
Hamilton cycle MakerBreaker game
(with D. Hefetz, M. Krivelevich, M. Stojaković),
Random Structures and Algorithms, 34
(2009) 112122.

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

RANDOM EDGE can be exponential on abstract cubes,
(with J. Matoušek)
Advances in Mathematics, 204(2006) 262277.
An extended abstract appeared in
Proc. 45nd Ann. IEEE Symp. on Foundations of Computer Science
(FOCS),
(2004), 92100.
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 cubelike 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 HoltKlee condition in every three dimensional
subcube.

Positional games on random graphs, (with M. Stojaković)
Random Structures & Algorithms,
26 (2005) 204223.
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) 225234.
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
kcliques. 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 squareroot
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) 547555.
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 producttype algorithm. It would be extremely interesting to
find any nontrivial randomized algorithm which works not
in a productlike fashion. Another challenge is to say something
nontrivial (= nonlinear currently) lower bound.
Last modified: Sun Jun 30 23:01:16 CEST 2013