Кіріспе
Үшбұрыштық графтардың түстелуі туралы теорема. Экстремалды жиын теориясындағы теорема. Математикада Спернер леммасы – Брауердің тұрақты нүкте теоремасына ұқсас, үшбұрыштылықтың түстеуіне қатысты комбинаторлық нәтиже. Ол, өлшемді симплекстің үшбұрыштығының кез келген Спернер түстеуі (төменде сипатталған) барлық төбелері әртүрлі түстерге ие ұяшықты қамтиды. Осы сияқты алғашқы нәтижені Эммануэль Спернер доменнің инварианттылығын дәлелдеумен байланысты көрсеткен. Спернер түстеулері тұрақты нүктелерді тиімді есептеуде және түбір табу алгоритмдерінде қолданылады, сондай-ақ әділ бөлу (торт кесу) алгоритмдерінде де пайдаланылады. "Совет математикалық энциклопедиясы" (ред. И. М. Виноградов) бойынша, 1929 жылғы Кнастер, Борсук және Мазуркевичтің теоремасы да Спернер леммасы ретінде белгілі болған – бұл мәселе ағылшын тіліне аудармасында (ред. М. Хазевинкель) талқыланады. Қазір бұл Кнастер–Куратовский–Мазуркевич леммасы деп белгілі.
the theorem in extremal set theory
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an dimensional simplex contains a cell whose vertices all have different colors. The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points and in root finding algorithms, and are applied in fair division (cake cutting) algorithms. According to the Soviet Mathematical Encyclopaedia (ed. I. M. Vinogradov), a related 1929 theorem (of Knaster, Borsuk and Mazurkiewicz) had also become known as the Sperner lemma – this point is discussed in the English translation (ed. M. Hazewinkel). It is now commonly known as the Knaster–Kuratowski–Mazurkiewicz lemma.
Бір өлшемді корпус
Бір өлшемде Спернер леммасын аралық мән теоремасының дискретті түрі деп қарастыруға болады. Бұл жағдайда, егер дискретті функция тек 0 және 1 мәндерін қабылдаса, 0 мәнімен басталып, 1 мәнімен аяқталса, онда ол мәндерді тақ рет ауыстыруы тиіс.
Дәлел
Алдымен екі өлшемді жағдайды қарастырайық. Т үшбұрышталмасынан құрылған G графигін қарастырайық: G графигінің төбелері – Т үшбұрышталмасының мүшелері және үшбұрыштан тыс жердегі аумақ. Екі төбе шеттермен байланысқан, егер олардың сәйкес келетін аумақтары ортақ шекарамен шектесетін болса, сонда бір төбе 1 түспен, ал екіншісі 2 түспен боялған. АВ аралығында 1, 2 түстес шекаралардың тақ саны бар екеніне назар аударыңыз (өйткені А 1 түспен, ал В 2 түспен боялған; және АВ бойымен жылғанда, басы мен соңында әртүрлі түстер алу үшін түстердің тақ саны ауысуы керек). Сондықтан, G графигінде сыртқы аумаққа сәйкес келетін төбе тақ дәрежеге ие. Бірақ белгілі (қол тілесу леммасы) шекті графикте тақ дәрежелі төбелердің саны жұп болуы керек. Демек, сыртқы аумақты есепке алмайтын қалған графикте Т үшбұрышталмасының мүшелеріне сәйкес келетін тақ дәрежелі төбелердің тақ саны бар. Оңай көруге болады, Т үшбұрышталмасынан алынған үшбұрыштың дәрежесі тек 0, 1 немесе 2 болуы мүмкін, және 1 дәрежелі үшбұрыш 1, 2 және 3 түстерімен боялған. Осылайша, біз сәл күштірек қорытындыға келдік, ол Т үшбұрышталмасында толық боялған үшбұрыштардың саны тақ (немесе кемінде біреуі) екенін көрсетеді. Көп өлшемді жағдайды симплекстің өлшемі бойынша индукция арқылы дәлелдеуге болады. Екі өлшемді жағдайдағыдай, дәл сол логиканы қолданып, n өлшемді үшбұрышталмада толық боялған симплекстердің саны тақ екеніне келеміз.
The vertices of G are the members of T plus the area outside the triangle. Two vertices are connected with an edge if their corresponding areas share a common border with one endpoint colored 1 and the other colored 2. Note that on the interval AB there is an odd number of borders colored 1 2 (simply because A is colored 1, B is colored 2; and as we move along AB, there must be an odd number of color changes in order to get different colors at the beginning and at the end). Therefore, the vertex of G corresponding to the outer area has an odd degree. But it is known (the handshaking lemma) that in a finite graph there is an even number of vertices with odd degree. Therefore, the remaining graph, excluding the outer area, has an odd number of vertices with odd degree corresponding to members of T.
It can be easily seen that the only possible degree of a triangle from T is 0, 1, or 2, and that the degree 1 corresponds to a triangle colored with the three colors 1, 2, and 3. Thus we have obtained a slightly stronger conclusion, which says that in a triangulation T there is an odd number (and at least one) of full colored triangles. A multidimensional case can be proved by induction on the dimension of a simplex. We apply the same reasoning, as in the two dimensional case, to conclude that in a n dimensional triangulation there is an odd number of full colored simplices.
Комментарийлер
Мұнда граф теориясына жаңадан келген оқырман үшін бұрынғы дәлелдеменің толық түсіндірмесі келтірілген. Бұл схемада бұрын берілген мысалдың төбелерінің түстері нөмірленген. Төбелерінің саны әртүрлі кіші үшбұрыштар графте көлеңкеленген. Әрбір кіші үшбұрыш үшбұрыштаудан туындаған жаңа графтың түйініне айналады. Кіші әріптер аймақтарды белгілейді, сегіз – фигураның ішінде, ал i аймағы оның сыртындағы кеңістікті көрсетеді. Бұрын сипатталғандай, 1 және 2 нөмірленген қабырғалары бар түйіндер туындаған графта біріктіріледі. Мысалы, d түйіні i сыртқы аймақпен қабырға бөліседі және оның төбелерінің саны әртүрлі болғандықтан, ол да көлеңкеленген. b түйіні көлеңкеленбеген, өйткені екі төбесінің саны бірдей, бірақ ол сыртқы аймаққа қосылған. Мысалы, a түйінінің 1 мен 1 арасындағы қабырғасына 3 нөмірлі түйін енгізіп, сол түйінды a-ның екінші ұшымен қосу арқылы жаңа толық нөмірленген үшбұрыш қосуға болады. Мұндай жағдайда f және g түйіндері сияқты жаңа түйіндер жұбы құрылуы керек.
Спернер симплексін есептеу
Көлденең ұзындығы N болатын d өлшемді симплекс бар деп есептейік, және ол 1 қабырғалы кіші симплекстерге бөлінеді. Бір функция кез келген үшбұрыштылау төбесінің түсін қайтарады. Түсіргіштің Спернердің шекаралық шартын сақтауы кепілдендірілген. Қанша рет функцияны шақыру керек, чтобы "көлікті" симплекс табуға? Әрине, біз барлық үшбұрыштылау төбелерін қарастыра аламыз, олардың саны O(Nd) – өлшемділік белгілі болғанда N-ге қатысты көпмүшелік. Бірақ, мұны N-нің екілік өрнегіне қатысты көпмүшелік уақытта, яғни O(poly(log N)) уақытында істеуге болады ма? Бұл мәселені алғаш Христос Пападимитриу зерттеді. Ол PPAD деп аталатын күрделілік класын енгізді, оған осы және осыған ұқсас мәселелер кіреді (мысалы, Брауэрдің бекітілген нүктесін табу). Ол Спернер симплексін табу d=3 үшін де PPAD-толық екенін дәлелдеді. 15 жылдан кейін Чен мен Денг PPAD-толықтығын d=2 үшін де дәлелдеді. PPAD-қиын мәселелерін O(poly(log N)) уақытында шешуге болмайды деп есептеледі.
Таңбалардың кіші топтары
Үшбұрыштың әрбір төбесі бірнеше түспен белгіленуі мүмкін делік, сондықтан бояу функциясы әрбір кіші-симплекс үшін оның төбелеріндегі белгілер жиыны [n + 1] түстер жиынынан алынған жиын болады. Бұл жиын отбасын гиперграф ретінде қарастыруға болады. Егер симплекстің жағындағы әрбір v төбесі үшін f(v)-дегі түстер, жақ қабырғаларындағы түстер жиынының ішкі жиыны болса, онда толық бөлшек сәйкестікті қабылдайтын гиперграфпен суб-симплекс бар – яғни, сәйкес гиперграфта толық бөлшек сәйкестік болатын белгілеу. Мысал үшін, 1=n = 2 болғандағы теңгерілген белгілеу мысалдары:
For every sub simplex, the set of labelings on its vertices is a set family over the set of colors [n + 1]. This set family can be seen as a hypergraph. If, for every vertex v on a face of the simplex, the colors in f(v) are a subset of the set of colors on the face endpoints, then there exists a sub simplex with a balanced labeling – a labeling in which the corresponding hypergraph admits a perfect fractional matching. To illustrate, here are some balanced labeling examples for 1=n = 2:
({1}, {2}, {3}) (1, 1, 1) салмақтарымен теңгерілген. ({1,2}, {2,3}, {3,1}) (1/2, 1/2, 1/2) салмақтарымен теңгерілген. ({1,2}, {2,3}, {1}) (0, 1, 1) салмақтарымен теңгерілген. Бұл 1973 жылы Шапли тарапынан дәлелденген. Бұл KKMS леммасының комбинаторлық аналогы болып табылады.
Политопальды нұсқалар
Бізде n төбесі бар d өлшемді политоп P бар деп есептейік. P триангуляцияланған, ал триангуляцияның әрбір төбесі {1, …, n} жиынынан белгіленеді. Кез келген басты төбе i, i деп белгіленеді. Егер субсимплекс d өлшемді болса және оның d + 1 төбесінің әрқайсысы әртүрлі белгіге ие болса, онда ол толық белгіленген деп аталады. Егер P-нің F жағындағы әрбір төбе F-тің соңғы төбелеріндегі бір белгімен белгіленген болса, онда кем дегенде n – d толық белгіленген симплекстер бар. Кейбір ерекше жағдайлар: 1=d = n – 1. Бұл жағдайда P – симплекс. Политоптық Спернер леммасы кем дегенде 1 толық белгіленген симплекстің бар екендігіне кепілдік береді. Яғни, ол Спернер леммасына дейін тоғысып келеді. 1=d = 2. n төбесі бар екі өлшемді көпбұрыш триангуляцияланып, 1, …, n белгілерін пайдалана отырып, i және i + 1 (mod n) төбелері арасындағы әрбір жағында тек i және i + 1 белгілері қолданылады деп есептейік. Содан кейін кем дегенде n – 2 субүшбұрыш бар, онда үш түрлі белгі қолданылады. Атанасов бұл тұжырымды 1996 жылы 1=d = 2 жағдайында дәлелдеді. Жалпы жағдайдың дәлелін алғаш рет 2002 жылы де Лоера, Петерсон және Су ұсынды. Олар екі дәлел келтіреді: біріншісі конструкциялық емес және қиыршық тастар жиынтығының түсінігін пайдаланады; екіншісі конструкциялық және графтердегі жолдарды іздеу аргументтеріне негізделген. Мюнье теореманы политоптардан политоптық денелерге дейін кеңейтті, олар дөңес немесе жай ғана байланысты болуы міндетті емес. Атап айтқанда, егер P политоп болса, онда оның жақтарының жиынтығы политоптық дене болып табылады. Төбелері бар политоптық дененің кез келген Спернер белгілеуінде кем дегенде: толық белгіленген симплекстер бар, сондықтан осы симплекстердің кез келген жұбы екі түрлі белгілеуді алады. Дәреже – B(P)-нің оған тиесілі жиектерінің саны. Дәреженің кем дегенде d болғаны үшін төменгі шек кем дегенде n – d. Бірақ ол одан үлкен болуы мүмкін. Мысалы, n төбесі бар 4 өлшемдегі циклдік политоп үшін төменгі шек мынадай: Мусин теореманы d өлшемді бөлікті сызықтық көптүрліліктерге, шекарасы бар немесе жоқ, кеңейтті. Асада, Фрик, Пишароди, Полеви, Стонер, Цанг және Веллнер теореманы шекарасы бар псевдо-көптүрлілікке дейін кеңейтті және жұппен ерекшеленетін белгілері бар жақтардың санына төменгі шекараны жақсартты.
1=d = n – 1. In this case, P is a simplex. The polytopal Sperner lemma guarantees that there is at least 1 fully labeled simplex. That is, it reduces to Sperner's lemma. 1=d = 2. Suppose a two dimensional polygon with n vertices is triangulated and labeled using the labels 1, , n such that, on each face between vertex i and vertex i + 1 (mod n), only the labels i and i + 1 are used. Then, there are at least n – 2 sub triangles in which three different labels are used. The general statement was conjectured by Atanassov in 1996, who proved it for the case 1=d = 2. The proof of the general case was first given by de Loera, Peterson, and Su in 2002. They provide two proofs: the first is non constructive and uses the notion of pebble sets; the second is constructive and is based on arguments of following paths in graphs. Meunier extended the theorem from polytopes to polytopal bodies, which need not be convex or simply connected. In particular, if P is a polytope, then the set of its faces is a polytopal body. In every Sperner labeling of a polytopal body with vertices , there are at least:
fully labeled simplices such that any pair of these simplices receives two different labelings. The degree is the number of edges of B(P) to which belongs. Since the degree is at least d, the lower bound is at least n – d. But it can be larger. For example, for the cyclic polytope in 4 dimensions with n vertices, the lower bound is:
Musin further extended the theorem to d dimensional piecewise linear manifolds, with or without a boundary. Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner further exended the theorem to pseudomanifolds with boundary, and improved the lower bound on the number of facets with pairwise distinct labels.
Кубтық нұсқалар
Егер симплекс кіші симплекстерге бөлінбей, n өлшемді куб кіші n өлшемді кубтарға бөлінсе, Гарольд В. Кун келесі лемманы дәлелдеді. Кубтың бірлік кубтарға бөлінгенін елестетіңіз. Бөліністің әр төбесіне {1, …, n + 1} жиынынан белгі қойылады, сондықтан әр v төбесі үшін: (1) егер v төбесіндегі белгі i-ден аспаса; (2) егер v төбесіндегі белгі i болмаса. Онда барлық {1, …, n + 1} белгілері бар бірлік куб бар (кейбіреулері бірнеше рет қайталанады). 1=n = 2 ерекше жағдайы: егер квадрат кіші квадраттарға бөлінген болса, әр төбесіне {1,2,3} жиынынан белгі қойылады. Сол жақ қабырғасына 1 (= ең көп дегенде 1) белгісі қойылады; төменгі қабырғасына 1 немесе 2 (= ең көп дегенде 2) белгісі қойылады; жоғарғы қабырғасына 1 немесе 3 (= 2 емес) белгісі қойылады; және оң жақ қабырғасына 2 немесе 3 (= 1 емес) белгісі қойылады. Онда 1,2,3 белгіленген квадрат бар. Поанкаре-Миранда теоремасымен байланысты тағы бір нұсқасы мынадай. Кубтың бірлік кубтарға бөлінгенін қарастырайық. Әр төбеге n ұзындығы бар екілік вектормен белгі қойылады, сондықтан әр v төбесі үшін: (1) егер v төбесіндегі белгінің i координатасы 0 болса; (2) егер v төбесіндегі белгінің i координатасы 1 болса; (3) егер екі төбе жанындас болса, олардың белгілері ең көп дегенде бір координатада өзгеше болады. Онда барлық белгілері әртүрлі бірлік куб бар. Екі өлшемде, осы теореманы былай тұжырымдауға болады: толық белгіленген кубтардың саны тақ екенін дәлелдеу арқылы осы екі нәтижені күшейту. Мусин бұл нәтижелерді жалпы төртбұрыштарға дейін кеңейтті.
Ағаштар мен циклдер
Сол сияқты, шекті және шексіз ағаштар мен циклдар туралы да лемма бар.
Байланысты нәтижелер
Мирзахани мен Вондрак Sperner таңбалауының әлсіз түрін зерттейді, ондағы жалғыз талап – i таңбасы i төбесіне қарама-қарсы жаққа қолданылмауы керек. Олар мұны Sperner-ге қабылданған таңбалау деп атайды. Олар әрбір ұяшықта ең көп 4 таңба болатын Sperner-ге қабылданған таңбалаулар бар екенін көрсетеді. Сондай-ақ, олар әрбір Sperner-ге қабылданған таңбалауда кем дегенде екі түрлі таңбасы бар ұяшықтардың санының ең төменгі шегін дәлелдейді. Олар, сонымен қатар, кез келген Sperner-ге қабылданған тұрақты симплекстің бөлінісі үшін бөліктер арасындағы шекараның жалпы ауданы Вороной бөлінісі арқылы ең аз болады екенін дәлелдейді.
Қолданбалар
Спернер бояуы тұрақты нүктелерді тиімді есептеу үшін қолданылған. Спернерлік бояуды толық белгіленген симплекстер берілген функцияның тұрақты нүктелеріне сәйкес келетіндей етіп құрастыруға болады. Триангуляцияны кішірейте келе, толық белгіленген симплекстердің лиміті дәл сол тұрақты нүкте екенін көрсетуге болады. Осылайша, бұл техника тұрақты нүктелерді жуықтауға мүмкіндік береді. Бұған байланысты қолданыс – периодты орбиталарды және символдық динамиканы сандық түрде анықтау. Спернер леммасын түбір табу алгоритмдері мен әділ бөлу алгоритмдерінде де қолдануға болады; Simmons–Su протоколдарына қараңыз. Спернер леммасы Монски теоремасының дәлелінің маңызды бөлігі болып табылады, яғни квадратты тең ауданы бар тақ санға үшбұрыштарға бөлу мүмкін емес. Спернер леммасын айырбас экономикасында бәсекелестік тепе-теңдікті табу үшін де пайдалануға болады, бірақ оны табудың тиімді жолдары да бар. Оны алғаш жариялағаннан кейін елу жыл өткен соң, Спернер өзінің комбинаторлық леммасының дамуы, ықпалы және қолданылуы туралы шолу жасады.