Andrásfai and Vega graphs in Ramsey–Turán theory

Abstract: Given positive integers

n g e s

, we let

m a t h r m e x (n, s)

denote the maximum number of edges in a triangle-free graph

G

on

n

vertices with

a l p h a (G) l e s

. In the early sixties Andr'{a}sfai conjectured that for

n / 3 < s < n / 2

the function

m a t h r m e x (n, s)

is piecewise quadratic with critical values at

s / n = k / (3 k - 1)

. We confirm that this is indeed the case whenever

s / n

is slightly larger than a critical value, thus determining

m a t h r m e x (n, s)

for all

n

and

s

such that

s / n i n [k / (3 k - 1), k / (3 k - 1) + g a m m a_{k}]

, where

g a m m a_{k} = T h e t a (k^{- 6})

.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Andrásfai and Vega graphs in Ramsey–Turán theory