Density version of the Ramsey problem and the directed Ramsey problem

Nagy, Zoltán Lóránt (2016) Density version of the Ramsey problem and the directed Ramsey problem. AUSTRALASIAN JOURNAL OF COMBINATORICS, 66 (2). pp. 240-255. ISSN 1034-4942

Preview

Text 1401.6823.pdf Available under License Creative Commons Attribution. Download (219kB) | Preview

Abstract

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.

Actions (login required)

Edit Item