On the Ramsey-Turán numbers of graphs and hypergraphs

Details On the Ramsey-Turán numbers of graphs and hypergraphs On the Ramsey-Turán numbers of graphs and hypergraphs

2011-09-20

arxiv.org/abs/1109.4428v2

Mathematics

Combinatorics

20 pages, 2 figures

Scientific paper

Let t be an integer, f(n) a function, and H a graph. Define the t-Ramsey-Tur\'an number of H, RT_t(n, H, f(n)), to be the maximum number of edges in an n-vertex, H-free graph G where f(n) is larger than the maximum number of vertices in a $K_t$-free induced subgraph of G. Erd\H{o}s, Hajnal, Simonovits, S\'os, and Szemer\'edi posed several open questions about RT_t(n,K_s,o(n)), among them finding the minimum s such that $RT_t(n,K_{t+s},o(n)) = \Omega(n^2)$, where it is easy to see that $RT_t(n,K_{t+1},o(n)) = o(n^2)$. In this paper, we answer this question by proving that $RT_t(n,K_{t+2},o(n)) = \Omega(n^2)$; our constructions also imply several results on the Ramsey-Tur\'an numbers of hypergraphs.

Affiliated with

Also associated with

No associations

Rating

On the Ramsey-Turán numbers of graphs and hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Ramsey-Turán numbers of graphs and hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Ramsey-Turán numbers of graphs and hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256730