In this paper we solve two problems of Esperet, Kang and Thomasse as well as Li concerning (i) induced bipartite subgraphs in triangle-free graphs and (ii) van der Waerden numbers. Each time random greedy algorithms allow us to go beyond the Lovasz Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method.Comment: 14 pages; minor edits; to appear in European Journal of Combinatoric
The behaviour of the random greedy algorithm for constructing a maximal packing of edgedisjoint tria...
Probabilistic methods have become an integral part of theoretical computer science. Typically, the u...
We study randomly induced subgraphs G of a hypercube. Specifically, we investigate vertex covering o...
We describe recent advances in the study of random analogues of combinatorial theorems
We describe recent advances in the study of random analogues of combinatorial theorems
The random greedy algorithm for finding a maximal independent set in a graph has been studied extens...
Recently there has been much interest in studying random graph analogues of well known classical res...
The Andrásfai-Erdős-Sós Theorem [2] states that all triangle-free graphs on n vertices with minim...
Abstract. This work is motivated by the long-standing open problem of designing a polynomial-time al...
Abstract. This work is motivated by the long-standing open problem of designing a polynomial-time al...
Bukh and Conlon used random polynomial graphs to give effective lower bounds on $\mathrm{ex}(n,\math...
Let r be a fixed constant and let H be an r-uniform, D-regular hypergraph on N vertices. Assume furt...
AbstractWe consider random processes more general than those considered by Erdös and Rényi for gener...
<p>The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as ...
AbstractA simple combinatorial approach is given for handling certain conditioning problems that ari...
The behaviour of the random greedy algorithm for constructing a maximal packing of edgedisjoint tria...
Probabilistic methods have become an integral part of theoretical computer science. Typically, the u...
We study randomly induced subgraphs G of a hypercube. Specifically, we investigate vertex covering o...
We describe recent advances in the study of random analogues of combinatorial theorems
We describe recent advances in the study of random analogues of combinatorial theorems
The random greedy algorithm for finding a maximal independent set in a graph has been studied extens...
Recently there has been much interest in studying random graph analogues of well known classical res...
The Andrásfai-Erdős-Sós Theorem [2] states that all triangle-free graphs on n vertices with minim...
Abstract. This work is motivated by the long-standing open problem of designing a polynomial-time al...
Abstract. This work is motivated by the long-standing open problem of designing a polynomial-time al...
Bukh and Conlon used random polynomial graphs to give effective lower bounds on $\mathrm{ex}(n,\math...
Let r be a fixed constant and let H be an r-uniform, D-regular hypergraph on N vertices. Assume furt...
AbstractWe consider random processes more general than those considered by Erdös and Rényi for gener...
<p>The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as ...
AbstractA simple combinatorial approach is given for handling certain conditioning problems that ari...
The behaviour of the random greedy algorithm for constructing a maximal packing of edgedisjoint tria...
Probabilistic methods have become an integral part of theoretical computer science. Typically, the u...
We study randomly induced subgraphs G of a hypercube. Specifically, we investigate vertex covering o...
DOI
Add to ORKG