✦ LIBER ✦

On Ramsey-Turán type problems in tournaments

✍ Scribed by A Bialostocki; N Sauer

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 467 KB
Volume: 59
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90168-8

No coin nor oath required. For personal study only.

✦ Synopsis

Let Tbe a tournament and let c :e(T)--> {1 ..... r} be an r-colouring of the edges of T. The associated reachability graph, denoted by R(T, c) is a directed graph whose vertices are the vertices of T, and a vertex v of R(T, c) dominates a vertex u of R(T, c) iff there is a monochromatic directed path in T from v to u.

In this paper we investigate properties of the reachability graph of edge coloured tournaments.

📜 SIMILAR VOLUMES

Turán-Ramsey problems

✍ Béla Bollobás 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 278 KB

For i = 1,2 .... ,k, let Gi be a graph with vertex set [n] = {1 .... ,n} containing no Fi as a subgraph. At most how many edges are in G1 t3 -• • U Gk? We shall answer this Turfin-Ramseytype question asymptotically, and pose a number of related problems. Given graphs F1 ..... Fk, write exk(n,F 1 ..

A Ramsey-type problem and the Turán numb

A Ramsey-type problem and the Turán numbers

✍ N. Alon; P. Erdős; D. S. Gunderson; M. Molloy 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract For each __n__ and __k__, we examine bounds on the largest number __m__ so that for any __k__‐coloring of the edges of __K~n~__ there exists a copy of __K~m~__ whose edges receive at most __k−__1 colors. We show that for $k \ge \sqrt{n}\;+\,\Omega(n^{1/3})$, the largest value of __m__ i

Explicit constructions of triple systems

Explicit constructions of triple systems for Ramsey–Turán problems

✍ Dhruv Mubayi; Vera T. Sós 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 68 KB

## Abstract We explicitly construct four infinite families of irreducible triple systems with Ramsey‐Turán density less than the Turán density. Two of our families generalize isolated examples of Sidorenko 14, and the first author and Rödl 12. Our constructions also yield two infinite families of i

A Turán type problem for interval graphs

✍ Harvey Abbott; Meir Katchalski 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 313 KB

We consider the following analogue of a problem of Turin for interval graphs: Let c = c(n, rn) be the largest integer such that any interval graph with n vertices and at least m edges contains a complete subgraph on c vertices. We determine the value of c(n, m) explicitly.

On three zero-sum Ramsey-type problems

✍ Noga Alon; Yair Caro 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 821 KB

## Abstract For a graph __G__ whose number of edges is divisible by __k__, let __R__(__G,Z__~k~) denote the minimum integer __r__ such that for every function __f__: __E__(__K__~r~) ↦ __Z__~k~ there is a copy __G__^1^ of __G__ in __K__~r~ so that Σe∈__E__(__G__^1^) __f(e)__ = 0 (in __Z__~k~). We pr

A Ramsey-type problem on right-angled tr

A Ramsey-type problem on right-angled triangles in space

✍ Miklós Bóna; Géza Tóth 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 342 KB

It is proved that for any 3-coloring of R 3 and for any right-angled triangle T, one can find a congruent copy of T, all of whose vertices are of the same color.