✦ LIBER ✦

A Ramsey-type problem and the Turán numbers

✍ Scribed by N. Alon; P. Erdős; D. S. Gunderson; M. Molloy

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 101 KB
Volume: 40
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10032

No coin nor oath required. For personal study only.

✦ Synopsis

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 is asymptotically equal to the Turá number $t(n,\lfloor {n\choose 2}/k\rfloor)$, while for any constant $\epsilon > 0,; {\rm if}; k \le (1-\epsilon) \sqrt{n}$ then the largest m is asymptotically larger than that Turá number. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 120–129, 2002

📜 SIMILAR VOLUMES

Mean Ramsey–Turán numbers

✍ Raphael Yuster 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract A ρ‐mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most ρ. For a graph __H__ and for ρ ≥ 1, the __mean Ramsey–Turán number RT__(__n, H,ρ − mean__) is the maximum number of edges a ρ‐__mean__ colored graph with _

Independence numbers of locally sparse g

Independence numbers of locally sparse graphs and a Ramsey type problem

✍ Noga Alon 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

Let G = (V, E ) be a graph on n vertices with average degree t 2 1 in which for every vertex u E V the induced subgraph on the set of all neighbors of u is r-colorable. We show that the independence number of G is at least log t , for some absolute positive constant c. This strengthens a well-known

On ramsey-tuŕan numbers for 3-graphs

✍ A. F. Sidorenko 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract For every __r__‐graph __G__ let π(__G__) be the minimal real number ϵ such that for every ϵ < 0 and __n__ ϵ __n__~0~(λ, __G__) every __R__‐graph __H__ with __n__ vertices and more than (π + ϵ)(nr) edges contains a copy of __G__. The real number λ(__G__) is defined in the same way, addin

On several variations of the turan and r

On several variations of the turan and ramsey numbers

✍ Yair Caro 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 424 KB

## Abstract We introduce several variations of the Turan and Ramsey numbers, including zero‐sum and bounded‐average Ramsey numbers. Some interesting relations between these concepts are presented. In particular, a generalization of the __k__‐local Ramsey numbers is established.

On a Ramsey-type problem

✍ F. R. K. Chung 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB

On A Problem of Erdős and Turán and Some

On A Problem of Erdős and Turán and Some Related Results

✍ N. Alon; M.N. Kolountzakis 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 315 KB

We employ the probabilistic method to prove a stronger version of a result of Helm, related to a conjecture of Erdos and Turan about additive bases of the positive integers. We show that for a class of random sequences of positive integers $A$, which satisfy $|A \cap[1, x]| \gg \sqrt{x}$ with pr