Қиылысулар санының немесе қиылысулар туралы леммның теңсіздігі осы бағананың қиылысуларының ең аз санының төменгі қырын қабырға мен бағанның жоғарғы санынан функция ретінде береді. Лемма e қабырғаларының саны N жоғарғы санымен салыстырғанда жеткілікті үлкен графтар үшін қиылыстар саны кем дегенде E3/n2 пропорционал екенін айтады.

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

Бекіту және тарих
Қиылыстар санының теңсіздігі e > 7n, CR(G) бағанындағы қиылыстар саны теңсіздікті қанағаттандырады

{\displaystyle \operatorname {cr} (G)\geq {\frac {E^{3} {29n^{2}}}}.} \operatorname{cr} (G) \geq \frac{e^3}{29 n^2}.
Константа 29 қазіргі уақытта ең жақсы және Акерманға тиесілі. Бұл мақаланы толықтырып, дамыту арқылы, Уикипедияға көмектесе аласыз.

7 константасы 4 дейін төмендеуі мүмкін, бірақ бұл константаның бағасы 29 ең нашар константамен ауыстырылады 64.

Қосымшалар
Бұл ескертуді дәлдеп ауыстыру қажет

Кейінірек Секей бұл теңсіздік қақтығыс геометриясындағы кейбір маңызды Теоремалардың өте қарапайым дәлелін береді деп түсінді. Мысалы, Семереди-Троттер теоремасы, осы нүктелер саны мен жазықтықтағы түзулердің арасындағы мүмкін болатын инциденция санының жоғарғы қыры, оның ұштары берілген нүктелер, ал қабырғалары — нүктелерді қосатын түзу кесінділер болатын баған тұрғызылған жөн. Егер Жетіереди-Троттер теоремасына қарағанда инциденция көп болса, бұл бағандар тура жұптардың жалпы санына қарағанда көп қиылысатын болар еді, бұл мүмкін емес. Теңсіздік[en] теоремасын дәлелдеу үшін де қолдануға болады, егер соңғы нүкте саны коллинеарлық нүктелердің сызықтық саны болмаса, онда бұл сан түрлі түзулердің квадраттық санын анықтайды[6]. Тамал Дей геометриялық k-жиындардың жоғарғы шекарасын дәлелдеу үшін теңсіздік қолданды[en][7].

Дәлелдеу
Алдымен алдын ала баға береміз — кез келген G бағаны үшін N шыңдары және E қабырғалары бар

{\displaystyle \operatorname {cr} (G)\geq e-3N} \operatorname{cr} (G) \geq e – 3n.
Мұны дәлелдеу үшін CR(G) қиылысу дәлдігі бар g бағанының суретін ұсынамыз. Сонда біз кем дегенде e − cr(G) қабырғалары мен N шыңдары бар бағандарды таба аламыз, сондықтан бұл бағандар планарен. Бірақ Эйлер формуласынан біз қажетті e − cr(G) ≤ 3n болуы керек. (Іс жүзінде біз n ≥ 3 үшін e − cr (G) ≤ 3n − 6).

Қиылыстар санының нақты теңсіздігін алу үшін, біз енді ықтимал дәлелдерді қолданамыз. 0 < p < 1 кейінірек таңдап алатын ықтимал параметр болсын. G бағанының әрбір шыңы p ықтималдығына қарамастан H-ға түсетін, ал G бағанының қыры H бағанына түскен кезде және тек екі шыңы h бағанына түскен кезде ғана түседі. H G бағаны кіші баған болғандықтан, G бағаны суретте h бағаны суреті бар. Алдын ала қиылысу теңсіздігіне сәйкес бізде

{\displaystyle \operatorname {cr} _ {H}\geq e_{H} – 3n_{H}.} \operatorname{cr}_h \geq e_H – 3n_H.
Осы шамалардың математикалық күтулерін қарастырайық,

{\displaystyle \mathbf {E} [\operatorname {cr} _ {H}]\geq \mathbf {E} [e_{H}]-3\mathbf {E} [n_{H}].} \mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] – 3 \mathbf{E}[n_H].

Аралас қиылысатын қабырғаларды қиылыстар саны азаяды
Әрбір N жоғарғы G бағаны p ықтималдығымен h бағанына кіретіндіктен, Біз e[nH] = pn иеміз. Осыған ұқсас, қабырғалардың әрбір G бағаны p2 Н бағанында болу ықтималдығы бар, себебі графаның екі ұшы да онда h болуы тиіс. Соңында, суреттегі әрбір қиылысудың G бағанында p4 Н бағанында болу ықтималдығы бар, өйткені әрбір қиылысудың төрт шыңының болуын талап етеді. Оны көрсету үшін CR(G) қиылыстарымен G графасын ұсынамыз. Біз осы суреттегі кез келген екі қабырға жалпы ұшымен қиылыспауға жол бере аламыз, әйтпесе олар альфа әрпіне жақын нәрсе құрайды (суретті қараңыз) және Біз доғаның бір бөлігін қиылысу нүктесіне дейін ауыстыра және қиылысулар санын азайта аламыз. Осылайша, E[crH] = p4cr (G) және біз аламыз

{\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.} p^4 \operatorname{cr}(G) \geq p^2 e – 3 p n.
Енді, егер біз p = 4n/e < 1 (Біз e > 4n деп ойладық), кейбір алгебралық есептеулерден кейін,

{\displaystyle\operatorname {cr} (G) \geq {\frac {E^{3} {64n^{2}}}}.} \operatorname{cr} (G) \geq \frac{e^3}{64 N^2}.
Бұл тәсілдің шағын жақсаруы 64 e > 7.5 n үшін 33.75-ке ауыстыруға мүмкіндік береді[3].

Вариация
Бұл мақаланы толықтырып, дамыту арқылы, Уикипедияға көмектесе аласыз.

{\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2} {n^{r+1}}}}.} \operatorname{cr} (G) \geq c_r\frac{e^{r+2} {n^{r+1}}.