Сидоренкос болжам - Википедия - Sidorenkos conjecture

Сидоренконың болжамы маңызды болып табылады болжам өрісінде графтар теориясы, қойылған Александр Сидоренко 1986 жылы. Болжам бойынша, кез-келген үшін екі жақты граф және график қосулы орташа дәрежесі бар шыңдар , кем дегенде бар даналарының көшірмелері жылы , кішігірім қате мерзіміне дейін. Ресми түрде ол туралы интуитивті теңсіздікті қамтамасыз етеді график гомоморфизмі тығыздығы графондар. Болжалды теңсіздік көшірмелердің тығыздығы туралы мәлімдеме ретінде түсіндірілуі мүмкін графикте асимптотикалық түрде кездейсоқ графиктің көмегімен минимизацияланады, өйткені оны күтуге болады көшірме болатын ықтимал ішкі графиканың бөлігі егер әр жиек ықтималдықпен болса .

Мәлімдеме

Келіңіздер график болу. Содан кейін бар деп айтылады Сидоренконың мүлкі егер, бәріне графондар , теңсіздік

шындық, қайда болып табылады гомоморфизм тығыздығы туралы жылы .

Сидоренконың болжамында (1986) әрбір екіжақты графиктің Сидоренконың қасиеті болатындығы айтылған.[1]

Егер бұл график , бұл біркелкі кездейсоқ картаға түсіру ықтималдығы дейін гомоморфизм - бұл, ең болмағанда, әр шетіндегі өнім сол жиектің шетіне кескінделу ықтималдығы . Бұл шамамен шыңдар саны және орташа дәрежесі бар кездейсоқ таңдалған графиктің белгіленген көшірмелердің минималды саны болатындығын білдіреді. . Бұл таңқаларлық болжам емес, өйткені теңсіздіктің оң жағы картаға түсудің гомоморфизм болу ықтималдығы, егер әр шеткі карта тәуелсіз болса. Сондықтан екі тараптың кем дегенде бірдей тәртіпте болатынын күту керек. Графондардың табиғи кеңеюі әр графонның болып табылатындығынан туындайды шектеу нүктесі графиктердің кейбір реттілігі.

Бұл талап Сидоренконың мүлкі болу үшін екі жақты болып табылады - егер қажет болса - бұл екі жақты граф бері үшбұрышсыз. Бірақ жиектерінің санынан екі есе артық , демек, Сидоренконың мүлкі иелік етпейді . Осыған ұқсас аргумент тақ циклі бар бірде бір графиктің Сидоренконың қасиетіне ие еместігін көрсетеді. Егер графта тақ циклдар болмаса ғана екі жақты болғандықтан, бұл Сидоренконың қасиетіне ие бола алатын жалғыз графиктер екі жақты графтар болатындығын білдіреді.

Эквивалентті тұжырымдау

Сидоренконың меншігі келесі қайта құруға тең:

Барлық графиктер үшін , егер бар шыңдары және орташа дәрежесі , содан кейін .

Бұл эквивалентті, өйткені гомоморфизм саны дейін жиектерінің санынан екі есе артық , және теңсіздік тек қашан тексерілуі керек - бұл бұрын айтылғандай график.

Бұл тұжырымдамада инъекциялық емес гомоморфизмдер саны болғандықтан дейін ең көп дегенде тұрақты уақыт , Сидоренконың мүлкі, ең болмағанда, бар дегенді білдіреді даналарының көшірмелері жылы .

Мысалдар

Бұрын айтылғандай, Сидоренконың қасиетін дәлелдеу үшін барлық графиктер үшін теңсіздікті көрсету жеткілікті . Осы бөлімде график болып табылады орташа дәрежесі бар шыңдар . Саны бастап гомоморфизмдердің санын айтады дейін . Бұл шама сияқты .

Сидоренконың кейбір графиктерге арналған меншікті элементтерінің дәлелі мынаған сәйкес келеді Коши-Шварц теңсіздігі немесе Хёлдер теңсіздігі. Басқаларын қолдану арқылы жасауға болады спектрлік графтар теориясы, әсіресе ұзындықтың жабық жолдарының саны туралы ескертуді атап өту керек шыңнан шыңға дейін жылы ішіндегі компонент болып табылады ші қатар және матрицаның бағанасы , қайда болып табылады матрица туралы .

Коши-Шварц: 4 цикл C4

Екі шыңды бекіту арқылы және туралы , әрбір данасы бар және қарама-қарсы ұштарда екі (міндетті түрде ерекшеленбейтін) ортақ көршілерді таңдау арқылы анықтауға болады және . Рұқсат ету белгілеу код дәрежесі туралы және (яғни жалпы көршілердің саны), бұл білдіреді

Коши-Шварц теңсіздігі. Қосынды енді барлық төбелер жұбы мен олардың ортақ көршілерінің санына айналды, бұл барлық төбелер мен жұптардың көршілерінің санымен бірдей. Сонымен

Коши-Шварц тағы да. Сонымен

қалағандай.

Спектрлік графикалық теория: 2к-цикл C2к

Коши-Шварцтың көзқарасы талғампаз және қарапайым, ол барлық циклдарда бірден қорытыла бермейді. Дегенмен, барлық циклдарда Сидоренконың қасиеттері бар екенін дәлелдеу үшін спектрлік графикалық теорияны қолдануға болады. Сидоренконың болжауынша тақ циклдар есепке алынбайды, себебі олар екі жақты емес.

Тұйық жолдар туралы бақылауларды қолдана отырып, осыдан шығады - диагональды жазбалардың қосындысы . Бұл тең із туралы , ол өз кезегінде -ның өкілеттіктері меншікті мәндер туралы . Егер меншікті мәндері болып табылады , содан кейін мин-макс теоремасы мұны білдіреді

қайда векторы болып табылады компоненттер, олардың барлығы . Бірақ содан кейін

өйткені а-ның меншікті мәндері нақты симметриялық матрица нақты. Сонымен

қалағандай.

Энтропия: ұзындығы 3 жолдары

Дж.Л.Сян Ли және Балас Сегеди (2011) пайдалану идеясын енгізді энтропия Сидоренко болжамының кейбір жағдайларын дәлелдеу. Сегеди (2015 ж.) Кейінірек екі жақты графиктердің одан да кең класы Сидоренконың меншігінде екенін дәлелдеу үшін идеяларды одан әрі қолданды.[2] Сегедидің дәлелі абстрактілі және техникалық болғанымен, Тим Гауэрс және Джейсон Лонг ұзындық жолдары сияқты нақты жағдайлар үшін аргументті қарапайымға дейін қысқартты .[3] Негізінде дәлелдеу жағымды нәрсені таңдайды ықтималдықтың таралуы жолында шыңдарды таңдау және қолдану Дженсен теңсіздігі (яғни дөңес) теңсіздікті шығару.

Ішінара нәтижелер

Мұнда екі жақты графиктердің тізімі берілген Сидоренконың меншігінде екендігі көрсетілген. Келіңіздер екіге бөліну .

  • Жолдар 1959 жылы Мулхолланд пен Смит көрсеткендей Сидоренконың меншігіне ие болу керек (Сидоренко болжамды тұжырымдамас бұрын).[4]
  • Ағаштар Сидоренконың жалпылама жолдары бар. Мұны Сидоренко 1991 жылғы мақаласында көрсеткен.[5]
  • Жұп ұзындықтағы циклдар Сидоренконың меншігінде бұрын көрсетілгендей. Сидоренко мұны өзінің 1991 жылғы мақаласында да көрсетті.
  • Толық екі жақты графиктер Сидоренконың меншігінде болады. Бұл Сидоренконың 1991 жылғы мақаласында да көрсетілген.
  • Екі жақты графиктер Сидоренконың меншігінде болады. Бұл Сидоренконың 1991 жылғы мақаласында да көрсетілген.
  • Гиперкуб графиктері (. жалпылау ) 2008 жылы Хатами көрсеткендей Сидоренконың меншігінде болуы керек.[6]
    • Жалпы, графикалық графиктер (Хатами енгізгендей) Сидоренконың меншігінде болады.
  • Егер шыңы бар болса бұл барлық шыңдары бар көршілер (немесе керісінше), содан кейін 2010 жылы Конлон, Фокс және Судаков көрсеткен Сидоренконың меншігіне ие.[7] Бұл дәлел қолданылған тәуелді кездейсоқ таңдау әдіс.
  • Барлық екі жақты графиктер үшін , оң натурал сан бар сияқты -жару туралы Сидоренконың меншігінде. Мұнда - үрлеу әрбір шыңды in орнына ауыстыру арқылы қалыптасады бірге әрқайсысы өзінің бастапқы көршілерімен байланысты өзінің көшірмелері . Мұны Конлон мен Ли 2018 жылы көрсетті.[8]
  • Сидоренконың қасиеттеріне ие жаңа графикті құру үшін Сидоренконың қасиеттері бар графиктердің жиынтығын алатын кейбір рекурсивті тәсілдер қолданылды. Бұл жолдағы негізгі ілгерілеуді Сидоренко өзінің 1991 жылғы еңбегінде, Ли және Сегедди 2011 жылы жасады[9], және Ким, Ли және Ли 2013 ж[10].
    • Ли мен Сегедидің қағаздары энтропия әдістерін қолданып, «шағылысатын ағаштар» деп аталатын графиктер класы үшін қасиетін дәлелдеді.
    • Ким, Ли және Лидің мақалалары бұл идеяны «ағаштармен реттелетін графиктер» деп аталатын ағаш тәрізді құрылымы бар графиктер класына дейін кеңейтті.

Дегенмен, Сидоренконың болжамдары әлі де ашық тұрған графиктер бар. Мысал ретінде «Мебиус жолағы» графигін алуға болады , жою арқылы пайда болды -өлшемдері бар толық екі жақты графиктен цикл .

Ласло Ловаш Сидоренко болжамының жергілікті нұсқасын дәлелдеді, яғни кесілген норма мағынасында кездейсоқ графикаға «жақын» графиктер үшін.[11]

Болжамды мәжбүрлеу

Графиктер тізбегі аталады тығыздықпен квази-кездейсоқ тығыздығы үшін

егер әрбір график үшін болса ,

Графиктердің реттілігі осылайша қасиеттерге ие болады Erdős – Rényi кездейсоқ графигі .

Егер жиек тығыздығы болса бойынша бекітілген , демек, шарт графиктердің реттілігі әр граф үшін Сидоренконың қасиетіндегі теңдік жағдайына жақын екендігін білдіреді .

Чунг, Грэм және Уилсонның квази-кездейсоқ графиктер туралы 1989 жылғы мақаласынан бұл үшін жеткілікті кездейсоқ графиктен күткенге сәйкес келетін санақ (яғни шарт орындалады) ).[12] Сонымен қатар қағазда қандай графиктер бар екендігі сұралады осы қасиетке ие болу керек . Мұндай графиктер деп аталады графиктерді мәжбүрлеу өйткені олардың саны графиктер тізбегінің квази кездейсоқтығын басқарады.

Мәжбүрлеу туралы болжам келесідей:

График егер ол ағаш емес, екі жақты болса ғана мәжбүр етеді.

Мұны түсіну тікелей мәжбүрлейді, демек ол ағаш емес, екі жақты. Графиктерді мәжбүрлеудің кейбір мысалдары тіпті циклдар болып табылады (Чунг, Грэм және Уилсон көрсеткен). Скокан мен Тома ағаштар емес барлық екі жақты графикалар мәжбүрлейтінін көрсетті.[13]

Сидоренконың жорамалы мәжбүрлі болжамнан туындайды. Бұдан басқа, мәжбүрлі болжам Сидоренконың меншігіндегі теңдікке жақын графиктер квази-кездейсоқтық шарттарын қанағаттандыруы керек екенін көрсетеді.[14]

Әдебиеттер тізімі

  1. ^ Сидоренко, Александр (1993), «Екі жақты графиктер үшін корреляциялық теңсіздік», Графиктер және комбинаторика, 9 (2–4): 201–204, дои:10.1007 / BF02988307
  2. ^ Сегеди, Балас (2015), Сидоренко болжамына ақпараттық теоретикалық көзқарас, arXiv:1406.6738
  3. ^ Говерс, Тим. «Энтропия және Сидоренконың болжамы - Сегедиден кейін». Gowers веб-блогы. Алынған 1 желтоқсан 2019.
  4. ^ Мулхолланд, Х.П .; Смит, Седрик (1959), «Генетикалық теорияда туындайтын теңсіздік», Американдық математикалық айлық (66): 673–683, дои:10.1080/00029890.1959.11989387
  5. ^ Сидоренко, Александр (1991), «Екі жақты графиктер тудыратын функционалдық теңсіздіктер», Дискретная математика (3): 50–65, дои:10.1515 / dma.1992.2.5.489
  6. ^ Хатами, Хамед (2010), «Графикалық нормалар және Сидоренконың болжамдары», Израиль математика журналы (175): 125–150, arXiv:0806.0047
  7. ^ Конлон, Дэвид; Түлкі, Джейкоб; Судаков, Бенни (2010), «Сидоренко болжамының болжамды нұсқасы», Геометриялық және функционалдық талдау (20): 1354–1366, arXiv:1004.4236
  8. ^ Конлон, Дэвид; Ли, Джункён (2018), Сидоренконың жарылысқа арналған болжамы, arXiv:1809.01259
  9. ^ Ли, Дж.Л.Сян; Сегеди, Балас (2011), Логарифимдік есептеулер мен Сидоренконың жорамалы бойынша, arXiv:1107.1153
  10. ^ Ким, Чжон Хан; Ли, Чонгбум; Ли, Джункён (2013), Сидоренко болжамына екі көзқарас, arXiv:1310.4383 Сілтемеде белгісіз параметр жоқ: |1= (Көмектесіңдер)
  11. ^ Ловас, Ласло (2010), Қол қойылған графондардағы графикалық тығыздық және жергілікті Сидоренко болжамдары, arXiv:1004.3026
  12. ^ Чун, Фан; Грэм, Рональд; Уилсон, Ричард (1989), «Квази-кездейсоқ графиктер», Комбинаторика, 9 (4): 345–362, дои:10.1007 / BF02125347
  13. ^ Скокан, Йозеф; Тома, Любос (2004), «Екі жақты субографиялар және квази-кездейсоқтық», Графиктер және комбинаторика, 20 (2): 255–262, дои:10.1007 / s00373-004-0556-1
  14. ^ Конлон, Дэвид; Түлкі, Джейкоб; Судаков, Бенни (2010), «Сидоренко болжамының болжамды нұсқасы», Геометриялық және функционалдық талдау (20): 1354–1366, arXiv:1004.4236