Эрдис-тас теоремасы - Erdős–Stone theorem - Wikipedia

Жылы экстремалды графтар теориясы, Эрдис-тас теоремасы болып табылады асимптотикалық нәтижені жалпылау Туран теоремасы ішіндегі жиектер санын шектеу үшін H-толық емес граф үшін ақысыз график H. Оған байланысты Paul Erdős және Артур Стоун, оны 1946 жылы кім дәлелдеді,^[1] және ол «экстремалды графтар теориясының негізгі теоремасы» ретінде сипатталды.^[2]

Туран графиктерінің экстремалды функциялары

Экстремальды функция (n; H) рет графигіндегі жиектердің максималды саны ретінде анықталған n құрамында изоморфты субографиясы жоқ H. Туран теоремасы бұрынғы (n; Қ_р) = т_р − 1(n), тәртібі Туран графигі, және Туран графигі бірегей экстремалды график. Erdős-Stone теоремасы мұны құрамында жоқ графиктерге дейін кеңейтеді Қ_р(т), толық р-партиттік график т әр сыныптағы шыңдар (барабар Туран графигі Т(rt,р)):

${ displaystyle { mbox {ex}} (n; K_ {r} (t)) = сол жақ ({ frac {r-2} {r-1}} + o (1) оң) {n 2} таңдаңыз.}$

Екі жақты емес графтардың ерікті функциялары

Егер H болып табылатын ерікті граф хроматикалық сан болып табылады р > 2, содан кейін H ішінде орналасқан Қ_р(т) қашан болса да т ішіндегі ең үлкен түс класы сияқты үлкен р-бояу H, бірақ ол Туран графикасында жоқ Т(n,р - 1) (өйткені осы Туран графигінің әрбір субографиясы боялған болуы мүмкін р Демек, экстремалды функция H ішіндегі жиектердің санынан кем емес Т(n,р - 1), және ең көп дегенде экстремалды функцияға тең Қ_р(т); Бұл,

${ displaystyle { mbox {ex}} (n; H) = left ({ frac {r-2} {r-1}} + o (1) right) {n 2} таңдаңыз.}$

Үшін екі жақты графиктер Hдегенмен, теорема экстремалды функцияға берік байланыс бермейді. Қашан екені белгілі H екі жақты, бұрынғы (n; H) = o(n²), ал жалпы екі жақты графиктер үшін көп нәрсе белгілі емес. Қараңыз Заранкевич проблемасы екі жақты графиктердің экстремалды функциялары туралы көбірек білуге ​​болады.

Сандық нәтижелер

Қатынасын дәлірек сипаттайтын теореманың бірнеше нұсқасы дәлелденді n, р, т және o(1) мерзім. Белгіге анықтама беріңіз^[3] с_{р, ε}(n) (0 үшін <ε <1 / (2 (р - 1))) ең үлкен болу т тәртіпті әрбір график n және мөлшері

${ displaystyle left ({ frac {r-2} {2 (r-1)}} + varepsilon right) n ^ {2}}$

құрамында а Қ_р(т).

Эрдоус пен Стоун мұны дәлелдеді

${ displaystyle s_ {r, varepsilon} (n) geq left ( underbrace { log cdots log} _ {r-1} n right) ^ {1/2}}$

үшін n жеткілікті үлкен. Дұрыс тәртібі с_{р, ε}(n) жөнінде n Боллобас пен Эрдосты тапты:^[4] кез келген үшін р және ε тұрақтылары бар c₁(р, ε) және c₂(р, ε) осылай c₁(р, ε) журналn < с_{р, ε}(n) < c₂(р, ε) журналn. Чвалат және Семереди^[5] тәуелділік сипатын анықтады р және ε, тұрақтыға дейін:

${ displaystyle { frac {1} {500 log (1 / varepsilon)}} log n$ жеткілікті үлкен n.

Ескертулер