Кіріспе
Экстремалды графтар теориясы – экстремалды комбинаторика мен графтар теориясының тоғысқан жерінде орналасқан комбинаториканың бір саласы, ал ол өзі математиканың бір бөлігі. Көбінесе, экстремалды графтар теориясы графтың жаһандық қасиеттері жергілікті құрылымға қалай әсер ететінін зерттейді. Экстремалды графтар теориясының нәтижелері әртүрлі граф қасиеттері арасындағы сандық байланыстарды қарастырады, олар жаһандық (төбелер мен қабырғалар саны сияқты) және жергілікті (нақты подграфтардың болуы сияқты) болуы мүмкін. Экстремалды графтар теориясындағы мәселелер көбінесе оптимизация мәселелері ретінде қойылады: графтың белгілі бір параметрлері қаншалықты үлкен немесе кішкентай болуы мүмкін, егер графтың орындалуы керек белгілі бір шарттары болса? Мұндай оптимизация мәселесіне ең жақсы шешім беретін граф экстремалды граф деп аталады, ал экстремалды графтар экстремалды графтар теориясында зерттеудің маңызды объектілері болып табылады. Экстремалды графтар теориясы Рамзи теориясы, спектралды графтар теориясы, есептеу күрделілігі теориясы және қосымша комбинаторика сияқты салалармен тығыз байланысты және көбінесе ықтималдық әдісін қолданады.
Тарих
Мантель теоремасы (1907) және Туран теоремасы (1941) экстремалды графтар теориясын зерттеудегі маңызды кезеңдердің бірі болды. Атап айтқанда, Туран теоремасы кейіннен Эрдос-Стон теоремасы (1946) сияқты нәтижелерді табуға түрткі болды. Бұл нәтиже таң қалдырады, себебі ол хроматикалық санды белгілі бір графтан бос графтың максималды қабырғалар санымен байланыстырады. Эрдос-Стон теоремасының тағы бір дәлелі 1975 жылы ұсынылды, ол экстремалды графтар теориясы мәселелерін шешудегі маңызды құрал – Сземередидің тұрақтылық леммасын қолданды.
Графикті бояу
Графтың дұрыс (түйіндік) бояуы – екі іргелес түйінінің бірдей түсі болмауы үшін түйіндердің боялуы. Графты дұрыс бояу үшін қажетті түстердің ең аз саны хроматикалық сан деп аталады, белгілі бір графтардың хроматикалық санын анықтау экстремалды графтар теориясының негізгі мәселесі болып табылады, себебі осы саланың және байланысты салалардың көптеген мәселелерін графты бояу арқылы тұжырымдауға болады. Графтың хроматикалық санына екі қарапайым төменгі шек бар: клика саны – кликаның барлық түйіндері әртүрлі түстерге ие болуы керек – және , мұнда – тәуелсіздік саны, өйткені белгілі бір түспен боялған түйіндер жиыны тәуелсіз жиын құруы керек. Ашкөз бояу жоғарғы шекті береді, мұнда – ең жоғары дәреже. Егер граф тақ цикл немесе клика болмаса, Брукс теоремасы жоғарғы шекті дейін азайтуға болатынын айтады. Егер граф жазық граф болса, төрт түс теоремасы оның хроматикалық саны ең көп дегенде төрт екенін көрсетеді. Жалпы, берілген графтың белгіленген сандағы түстермен боялуы мүмкін-мүмкін еместігін анықтау NP-қиын мәселе екені белгілі. Түйіндік бояудан басқа, басқа да бояу түрлері зерттеледі, мысалы, қабырға бояуы. Графтың хроматикалық индексі – графтың дұрыс қабырға бояуындағы түстердің ең аз саны, ал Визинг теоремасы графтың хроматикалық индексі немесе болады деп мәлімдейді.
Тыйым салынған субграфтар
Тыйым салынған субграф мәселесі – экстремалды граф теориясының орталық мәселелерінің бірі. Граф берілгенде, тыйым салынған субграф мәселесі, -ге изоморфты субграфты қамтымайтын n төбелі графтың шеттерінің максималды санын анықтауға қатысты.
When is a complete graph, Turán's theorem gives an exact value for and characterizes all graphs attaining this maximum; such graphs are known as Turán graphs. For non bipartite graphs , the Erdős–Stone theorem gives an asymptotic value of in terms of the chromatic number of
The problem of determining the asymptotics of when is a bipartite graph is open; when is a complete bipartite graph, this is known as the Zarankiewicz problem.
- толық граф болған жағдайда, Туран теоремасы осы максимумқа жететін барлық графтардың нақты мәнін береді және оларды сипаттайды; мұндай графтар Туран графтары деп аталады. Екі бөлікке бөлінбеген графтар үшін, Эрдос-Стоун теоремасы -ның хроматикалық саны тұрғысынан асимптотикалық мәнін береді.
When is a complete graph, Turán's theorem gives an exact value for and characterizes all graphs attaining this maximum; such graphs are known as Turán graphs. For non bipartite graphs , the Erdős–Stone theorem gives an asymptotic value of in terms of the chromatic number of
The problem of determining the asymptotics of when is a bipartite graph is open; when is a complete bipartite graph, this is known as the Zarankiewicz problem.
- екі бөлікке бөлінген граф болған кезде, оның асимптотикасын анықтау мәселесі шешілмеген; ал - толық екі бөлікке бөлінген граф болған жағдайда, бұл мәселе Заранкевич проблемасы деп аталады.
When is a complete graph, Turán's theorem gives an exact value for and characterizes all graphs attaining this maximum; such graphs are known as Turán graphs. For non bipartite graphs , the Erdős–Stone theorem gives an asymptotic value of in terms of the chromatic number of
The problem of determining the asymptotics of when is a bipartite graph is open; when is a complete bipartite graph, this is known as the Zarankiewicz problem.
Гомоморфизм тығыздығы
Графтың гомоморфизм тығыздығы – бұл графтың төбелік жиынынан басқа графтың төбелік жиынына кездейсоқ таңдалған бейнелеудің граф гомоморфизмі болу ықтималдығын көрсетеді. Ол субграфтың тығыздығымен тығыз байланысты, ол графтың қанша рет басқа графтың ішкі графы ретінде кездесетінін сипаттайды. Тыйым салынған ішкі граф мәселесін нөлдік тығыздығы бар графтың жиек тығыздығын барынша арттыру ретінде қайта формулиреуге болады, бұл граф гомоморфизмі теңсіздіктері түрінде жалпылауға әкеледі, олар әртүрлі графтар үшін қатынастарды анықтайды. Гомоморфизм тығыздығын графондарға – тығыз графтардың лиміті ретінде туындайтын объектілерге – кеңейту арқылы, графтың гомоморфизм тығыздығы интеграл түрінде жазылуы мүмкін, ал гомоморфизм теңсіздіктерін алу үшін Коши-Шварц теңсіздігі және Гельдер теңсіздігі сияқты теңсіздіктерді қолдануға болады. Гомоморфизм тығыздықтарымен байланысты маңызды ашық мәселе – Сидоренконың болжамы, ол графтың жиек тығыздығы тұрғысынан екі бөлікті графтың гомоморфизм тығыздығы үшін төменгі шекті көрсетеді.
The forbidden subgraph problem can be restated as maximizing the edge density of a graph with density zero, and this naturally leads to generalization in the form of graph homomorphism inequalities, which are inequalities relating for various graphs By extending the homomorphism density to graphons, which are objects that arise as a limit of dense graphs, the graph homomorphism density can be written in the form of integrals, and inequalities such as the Cauchy Schwarz inequality and Hölder's inequality can be used to derive homomorphism inequalities. A major open problem relating homomorphism densities is Sidorenko's conjecture, which states a tight lower bound on the homomorphism density of a bipartite graph in a graph in terms of the edge density of .
Графиктің тұрақтылығы
Сземередидің тұрақтылық леммасы барлық графтардың келесі мағынада "тұрақты" екенін көрсетеді: кез келген графтың төбелік жиынтығы шектелген санда бөліктерге бөлінеді, сонда көптеген бөлік жұптары арасындағы екітарапты графтар кездейсоқ екітарапты графтар сияқты мінез-құлық көрсетеді. Бұл бөлу бастапқы графқа құрылымдық жуықтауды береді, ол бастапқы графтың қасиеттері туралы ақпаратты ашады. Тұрақтылық леммасы экстремалды граф теориясының маңызды нәтижесі болып табылады және аддитивті комбинаторика мен есептеу күрделілігі теориясының туыс салаларында көптеген қолданысқа ие. (Сземереди) тұрақтылығынан өзге, графтың тұрақтылығының ұқсас түсініктері, мысалы, күшті тұрақтылық және Фриз-Каннанның әлсіз тұрақтылығы да зерттелді, сондай-ақ гиперграфтарға тұрақтылықты кеңейту де қарастырылды. Графтардың тұрақтылығын қолдану жиі санау леммалары мен жою леммаларын пайдаланады. Ең қарапайым түрінде графты санау леммасы тұрақты бөлудегі бөлік жұптары арасындағы тұрақтылықты субграфтардың санын жуықтау үшін қолданады, ал графты жою леммасы берілген субграфтың азын-азын көшірмелері бар граф берілген жағдайда, субграфтың барлық көшірмелерін жою үшін азғантай жиектерді жоюға болады.