Кіріспе
Жиындардың қиылысатын отбасыларына жоғарғы шектеу
Математикада, Эрдёс-Ко-Радо теоремасы жиындар отбасындағы жиындар санын шектейді, онда кез келген екі жиында кемінде бір ортақ элемент болады. Пауль Эрдёс, Чао Ко және Ричард Радо теореманы 1938 жылы дәлелдеді, бірақ оны 1961 жылға дейін жарияламады. Бұл комбинаторика саласының бір бөлігі және оның негізгі нәтижелерінің бірі.
Теорема барлық жиындары бірдей өлшемдегі жиындар отбасыларына қолданылады, және олардың барлығы белгілі бір үлкен жиынның ішкі жиындары болып табылады. Осы параметрлермен жиындар отбасын құрудың бір жолы – әрқайсысы элементпен бөлісетіндей, барлық ішкі жиындарға жататын бір элементті таңдап, содан кейін таңдалған элементті қамтитын барлық ішкі жиындарды құру. Эрдёс-Ко-Радо теоремасы проблема тривиалды емес болуы үшін жеткілікті үлкен болғанда, бұл құрылым ең үлкен қиылысатын отбасыларды тудырады. мәні үлкен болған кезде басқа да бірдей үлкен отбасылар болуы мүмкін, бірақ үлкен мәндер үшін осылайша құрылған отбасылар ғана ең үлкені болуы мүмкін. Эрдёс-Ко-Радо теоремасын гиперграфтар немесе Кнезер графтарындағы тәуелсіз жиындар арқылы да сипаттауға болады. Бірнеше ұқсас теоремалар жиындардан басқа математикалық объектілердің басқа түрлеріне де қолданылады, оның ішінде сызықтық кіші кеңістіктерге, пермутацияларға және тізбектерге. Олар ең үлкен қиылысатын отбасыларды элементті таңдап, таңдалған элементті қамтитын барлық объектілердің отбасын құру арқылы қалыптастыратынын сипаттайды.
Тарих
Пол Эрдосс, Чао Ко және Ричард Радо бұл теореманы 1938 жылы Англияда бірге жұмыс істегеннен кейін дәлелдеді. Радо Берлиннен Кембридж университетіне, ал Эрдос Венгриядан Манчестер университетіне көшіп келді, екеуі де нацистік Германияның ықпалынан қашты; Ко Луи Морделлдің студенті болды. Дегенмен, олар осы нәтижені 1961 жылға дейін жарияламады. Бұл шарттарға сәйкес келетін кіші жиындықтар жиынын дәл белгілі бір мөлшердегі кіші жиындықтарға дейін кеңейтуге болады, немесе әрбір кеңейтілген кіші жиындықты симметриялық тізбектік жіктеудегі бір тізбектен таңдауға болады.
Ең үлкен отбасылар
Эрдёс-Ко-Радо шектеуімен дәл сәйкес келетін элементтік жиынтықтардың қиылысатын отбасын құрудың қарапайым тәсілі – кез келген белгілі бір элементті таңдап, оны қамтитын барлық элементтік кіші жиынтықтарды алу болып табылады. Мысалы, 4 элементтік жиынтықтың 2 элементтік кіші жиынтықтары үшін , бұл отбасыны құрайды. Бұл отбасыдағы кез келген екі жиынтық қиылысады, себебі олардың екеуі де сол элементті қамтиды. Жиынтықтардың саны , себебі белгілі бір элемент таңдалғаннан кейін таңдау үшін қалған элементтер болады, және әрбір жиынтық осы қалған элементтерден біреуін таңдайды. жағдайында, бұл осы өлшемдегі жалғыз қиылысатын отбасы болып табылады. Алайда, жағдайында, көбірек жалпыланған құрылым бар. Әрбір элементтік жиынтықты оның толықтырғышымен сәйкестендіруге болады, ол одан ажыратылған жалғыз элементтік жиынтық. Содан кейін, осы бір-біріне толықтыратын жұптардың әрқайсысынан бір жиынтықты таңдаңыз. Мысалы, жоғарыдағы бірдей параметрлер үшін, бұл көбірек жалпыланған құрылымды қолдану арқылы, әр екі жиынтықтың қиылысатын отбасын құруға болады, бірақ үш жиынтықтың барлығына ортақ элемент болмайды. Бұл мысалда, барлық жиынтықтар бірінші мысалдағы жиынтықтардың толықтырылған нұсқалары, бірақ тек кейбір жиынтықтарды ғана толықтыруға болады. Бірінші типтегі отбасылар (жұлдыздар, диктатуралар, хунталар, орталықтандырылған отбасылар немесе негізгі отбасылар) – бұл бірегей ең үлкен отбасылар. Бұл жағдайда, дерлік ең үлкен өлшемді отбасының барлық жиынтықтарына ортақ элемент болады. Бұл қасиет деп аталады, бірақ дәл осы термин басқа қасиетті де сипаттау үшін қолданылған, а именно, (параметрлердің кең ауқымы үшін) Кнезер графигінен кездейсоқ таңдалған қабырғаларды жою оның тәуелсіз жиынтықтарының мөлшерін арттырмайды.
Any two sets in this family intersect, because they both include The number of sets is , because after the fixed element is chosen there remain other elements to choose, and each set chooses of these remaining elements. When this is the only intersecting family of this size. However, when , there is a more general construction. Each element set can be matched up to its complement, the only element set from which it is disjoint. Then, choose one set from each of these complementary pairs. For instance, for the same parameters above, this more general construction can be used to form the family
where every two sets intersect despite no element belonging to all three sets. In this example, all of the sets have been complemented from the ones in the first example, but it is also possible to complement only some of the sets. When , families of the first type (variously known as stars, dictatorships, juntas, centered families, or principal families) are the unique maximum families. In this case, a family of nearly maximum size has an element which is common to almost all of its sets. This property has been called although the same term has also been used for a different property, the fact that (for a wide range of parameters) deleting randomly chosen edges from the Kneser graph does not increase the size of its independent sets.
Дәлелдендіру
Эрдёш-Ко-Радо теоремасының бастапқы дәлелі негізге индукция қолданды. = үшін жағдай, қиылысатын отбасында жиын және оның толықтығын бірге қамту мүмкін емес екендігінен және осы жағдайда Эрдёш-Ко-Радо теоремасының шектеуі барлық -элементті жиынның санының жартысына тең екендігінен оңай шығады. Үлкен мәндерге индукциялық қадам "ауыстыру" деп аталатын әдісті қолданады, ол қиылысатын отбасылардағы элементтерді ауыстыру арқылы отбасын лексикографиялық тәртіп бойынша кішірейтіп, оны талдау оңай болатын канондық түрге келтіреді. 1972 жылы Гюла О.Х. Катона келесі қысқа дәлелді ұсынды: -элементті жиынның -элементті жиыншаларының кез келген қиылысатын отбасы үшін, барлық -элементті элементтерді кез келген циклдық тәртіпте орналастырыңыз және осы таңдалған циклдық тәртіпте -ұзындығындағы аралықтарды қарастырыңыз. Мысалы, егер және болса, сандар үшін мүмкін циклдық тәртіп сегіз 3-элементті аралықты қамтиды (айналып өтетіндері де бар):
bi|left=1.6|Let be any intersecting family of element subsets of an element set. Arrange all elements into any cyclic order, and consider the sets from that form intervals of length within this chosen cyclic order. For example if and , one possible cyclic order for the numbers is the order , which has eight 3 element intervals (including the ones that wrap around):
However, only some of these intervals can belong to , because they do not all intersect. Katona's key observation is that at most intervals from a single cyclic order may belong to This is because, if is one of these intervals, then every other interval of the same cyclic order that belongs to separates from , for some , by containing precisely one of these two elements. The two intervals that separate these elements are disjoint, so at most one of them can belong to Thus, the number of intervals in is at most one plus the number of pairs that can be separated.
Дегенмен, осы аралықтардың тек бір бөлігі ғана жата алады, өйткені олардың барлығы қиылыспайды. Катонаның негізгі байқауы – бір циклдық тәртіптен ең көп аралық жата алады. Бұл себебі, егер аралықтардың бірі болса, онда сол циклдық тәртіптегі басқа әрбір аралық, кейбір үшін, осы екі элементтің біреуін қамти отырып, бөліп тұрады. Осы элементтерді бөліп тұрған екі аралық қиылыспайды, сондықтан олардың ең көп дегенде біреуі жата алады. Осылайша, отбасыдағы аралықтардың саны ең көп дегенде бірге, бөліне алатын жұптардың санына тең болады.
bi|left=1.6|Let be any intersecting family of element subsets of an element set. Arrange all elements into any cyclic order, and consider the sets from that form intervals of length within this chosen cyclic order. For example if and , one possible cyclic order for the numbers is the order , which has eight 3 element intervals (including the ones that wrap around):
However, only some of these intervals can belong to , because they do not all intersect. Katona's key observation is that at most intervals from a single cyclic order may belong to This is because, if is one of these intervals, then every other interval of the same cyclic order that belongs to separates from , for some , by containing precisely one of these two elements. The two intervals that separate these elements are disjoint, so at most one of them can belong to Thus, the number of intervals in is at most one plus the number of pairs that can be separated.
Жалпылау
Теореманың жалпылауы үлкен қиылыстар болуы қажет болатын жиыншаларға қолданылады. Ердос-Ко-Радо теоремасының бастапқы түрі үшін, жалпы алғанда, егер басқа екі параметрге қатысты жеткілікті үлкен болса, жалпыланған теорема бойынша, қиылысатын жиыншалар отбасының мөлшері ең көп дегенде тең болады. Бұл шектеу қашан орындалады және кіші мәндерде қашан орындалмайды? Осы мөлшердегі жалғыз қиылысатын отбасылар, барлық жиыншалардың ортақ қиылысы ретінде элементтерді белгілеу арқылы және осы белгіленген элементтерді қамтитын барлық элемент жиыншаларын құру арқылы алынады. t-қиылысатын отбасының ең үлкен мөлшерін Ahlswede және Khachatrian анықтады, олардың Ahlswede–Khachatrian теоремасында көрсетілген. Бұл жалпылаудың сәйкес граф теориялық тұжырымдамасы Кнезер графиктерінің орнына Джонсон графиктерін қолданады. жеткілікті үлкен мәндері үшін, және әсіресе үшін, Ердос-Ко-Радо теоремасы және оның жалпылауы графтың тәуелсіздік санынан Шаннон сыйымдылығына дейін күшейтілуі мүмкін: қиылысатын элемент жиыншаларына сәйкес Джонсон графигінің Шаннон сыйымдылығы тең. Теореманы әрбір жиыншаның ортақ қиылысы бар отбасыларға да жалпылауға болады. Бұл әрбір жұптың қиылысуы шартын күшейтеді (ол үшін ), сондықтан бұл отбасылардың ең үлкен мөлшері бірдей болады, егер жеткілікті үлкен болса. Алайда, бұл жағдайда "жеткілікті үлкен" мағынасынан дейін азайтуға болады.
More precisely, this bound holds when , and does not hold for smaller values of When , the only intersecting families of this size are obtained by designating elements as the common intersection of all the subsets, and constructing the family of all element subsets that include these designated elements. The maximal size of a t intersecting family when was determined by Ahlswede and Khachatrian, in their Ahlswede–Khachatrian theorem. The corresponding graph theoretic formulation of this generalization involves Johnson graphs in place of Kneser For large enough values of and in particular for , both the Erdős–Ko–Rado theorem and its generalization can be strengthened from the independence number to the Shannon capacity of a graph: the Johnson graph corresponding to the intersecting element subsets has Shannon capacity
The theorem can also be generalized to families in which every subsets have a common intersection. Because this strengthens the condition that every pair intersects (for which ), these families have the same bound on their maximum size, when is sufficiently large. However, in this case the meaning of "sufficiently large" can be relaxed from to .
Аналогтары
Эрдёс-Ко-Радо теоремасына ұқсас көптеген нәтижелер белгілі, бірақ шекті жиынтықтардан өзге объектілер кластары үшін. Бұлар, әдетте, қиылысудың кейбір анықтамасы үшін қиылысатын объектілердің ең үлкен отбасыларын бір элементті таңдап, сол таңдалған элементті қамтитын барлық объектілердің отбасын құрастыру арқылы алуға болатындығы туралы мәлімдемелерді қамтиды. Мысалдарға мыналар жатады: Шекті өрістердегі сызықтық кіші кеңістіктердің қиылысатын отбасылары үшін Эрдёс-Ко-Радо теоремасының q аналогы бар. Екі пермутация, егер олардың біреуінің астындағы бір элементтің бейнесі бірдей болса, қиылысатын болып табылады. Элементтер жиынтығындағы қиылысатын пермутациялардың анық туысы – элементтердің біреуін бекіту (осы элементтің тұрақтандырушы кіші тобы). Сәйкес теорема – пермутациялардың қиылысатын отбасылары үлкендеу бола алмайды және өлшемділік қиылысатын отбасылар бір элементтің тұрақтандырғыштарының коссеттері болып табылады. Оларды бір тұрақты элементті басқа тұрақты элементке сәйкестендіретін пермутациялардың отбасылары ретінде тікелей сипаттауға болады. Жалпы алғанда, кез келген n және жеткілікті үлкен m үшін, әр жұптың ортақ элементтері бар пермутациялар отбасысының ең үлкен мөлшері m!/(m-n)! болып табылады, ал осы мөлшердегі жалғыз отбасылар нүктелік тұрақтандырушылардың коссеттері болып табылады. Сонымен қатар, граф теориясы терминдерінде элементтердің пермутациялары толық екіжақты графтың толық сәйкестіктеріне сәйкес келеді және теорема бойынша, әр жұптың шеттері бар толық сәйкестіктер отбасылары арасында ең үлкен отбасылар барлық таңдалған сәйкестіктерден тұрады. Теореманың басқа аналогы, жиынтықтың бөлімдері үшін, толық графтың (жұп санындағы) толық сәйкестіктерін ерекше жағдай ретінде қамтиды. Бұл жерде қос факторлыны көрсететін сәйкестіктер бар. Жұппен қиылысатын (яғни, олардың ортақ жиегі бар) сәйкестіктердің ең үлкен отбасы мөлшері бар және бір жиекті бекіту және қалған n-1 ұшымен сәйкестіктің барлық жолдарын таңдау арқылы алынады. Ішінара геометрия – белгілі бір аксиомаларды қанағаттандыратын, барлық сызықтарда бірдей нүктелер саны және барлық нүктелер сызықтардың бірдей санына жататын шекті көптеген абстрактіл нүктелер мен сызықтардың жүйесі. Ішінара геометрияда, кез келген бір нүкте арқылы өтетін сызықтар жиынтығынан жұппен қиылысатын ең үлкен жүйе алынуы мүмкін. Екі жиынтық, егер олардың әрқайсысында бірдей белгісі бар ортақ элемент болса, қиылысатын болып табылады. Содан кейін элементтік ғаламнан алынған элементтік белгіленген жиынтықтардың қиылысатын отбасы ең көп дегенде белгіленген жиынтықтардан тұрады. Бұл санды бір элемент пен оның белгісін бекіту арқылы және қалған элементтер мен белгілерді еркіндікпен таңдау арқылы алуға болады. Ұзындығы n және алфавит мөлшері k болатын тізбектер үшін, егер екеуінің де бірдей символы бар болса, екі тізбекті қиылысатын деп анықтауға болады. Ең үлкен қиылысатын отбасылар бір орынды және сол орынға арналған белгіні таңдап, қалған орынды кездейсоқ өзгертуге жол беру арқылы алынады. Бұл отбасылар тізбектерден тұрады және осы мөлшердегі жұппен қиылысатын жалғыз отбасылар болып табылады. Жалпы алғанда, әр екі тізбекте тең белгілері бар орын саны k болатын тізбектердің ең үлкен отбасылары k, n және m-ге тәуелді сан үшін сол белгілер үшін белгілерді таңдап, әрқайсысында кем дегенде k таңдалған белгілері бар тізбектердің отбасын құрастыру арқылы алынады. Бұл нәтижелерді Хэмминг схемасы бойынша теориялық түрде түсіндіруге болады. Гил Калай мен Карен Мегер ұсынған дәлелденбеген болжам, бұрыштары n болатын дөңгелек көпбұрыштың үшбұрыштарға бөлінуі үшін тағы бір аналогқа қатысты. Барлық үшбұрыштардың саны Каталан саны болып табылады, ал болжам бойынша әр жұптың шеттері бар үшбұрыштар отбасының ең үлкен мөлшері бар. Көпбұрыштың бір ұшын үшбұрышпен кесіп, қалған n-3 ұшы бар көпбұрышты үшбұрыштарға бөлудің барлық жолдарын таңдау арқылы дәл өлшемді қиылысатын отбасы алынуы мүмкін.
There is a q analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If is an intersecting family of dimensional subspaces of an dimensional vector space over a finite field of order , and , then
where the subscript q marks the notation for the Gaussian binomial coefficient, the number of subspaces of a given dimension within a vector space of a larger dimension over a finite field of In this case, a largest intersecting family of subspaces may be obtained by choosing any nonzero vector and constructing the family of subspaces of the given dimension that all contain the chosen vector. Two permutations on the same set of elements are defined to be intersecting if there is some element that has the same image under both permutations. On an element set, there is an obvious family of intersecting permutations, the permutations that fix one of the elements (the stabilizer subgroup of this element). The analogous theorem is that no intersecting family of permutations can be larger, and that the only intersecting families of size are the cosets of one element stabilizers. These can be described more directly as the families of permutations that map some fixed element to another fixed element. More generally, for any and sufficiently large , a family of permutations each pair of which has elements in common has maximum size , and the only families of this size are cosets of pointwise stabilizers. Alternatively, in graph theoretic terms, the element permutations correspond to the perfect matchings of a complete bipartite graph and the theorem states that, among families of perfect matchings each pair of which share edges, the largest families are formed by the matchings that all contain chosen Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph (with even). There are matchings, where denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size and is obtained by fixing one edge and choosing all ways of matching the remaining vertices. A partial geometry is a system of finitely many abstract points and lines, satisfying certain axioms including the requirement that all lines contain the same number of points and all points belong to the same number of lines. In a partial geometry, a largest system of pairwise intersecting lines can be obtained from the set of lines through any single
A signed set consists of a set together with sign function that maps each element to Two signed sets may be said to intersect when they have a common element that has the same sign in each of them. Then an intersecting family of element signed sets, drawn from an element universe, consists of at most
signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining elements and signs
For strings of length over an alphabet of size , two strings can be defined to intersect if they have a position where both share the same symbol. The largest intersecting families are obtained by choosing one position and a fixed symbol for that position, and letting the rest of the positions vary arbitrarily. These families consist of strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have positions with equal symbols are obtained by choosing positions and symbols for those positions, for a number that depends on , , and , and constructing the family of strings that each have at least of the chosen symbols. These results can be interpreted graph theoretically in terms of the Hamming scheme. An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with vertices. The number of all triangulations is a Catalan number , and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size An intersecting family of size exactly may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining vertex polygon.
Қолданбалар
Эрдёс-Ко-Радо теоремасы ықтималдық теориясында келесі нәтижені дәлелдеуге қолданылуы мүмкін. Бір болу ықтималдығы *p* болатын тәуелсіз 0–1 кездейсоқ шамалар болсын, және *x* осы шамалардың кез келген бекітілген дөңгелек комбинациясы болсын. Содан кейін…
Дәлелдеме индикатор векторлары үлкен дөңгелек комбинацияға ие болатын шамалардың ішкі жиынтықтарының қиылыспауы тиіс екенін байқауды және осы жиынтықтардың санын шектеу үшін Эрдёс-Ко-Радо теоремасын пайдалануды қамтиды. Эрдёс-Ко-Радо теоремасының тұрақтылық қасиеттері Кнезер графиктерінің бұрыс түс қағазындағы монохроматикалық қабырғаларды табуға арналған тиімді алгоритмде маңызды рөл атқарады. Эрдёс-Ко-Радо теоремасы филогенетикалық ағаштар кеңістігінің симметриясын сипаттау үшін де қолданылған.
The proof involves observing that subsets of variables whose indicator vectors have large convex combinations must be non disjoint and using the Erdős–Ko–Rado theorem to bound the number of these subsets. The stability properties of the Erdős–Ko–Rado theorem play a key role in an efficient algorithm for finding monochromatic edges in improper colorings of Kneser graphs. The Erdős–Ko–Rado theorem has also been used to characterize the symmetries of the space of phylogenetic trees.