1
$\begingroup$

Let $G$ be a finite, simple, loopless graph with $|V(G)|=n$. We define its edge density as $$ed(G) := \frac{|E(G)|}{n \choose 2}.$$

Moreover we set $$d_n := \text{max}\big\{ed(G): G \text{ is a triangle-free graph with } V(G) = \{1,\ldots, n\} \big\}.$$

Does $\lim_{n\to\infty}d_n$ exist and if yes, what is its value? If not, what is $\lim \text{sup}_{n\to\infty}d_n$? (I would expect this value to be around $2/3$ but I really don't have any idea.)

$\endgroup$
6
$\begingroup$

Turan's theorem says that this limit exists and is equal to $\frac{1}{2}$. The graphs that achieve this are the complete bipartite graphs. Moreover, the theorem gives the answer for the more general question of $K_{r+1}$-free graphs, where maximum edge density comes from complete $r$-partite graphs.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.