Кіріспе
Экстремалды граф теориясы кликасыз граф қабырғаларына шектеулер қояды. Граф теориясында Туран теоремасы, белгілі бір өлшемдегі толық қосалқы графтары жоқ бағытталмаған графқа қамтуға болатын қабырғалар санын шектейді. Бұл экстремалды граф теориясының орталық нәтижелерінің бірі болып табылады, ол берілген қасиеттері бар ең үлкен немесе ең кіші графтарды зерттейтін сала және белгілі бір қосалқы графтары жоқ графтың ең көп қабырғаларының саны туралы тыйым салынған қосалқы граф мәселесінің ерекше жағдайы. Кез келген *n* төбелі графтың, *k* төбелі кликасы жоқ мысалы, *n* төбелер жиынын тең немесе шамамен тең өлшемді *k* бөлікке бөлу арқылы және егер екі төбе әртүрлі бөліктерге жатса, оларды қабырғамен қосу арқылы құруға болады. Нәтижесінде алынған граф – Туран графигі. Туран теоремасы бойынша, Туран графигі *Kr+1*-сыз барлық *n* төбелі графтардың арасында ең көп қабырғаға ие. Туран теоремасы және оның шектік жағдайын беретін Туран графиктерін алғаш рет венгр математигі Пал Туран 1941 жылы сипаттаған және зерттеген. Үшбұрышсыз графтар үшін теореманың ерекше жағдайы Мантель теоремасы деп аталады; оны 1907 жылы голланд математигі Виллем Мантель тұжырымдаған.
In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties, and is a special case of the forbidden subgraph problem on the maximum number of edges in a graph that does not have a given subgraph. An example of an vertex graph that does not contain any vertex clique may be formed by partitioning the set of vertices into parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the Turán graph Turán's theorem states that the Turán graph has the largest number of edges among all Kr+1 free n vertex graphs. Turán's theorem, and the Turán graphs giving its extreme case, were first described and studied by Hungarian mathematician Pál Turán in 1941. The special case of the theorem for triangle free graphs is known as Mantel's theorem; it was stated in 1907 by Willem Mantel, a Dutch mathematician.
Айтылым
Тұран теоремасы бойынша, төбелері бар және кіші граф ретінде қамтымайтын кез келген графтың жиектерінің саны Тұран графигіндегіден көп болмайды. Белгілі бір мәні үшін, бұл граф кішкентай о нотациясын қолдана отырып, жиекке ие. Интуитивті түрде, бұл дегеніміз, артқан сайын, жиектердің үлесіне жақындай береді. Келесі дәлелдердің көпшілігі тек жоғарғы шекті ғана көрсетеді.
Дәлелдендіру
Тұран теоремасының бес түрлі дәлелін келтіріңіз. Көптеген дәлелдемелер графикті толық көпбөлікті график түріне келтіруді және қабырғалар саны бөліктердің мөлшері мүмкіндігінше тең болғанда максималды болатынын көрсетуді қамтиды.
Ең жоғарғы деңгейі
Бұл дәлел Пол Эрдосқа тиесілі. Ең үлкен дәрежесі бар төбесін таңдаңыз. -қа жанас емес төбелер жиыны мен -қа жанас төбелер жиынын қарастырыңыз.
Енді, жиын ішіндегі барлық қабырғаларды жойып, және жиындары арасындағы барлық қабырғаларды қосыңыз. Бұл, максималдылық болжамымыз бойынша, қабырғалар санын арттырады және графты -сыз қалдырады. Енді -сыз болғандықтан, дәл осы аргументті қайтадан -қа қолдануға болады.
Осы аргументті қайталау нәтижесінде, бір-бірімен байланысы жоқ жиынтықтардан және әртүрлі байланыссыз жиынтықтардың әрқайсысынан шығатын қабырғалардан тұратын Туран графигі сияқты формадағы граф пайда болады. Қарапайым есептеулер көрсеткендей, бұл графтың қабырғаларының саны барлық байланыссыз жиынтықтардың өлшемдері мүмкіндігінше тең болғанда максималды болады.
Now, delete all edges within and draw all edges between and This increases the number of edges by our maximality assumption and keeps the graph free. Now, is free, so the same argument can be repeated on
Repeating this argument eventually produces a graph in the same form as a Turán graph, which is a collection of independent sets, with edges between each two vertices from different independent sets. A simple calculation shows that the number of edges of this graph is maximized when all independent set sizes are as close to equal as possible.
Толық көп тарапты оңтайландыру
Бұл дәлелдеме, Зиков симметриясын дәлелдеу сияқты, графты толық көпбөлікті графқа келтіруді және тәуелсіз жиынтықтардың мөлшері мүмкіндігінше тең болғанда жиектер санының максималды болатынын көрсетуді қамтиды. Бұл қадамды былай жасауға болады:
Көпбөлікті графтың тәуелсіз жиынтықтары болсын. Егер екі төбе бір тәуелсіз жиынтыққа жатпаса, олардың арасында жиек болады, сондықтан жиектер саны
тең болады, мұнда сол жақ тікелей санау арқылы, ал оң жақ толықтыру санау арқылы алынады. шегін көрсету үшін, оң жақтағы мүшеге Коши-Шварц теңсіздігін қолдану жеткілікті, себебі. Туран графигінің оңтайлы екенін дәлелдеу үшін, екі жиынтықтың мөлшері екіден артық айырмашылыққа ие емес екенін көрсетуге болады. Атап айтқанда, егер бізде кейбір үшін болса, бір төбені жиынтығынан жиынтығына жылжыту (және жиектерді тиісінше түзету) қосындының мәнін арттырады. Мұны жоғарыдағы өрнектің екі жағындағы жиектер санының өзгеруін қарастыру арқылы немесе жылжытылған төбенің дәрежесінің артатынын байқау арқылы көруге болады.
To prove the Turán Graph is optimal, one can argue that no two differ by more than one in size. In particular, supposing that we have for some , moving one vertex from to (and adjusting edges accordingly) would increase the value of the sum. This can be seen by examining the changes to either side of the above expression for the number of edges, or by noting that the degree of the moved vertex increases.
Лагранждық
Бұл дәлелдеу олардың еңбегімен байланысты. Олар нүктелерімен белгіленген бос графты қарастырудан бастайды және сомасы бірге тең болатын барлық теріс емес мәндер бойынша функцияны максимизациялауды қарастырады. Бұл функция графтың және оның қабырғаларының Лагранжианы деп аталады. Дәлелдеудің негізгі идеясы мынада: егер екеуі де нөлден өзгеше болса, ал граф бойынша олар іргелес болмаса, онда функция аргументтердің біріне байланысты сызықтық. Сондықтан, функцияның мәнін кемітпестен, бірін немесе бірін ауыстыруға болады. Осылайша, функция максималды мәнге ие болатын нүктеде нөлден артық айнымалылардың саны ең көп дегенде болады. Енді, Коши-Шварц теңсіздігі максималды мәннің ең көп дегенде екенін көрсетеді. Барлық мәндері үшін қосу максималды мәннің ең кем дегенде екенін көрсетеді, бұл қажетті шектеме береді.
Мантель теоремасы
Тұран теоремасының ерекше жағдайы – Мантель теоремасы: үшбұрышсыз графтың ең көп шеттерінің саны . Басқаша айтқанда, үшбұрышсыз граф алу үшін графтың дерлік жартысына жуық шеттерін жою қажет. Мантель теоремасының күшейтілген түрі, кем дегенде шеттері бар кез келген Гамильтондық граф толық екі бөлікті граф немесе панциклдік болуы керек деп мәлімдейді: ол тек үшбұрыш ғана емес, графтың төбелерінің санына дейінгі барлық мүмкін ұзындықтағы циклдарды да қамтуы керек. Мантель теоремасының тағы бір күшейтілген түрі, кез келген нүктелі графтың шеттерін ең көп шет немесе үшбұрыштардан тұратын кликалармен жабуға болады дейді. Осыдан келіп, графтың қиылысу саны (барлық шеттерін жабу үшін қажетті кликалардың ең аз саны) ең көп дегенде болады.
Басқа тыйым салынған субграфтар
Тұран теоремасы еркін графтың ең көп жиектерінің санын көрсетеді. Эрдос-Стон теоремасы басқа барлық графтардағы қатеге дейін жиектер санын анықтайды: (Эрдос-Стон) Хроматикалық саны болатын графты қарастырайық. Субграф ретінде пайда болмайтын графтың ең көп жиектері саны, тек бір ғана тұрақтыға байланысты. -ның хроматикалық саны болғандықтан, Тұран теоремасы - бұл жағдай, егер болатын болса. Кейбір субграфтың көшірмесіз графқа қанша жиек қосуға болатыны туралы жалпы сұрақ – бұл тыйым салынған субграф мәселесі.
The general question of how many edges can be included in a graph without a copy of some is the forbidden subgraph problem.
Басқа мөлшерлерді барынша арттыру
Тұран теоремасының тағы бір табиғи кеңейтімі келесі сұрақ: егер графтың s болмаса, онда оның қанша данасы болуы мүмкін? Тұран теоремасы – бұл Цыков теоремасы осы сұраққа жауап беретін жағдай: (Цыков теоремасы) s жоқ және s-тің мүмкін болатын ең үлкен саны бар төбелері бар граф – бұл Тұран графигі. Бұл тұңғыш рет Цыков (1949) Цыков симметриясын қолдана отырып көрсетті. Тұран графигі шамамен өлшемдегі бөліктерден тұратындықтан, s саны шамамен болады. 2016 жылы Алон мен Шихельманның мақаласында мынадай жалпылама берілген, ол Эрдёш-Стоунның Тұран теоремасының жалпыламасына ұқсас: (Алон, Шихельман, 2016) Хроматикалық саны бар граф болсын. s көшірмесі жоқ графтың s-тің ең үлкен саны – . Эрдёш-Стоун сияқты, Тұран графигі қажетті көшірмелер санын қамтиды.
A paper by Alon and Shikhelman in 2016 gives the following generalization, which is similar to the Erdos Stone generalization of Turán's theorem:(Alon Shikhelman, 2016) Let be a graph with chromatic number The largest possible number of s in a graph with no copy of isAs in Erdős–Stone, the Turán graph attains the desired number of copies of .
Edge-Clique аймағы
Тұран теоремасы бойынша, егер графтың жиектік гомоморфизм тығыздығы қатаң түрде үлкен болса, онда s саны нөлден өзгеше болады. Одан да жалпырақ сұрақ туындайды: егер графтың жиектік тығыздығы берілсе, s тығыздығы туралы қандай тұжырым жасауға болады? Бұл сұраққа жауап берудегі қиындық – берілген тығыздық үшін, ешбір графқа қол жеткізе алмайтын, бірақ кейбір шексіз графтар тізбегі жақындасатын шек болуы мүмкін. Осы мәселені шешу үшін салмақты графтар немесе графтар қарастырылады. Атап айтқанда, графтар кез келген шексіз графтар тізбегінің лимитін қамтиды. Берілген жиек тығыздығы үшін ең үлкен s тығыздығын құру үшін, шексізге жақындаған төбелер санын алыңыз. Төбелердің арасынан s төбесін таңдап, егер екі төбе таңдалған жиынға кірсе, оларды қосыңыз. Бұл s тығыздығын береді. Ең кіші s тығыздығын құру үшін, шексізге жақындаған төбелер санын алыңыз. Барлық бөліктерінің мөлшері бірдей, бірақ бірегей ең кішкентай бөлігінен басқа, бөліктік графты алыңыз, ал бөліктердің мөлшері жалпы жиек тығыздығына тең болатындай етіп таңдаңыз. , бұл бөліктік графты береді, сондықтан s жоқ. Төменгі шекараны үшбұрыштар үшін Разборов (2008) дәлелдеген, ал кейін Рейхер (2016) оны барлық кликтерге жалпылады. Жоғарғы шек Крускал-Катона теоремасының салдары болып табылады.
The lower bound was proven by Razborov (2008) for the case of triangles, and was later generalized to all cliques by Reiher (2016). The upper bound is a consequence of the Kruskal–Katona theorem .