Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 17I / b

Table of contents
- Solution b

Solution

The Erdős-Stone theorem states that if the chromatic number of

H

is

r + 1 \geq 2

, then

ex (n, H) = (1 - \frac{1}{r} + o (1)) (2 n) .

If

H

is a bipartite graph with at least one edge, its chromatic number is two, so

r = 1

and therefore

n \to \infty lim \frac{ex ( n , H )}{( 2 n )} = 0.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version