Эрдёш-Фабер-Ловас болжамы: Түстің қатынасы және гиперграфиктер туралы

Кіріспе

Графтар теориясында Эрдёш-Фабер-Ловас болжамы – графтарды түстің қалыпты жағдайында бояу туралы мәселе. Бұл мәселе 1972 жылы оны тұжырымдаған Пол Эрдёш, Ванс Фабер және Ласло Ловас есімін алған. Ол былай тұжырымдайды: Егер k толық графтың әрқайсысының дәл k төбесі болса және әрбір екі толық графтың бір-ғана ортақ төбесі болса, онда графтардың бірігімі k түспен дұрыс боялуы мүмкін. K-ның жеткілікті үлкен мәндері үшін бұл болжамды Донг Йеп Канг, Том Келли, Даниэла Кюн, Абхишек Метуку және Дерик Остхус дәлелдеді.

Теңдес формулалар

проблеманы комитеттердегі орын бөлу туралы мысалмен түсіндірді: университет кафедрасында әрқайсысы k оқытушыдан тұратын k комитет болсын, және барлық комитеттер k орындықтары бар бір бөлмеде жиналады. Сонымен қатар, кез келген екі комитеттің құрамында ең көп дегенде бір адам бар деп есептейік. Мүшелерді орындықтарға тағайындауға бола ма, осылайша әр мүше өзі қатысатын барлық комитеттерде бір орынға отырады? Бұл модельде оқытушылар графтың төбелеріне, комитеттер толық графтарға, ал орындықтар төбелердің түстеріне сәйкес келеді. Сызықтық гиперграф (немесе жартылай сызықтық кеңістік) – әрбір екі гиперқабырғаның ортақ төбесінің саны ең көп дегенде біреуге тең болатын гиперграф. Егер гиперграфтың барлық гиперқабырғалары бірдей санында төбелері болса, онда ол біртекті гиперграф деп аталады. Эрдос-Фабер-Ловас болжамындағы n өлшемді n кликаларды n біртекті сызықтық гиперграфтың гиперқабырғалары ретінде қарастыруға болады, олардың төбелері негізгі графтың төбелерімен сәйкес келеді. Осы тұрғыдан алғанда, Эрдос-Фабер-Ловас болжамы мынадай: кез келген n біртекті сызықтық гиперграфты n гиперқабырғасымен берілген жағдайда, төбелерді n түспен бояуға болады, осылайша әр гиперқабырғада әр түстің бір төбесі болады. Жасырап гиперграф – кез келген екі төбеге ең көп дегенде бір гиперқабырға жалғанатын және өлшемі ең көп дегенде біреуге тең гиперқабырғалары жоқ гиперграф. Эрдос-Фабер-Ловас болжамының граф түсіне беруінде, бір кликаға жататын төбелерді алып тастау қауіпсіз, өйткені оларды түсіру қиындық тудырмайды; мұндай амалдан кейін, әр клика үшін төбесі бар және әр граф төбесі үшін гиперқабырғасы бар гиперграф жасырап гиперграф құрайды. Гиперграфтағы төбелерді түсірудің екілігі – қабырғаларды түсіру. Осылайша, Эрдос-Фабер-Ловас болжамы n төбесі бар кез келген жасырап гиперграфтың хроматикалық индексі (қабырғаларды түсіру саны) n-ден аспайды деген мәлімдемеге тең. Эрдос-Фабер-Ловас болжамының графигін жиындардың қиылысу графигі ретінде бейнелеуге болады: графтың әр төбесіне сол төбесін қамтитын кликалар жиыны сәйкес келеді, және егер олардың сәйкес жиындарының қиылысы бос емес болса, онда кез келген екі төбе жиекпен жалғанады. Графиктің осы сипаттамасын пайдаланып, болжамды былай қайта формулиреуге болады: егер жиындардың бір жиынында n элемент болса және кез келген екі жиынның қиылысы ең көп дегенде бір элементтен тұрса, онда жиындардың қиылысу графигі n түспен боялуы мүмкін. Графтың қиылысу саны – қиылысу графигі G болатын жиындар жиынындағы ең аз элементтер саны, немесе эквивалентті түрде, сызықтық графигі G болатын гиперграфтағы ең аз төбелер саны. Графтың сызықтық қиылысу санын сызықтық гиперграфтағы ең аз төбелер саны ретінде анықтаймыз, оның сызықтық графигі G болады. Олар байқағандай, Эрдос-Фабер-Ловас болжамы кез келген графтың хроматикалық саны оның сызықтық қиылысу санынан аспайды деген мәлімдемеге тең. Бұл тұжырымдаманы клондар теориясы тұрғысынан қарастыруға болады.

introduced the problem with a story about seating assignment in committees: suppose that, in a university department, there are k committees, each consisting of k faculty members, and that all committees meet in the same room, which has k chairs. Suppose also that at most one person belongs to the intersection of any two committees. Is it possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs? In this model of the problem, the faculty members correspond to graph vertices, committees correspond to complete graphs, and chairs correspond to vertex colors. A linear hypergraph (also known as partial linear space) is a hypergraph with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The n cliques of size n in the Erdős–Faber–Lovász conjecture may be interpreted as the hyperedges of an n uniform linear hypergraph that has the same vertices as the underlying graph. In this language, the Erdős–Faber–Lovász conjecture states that, given any n uniform linear hypergraph with n hyperedges, one may n color the vertices such that each hyperedge has one vertex of each color. A simple hypergraph is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős–Faber–Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph. And, the hypergraph dual of vertex coloring is edge coloring. Thus, the Erdős–Faber–Lovász conjecture is equivalent to the statement that any simple hypergraph with n vertices has chromatic index (edge coloring number) at most n.

The graph of the Erdős–Faber–Lovász conjecture may be represented as an intersection graph of sets: to each vertex of the graph, correspond the set of the cliques containing that vertex, and connect any two vertices by an edge whenever their corresponding sets have a nonempty intersection. Using this description of the graph, the conjecture may be restated as follows: if some family of sets has n total elements, and any two sets intersect in at most one element, then the intersection graph of the sets may be n colored. The intersection number of a graph G is the minimum number of elements in a family of sets whose intersection graph is G, or equivalently the minimum number of vertices in a hypergraph whose line graph is G. define the linear intersection number of a graph, similarly, to be the minimum number of vertices in a linear hypergraph whose line graph is G. As they observe, the Erdős–Faber–Lovász conjecture is equivalent to the statement that the chromatic number of any graph is at most equal to its linear intersection number. present another yet equivalent formulation, in terms of the theory of clones.

Қатысушы мәселелер

Сондай-ақ, k төбесі бар k кликалардың бірігісінен құралған графтардың хроматикалық санын қарастыру қызығушылық тудырады, кликалар жұптарының қиылысының мөлшеріне шектеу қоймай. Мұндай жағдайда, олардың бірігісінің хроматикалық саны ең көп дегенде , ал кейбір осылай құралған графтар осы көптеген түстерді қажет етеді. Хроматикалық санның орнына бөлшектік хроматикалық санды қолданатын болжамның нұсқасы рас екені белгілі. Яғни, егер G графы бір-бірімен ең көп дегенде бір төбеде қиылысатын k кликаның бірігісінен құралса, онда G k түспен боялуы мүмкін. Қарапайым гиперграфтарды қабырғамен бояу аясында L саны қарапайым гиперграфтың үш немесе одан көп төбесі бар гиперқабырғаға тиесілі төбелер саны ретінде анықталады. Ол L-дің кез келген белгілі бір мәні үшін, осы L мәніне ие барлық қарапайым гиперграфтар үшін болжамның рас екенін тексеру үшін шекті есептеу жеткілікті екенін көрсетеді. Осы идеяға сүйене отырып, ол L ≤ 10 бар барлық қарапайым гиперграфтар үшін болжамның шын мәнінде рас екенін көрсетеді. Кликалардың бірігісінен құралған графтарды бояу тұрғысынан Хиндманның нәтижесі болжамның дұрыс екенін көрсетеді, егер кликалардың ең көп дегенде он бөлігі үш немесе одан көп кликаға тиесілі төбесі болса. Атап айтқанда, n ≤ 10 үшін бұл рас.