Ramsey-Turan number

Question

The following parameter (motivated by Ramsey's and Turan's theorem) in extremal graph theory is defined as:

$RT(n, k, \ell) = \max\{|E(G)|:G=(V,E)$ with $|V| = n, \alpha(G) < k$ and $\omega(G) < \ell \}$

How can I write $ex(n, K_t)$ as $RT(.,.,.)$? For which parameter is $RT(.,.,.)$ according to Ramsey's theorem trivial?

Answer 1

This problem is mostly just knowing what the definitions are. The definitions appear to be:

• $\mathrm{ex}(n,K_t)$ is the maximum number of edges of a graph on $n$ vertices not containing $K_t$ as a subgraph;

• $\mathrm{RT}(n, k, \ell)$ is the maximum number of edges of a graph on $n$ vertices with independence number less than $k$ and clique number less than $\ell$;

• the independence number $\alpha(G)$ is the cardinality of the largest independent vertex set of $G$; and

• the clique number $\omega(G)$ is the number of vertices in a maximum clique of $G$.

The number $\mathrm{ex}(n,K_t)$ is related to $K_t$-free graphs, or in other words, graphs with clique number $<t$; it places no restrictions on the independence number. So the relationship is basically as you say: $$ \mathrm{ex}(n,K_t) = \mathrm{RT}(n, n+1, t) $$ but we need to set the parameter $k$ to be greater than $n$, since the definition of $\mathrm{RT}$ restricts to graphs $G$ with $\alpha(G) < k$.