Density version of the Ramsey problem and the directed Ramsey problem

We discuss a variant of the Ramsey and the directed Ramsey problem. First, consider a complete graph on n vertices and a two-coloring of the edges such that every edge is colored with at least one color and the number of bicolored edges |ERB| is given. The aim is to find the maximal size f of a monochromatic clique which is guaranteed by such a coloring. Analogously, in the second problem we consider a semicomplete digraph on n vertices such that the number of bi-oriented edges |Ebi| is given. The aim is to bound the size F of the maximal transitive subtournament that is guaranteed by such a digraph. Applying probabilistic and analytic tools and constructive methods, we show that if (Formula Presented), then f,F < Cp log(n) where Cp only depends on p, while if (Formula Presented). The latter case is strongly connected to Turán-type extremal graph theory. © 2016, University of Queensland. All rights reserved