2014/01/27 by Zoltán Lóránt Nagy, Nagy, Zoltán Lóránt · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1401.6823
17 pages. Further lower bound added in case $|E_{RB}|=|E_{bi}| = p{n\choose 2}$
arxiv created 2016/01/21 · arxiv updated 2016/01/22
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 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 |ERB|=|Ebi| = pn\choose 2, (p∈ [0,1)), then f, F < Cplog(n) where Cp only depend on p, while if m=n \choose 2 - |ERB| <n3/2 then f= Θ((n2)/(m+n)). The latter case is strongly connected to Turán-type extremal graph theory.