Simonovits, Miklos


Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family ${\cal F}$ of graphs and an integer $n$, the Turán number $ex(n,{\cal F})$ of ${\cal F}$ is the largest integer $m$ such that there exists a graph on $n$ vertices with $m$ edges which contains no member of ${\cal F}$ as a subgraph.

\begin{conjecture} For every finite family ${\cal F}$ of graphs there exists an $F\in {\cal F}$ such that $ex(n, F ) = O(ex(n, {\cal F}))$ .% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Syndicate content