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

Table of contents
- Solution a

Solution

Write

d_{n} (H) = \frac{ex ( n , H )}{( 2 n )} .

Let

G

be an

H

n

ex (n, H)

edges, and choose a uniformly random set of

m < n

vertices. Its induced subgraph is still

H

-free, and each edge survives with probability

(2 m) / (2 n)

. Hence

ex (m, H) \geq ex (n, H) \frac{( 2 m )}{( 2 n )},

so

d_{m} (H) \geq d_{n} (H)

. Thus the normalized extremal number is nonincreasing and bounded below by zero, proving that

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

 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