Берр-Эрденің болжамы - Википедия - Burr–Erdős conjecture

Жылы математика, Берр-Эрдс жорамалы қатысты мәселе болды Рэмси нөмірі туралы сирек графиктер. Болжам атымен аталды Стефан Бурр және Paul Erdős, және көпшілігінің бірі Ердостың атындағы болжамдар; онда кез-келген сирек кездесетін графикалық отбасылардағы Рэмси графигінің саны болуы керек екендігі айтылған түзу өседі санында төбелер график.

Болжамды Чонгбум Ли дәлелдеді (осылайша ол қазір теорема).[1]

Анықтамалар

Егер G болып табылады бағытталмаған граф, содан кейін деградация туралы G ең төменгі сан б сияқты әрбір субографиясы G градус шыңынан тұрады б немесе кішірек. Төмендеуі бар график б аталады б- деградация. Эквивалентті түрде, а б-дегенеративті график деп -ге дейін азайтылатын график бос график градус шыңын бірнеше рет алып тастау арқылы б немесе кішірек.

Бұдан шығады Рэмси теоремасы кез келген график үшін G ең аз бүтін сан бар , Рэмси нөмірі туралы G, кез келген сияқты толық граф ең болмағанда төбелер кімдікі шеттері қызыл немесе көк түсте монохроматикалық көшірме бар G. Мысалы, үшбұрыштың Рэмси саны 6-ға тең: алты шыңдағы толық графтың шеттері қызыл немесе көк түске боялғанына қарамастан, қызыл немесе көк үшбұрыш әрқашан болады.

Болжам

1973 жылы, Стефан Бурр және Paul Erdős келесі болжам жасады:

Әрбір бүтін сан үшін б тұрақты бар cб сондықтан кез келген б-герілген график G қосулы n шыңдарда ең көп дегенде Рэмси саны бар cб n.

Яғни, егер n-текс сызбасы G болып табылады б- дегенерация, содан кейін монохроматикалық көшірме G әрбір екі жиектегі толық графикте болуы керек cб n төбелер.

Белгілі нәтижелер

Толық болжам дәлелденгенге дейін, ол кейбір ерекше жағдайларда шешілді. Бұл шектелген градустық графиктер үшін дәлелденді Чваталь және басқалар (1983); олардың дәлелі өте жоғары мәнге әкелді cб, және осы тұрақты жақсартулар жасады Итон (1998) және Грэм, Родл және Ручинский (2000). Жалпы алғанда, болжам шындыққа сәйкес келеді б- шектелген максималды дәрежесі бар графиктерді қамтитын реттелетін графиктер, жазықтық графиктер және а-ны қамтымайтын графиктер бөлу туралы Қб.[2] Ол сондай-ақ бөлінген графиктермен белгілі, онда екі шектес шыңның екіден жоғары дәрежесі жоқ графиктер.[3]

Ерікті графиктер үшін Рэмси саны шамалы ғана супер сызықтық өсетін функциямен шектелетіні белгілі. Нақтырақ айтқанда, Фокс және Судаков (2009) тұрақты болатынын көрсетті cб кез келген үшін б- деградация n-текс сызбасы G,

Ескертулер

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