dee brune-erdos pramey (graph siddhant)

graph siddhant mein, dee brune-erdos pramey ack anant graph key graph rung koo usee samasya seey sambandhit kartaa haye joe isake seemit upgraph parr haye. yeh bataata haye kii jaba sabhi seemit upgraph koo sootra _ 1 rangon key saath rangeen kiya jaa sakata haye, tou poore graph key liye yahee sach haye. iss pramey koo nikola govert dee brujan aur paul erdos (1951) dwara saabit kiya gayaa thaa, jinake naam parr iska naam rakhaa gayaa haye.
dee brune-erdos pramey mein kaee alag-alag pramaan hain, joe sabhi kissy naa kissy tarah seey pasand key swayamsiddh parr nirbhar karate hain. isake anuprayogon mein chaar-rung pramey aur dialworth kii pramey koo seemit graph seey vistaarit karna aur aanshik roop seey sett koo anant taka seemit karna aur samtal kii rangeen sankhya parr headwiger-nelson samasya koo seemit graph key baare mein ack samasya mein cumm karna shamil haye. ise rangon kii seemit sankhya seey laker rangon key sett taka saamaanyikrit kiya jaa sakata haye jinaki cardinality ack majboot compact cardinal haye.
paribhaashaaen aur kathan.
ack dishaheen graph ack ganitiya vastu haye jisamen sheershon kaa ack samooh aur kinaaron kaa ack samooh hotaa haye joe sheershon key jode koo jodata haye. pratyek kinare seey judey dou sheershon koo isake antim bindu kahaa jaataa haye. graph seemit hotaa haye jaba isake sheersh aur kinare seemit sett banaate hain, aur anyatha anant. ack graph rung pratyek sheersh koo rangon key ack samooh seey kheenche gaye rung key saath iss tarah seey jodata haye kii pratyek kinare key antim binduon parr dou alag-alag rung hotey hain. graph rung mein ack baar-baar lakshya upayog kiye jaane vaale rangon kii kull sankhya koo cumm karna haye; graph kii rangeen sankhya rangon kii yeh nyuntam sankhya haye. chaar-rung pramey bataata haye kii pratyek seemit graph jise euclidean tala mein paar kiye binaa kheencha jaa sakata haye, usey adhikatam chaar rangon kii aavashyakta hoti haye; haalaanki, adhik jatil sampark vaale kuchh graphon koo chaar seey adhik rangon kii aavashyakta hoti haye. yeh pasand key swayamsiddh kaa ack parinam haye kii varna sankhya anant graph key liye achchi tarah seey paribhaashit haye, lekin inn graph key liye varna sankhya apane aap mein ack anant cardinal sankhya hoe sakati haye.
ack graph kaa upa-graph ack aur graph haye joe isake sheershon key upa-samooh aur isake kinaaron key upa-samooh seey praapt kiya jaataa haye. yadi badaa graph rangeen haye, tou usee rung kaa upayog upgraph key liye kiya jaa sakata haye. isaliye, ack upgraph kii rangeen sankhya poore graph kii rangeen sankhya seey badee naheen hoe sakati haye. dee brune-erdos pramey anant graph kii rangeen sankhyaon seey sambandhit haye, aur yeh darshaata haye kii (phir seey, pasand key swayamsiddh koo maanate hue) unaki ganana unake seemit upgraph kii rangeen sankhyaon seey kii jaa sakati haye. yeh bataata haye kii, yadi ack graph sootra _ 2 key parimit upgraph kii rangeen sankhya kaa ack seemit adhikatam moolya sootra _ 1 haye, tou sootra _ 2 kii rangeen sankhya hii bilkul sootra _ 1 haye. doosari or, yadi sootra _ 2 key seemit upgraph kii rangeen sankhya parr koee seemit oopari seema naheen haye, tou sootra _ 2 kii rangeen sankhya hii anant honey chaahiye.
anuprayog.
iss samasya kaa adhyayan karane mein erdos kii mool prerana parimit seey anant graph taka vistaar karna thaa, yeh pramey kii jaba bhee kissy graph mein seemit adhikatam out-degree sootra _ 8 key saath ack abhivinyas hotaa haye, tou iska ack sootra _ 9-rung bhee hotaa haye. seemit graph key liye yeh iss prakaar haye kyonki aise graph mein hamesha adhikatam sootra _ 10 parr degree kaa sheersh hotaa haye, jise sabhi shesh sheershon key punaraavarti roop seey rangeen honey key baad sootra _ 11 rangon mein seey ack key saath rangaa jaa sakata haye. iss tarah key abhivinyas key saath anant graph mein hamesha nimn-degree sheersh naheen hotaa haye (udaaharan key liye, jaali mein sootra _ 12 hotaa haye lekin manmaane dhang seey badee nyuntam degree hoti haye), isaliye iss tark key liye graph koo seemit honey kii aavashyakta hoti haye. lekin dee brune-erdos pramey seey pataa chalata haye kii anant graph key liye bhee ack sootra _ 9-rung maujood haye.
dee bruyson-erdos pramey kaa ack aur anuprayog headwigger-nelson samasya key liye haye, joe poochata haye kii euclidean tala key binduon koo rangane key liye kitane rangon kii aavashyakta hoti haye taaki pratyek dou bindu joe ack ikai doori parr hain, unake alag-alag rung houn. yeh ack anant graph key liye ack graph rung samasya haye jisamen samtal key pratyek bindu key liye ack sheersh hotaa haye aur pratyek dou binduon key liye ack kinara hotaa haye jinaki euclidean doori bilkul ack hoti haye. iss graph key prerit upa-graph koo ikai doori graph kahaa jaataa haye. saat-vertex ikai doori graph, moser spindle, key liye chaar rangon kii aavashyakta hoti haye; 2018 mein, bahut badey ikai doori graph paae gaye they jinamen paanch rangon kii aavashyakta hoti haye. poore anant graph mein samtal key shatkon tiling key aadhar parr saat rangon key saath ack gyaat rung haye. isaliye, tala kii rangeen sankhya yaa tou 5,6, yaa 7 honey chaahiye, lekin yeh gyaat naheen haye kii inn teen sankhyaon mein seey kaun saa sahee moolya haye. dee brune-erdos pramey seey pataa chalata haye kii, iss samasya key liye, poore tala key samaan rangeen sankhya key saath ack seemit ikai doori graph maujood haye, isaliye yadi rangeen sankhya paanch seey adhik haye tou iss tathya koo ack seemit ganana dwara saabit kiya jaa sakata haye.
dee brune-erdos pramey kaa upayog dialworth kii pramey koo seemit seey anant aanshik roop seey krambaddh sett taka badhaane key liye bhee kiya jaa sakata haye. dilworth kii pramey bataati haye kii ack aanshik crum kii chaudaai (parasparik roop seey atulaniya tatvon key ack samooh mein tatvon kii adhikatam sankhya) shrinkhalaon kii nyuntam sankhya (poori tarah seey krambaddh upasamuchchay) key barabar haye jisamen aanshik crum koo vibhajit kiya jaa sakata haye. janjeeron mein vibhajan koo aanshik crum key atulaniyata graph key rung key roop mein vyakhya kii jaa sakati haye. yeh crum key pratyek tatva key liye ack sheersh key saath ack graph haye aur atulaniya tatvon kii pratyek jodee key liye ack kinara haye. iss rung vyakhya kaa upayog karate hue, seemit aanshik roop seey krambaddh seton key liye dialworth kii pramey key ack alag pramaan key saath, yeh saabit karna sambhav haye kii ack anant aanshik roop seey krambaddh sett mein parimit chaudaai sootra _ 14 haye yadi aur kewal tabhi jaba iska sootra _ 14 shrinkhalaon mein vibhajan hoe.
isi tarah, dee brune-erdos pramey chaar rangon kii pramey koo seemit samtaliya graph seey anant samtaliya graph taka vistaarit kartaa haye. pratyek seemit samtal graph koo chaar rangon key pramey dwara chaar rangon key saath rangeen kiya jaa sakata haye. dee brune-erdos pramey taba dikhaata haye kii
pratyek graph jise samtal mein paar kiye binaa kheencha jaa sakata haye, seemit yaa anant, chaar rangon key saath rangeen hoe sakata haye. adhik aam taur parr, pratyek anant graph jisake liye sabhi seemit upgraph samtal hain, phir seey chaar rung kaa hoe sakata haye.
pramaan.
dee brune-erdos pramey kaa mool pramaan, dee brune dwara, transfinite induction kaa upayog kiya gayaa.
 topology mein tyconoff kii saghanata pramey key aadhar parr nimnalikhit bahut hii sankshipt pramaan pradaan kiya gayaa. maan leejiye kii diye gaye anant graph sootra _ 2 key liye, pratyek parimit upgraph sootra _ 8-rangeen haye, aur sootra _ 18 koo sootra _ 2 key sheershon key liye sootra _ 8 rangon key sabhi assignment kaa sthaan honey dein (chaahe way ack vaidh rung banaate houn). phir sootra _ 18 koo utpaad sthaan sootra _ 22 key roop mein ack topology dee jaa sakati haye, jahan sootra _ 23 graph key sheershon key sett koo darshaata haye. tyconoff kii pramey key anusaar yeh sthalvaigyaanik sthaan saghan haye. sootra _ 2 key pratyek parimit upgraph sootra _ 24 key liye, sootra _ 26 koo sootra _ 18 kaa upasamuchchay honey dein jisamen rangon key assignment shamil hain joe vaidh roop seey rung sootra _ 24 hain. phir sett sootra _ 26 kii pranali seemit pratichhedan sampatti key saath bund seton kaa ack parivaar haye, isaliye saghanata seey iska ack gair-khaali pratichhedan haye. iss pratichhedan kaa pratyek sadasya sootra _ 2 kaa ack vaidh rung haye.
zorn key lemma kaa upayog karke ack alag pramaan lajos posa dwara diyaa gayaa thaa, aur 1951 ph mein bhee.dee. gabriel andru derack kaa thesis. yadi sootra _ 2 ack anant graph haye jisamen pratyek parimit upgraph sootra _ 8-rangeen haye, tou zorn key lemma dwara yeh ack hii guna key saath ack adhikatam graph sootra _ 33 kaa upgraph haye (jisamen kuchh seemit upgraph koo sootra _ 8 rangon seey adhik kii aavashyakta key binaa koee adhik kinare naheen jode jaa sakate hain). sootra _ 33 mein gair-samatulyata kaa dwiaadhaari sambandh ack samatulyata sambandh haye, aur isake samatulyata varg sootra _ 2 kaa sootra _ 8-rung pradaan karate hain. haalaanki, iss pramaan koo sankshiptata pramaan kii tulanaa mein samanya banaana adhik kathin haye.
pramey koo ultrafilter yaa gair-maanak vishleshan kaa upayog karke bhee saabit kiya jaa sakata haye. kennig key anant lemma key aadhar parr sheershon kii ack ganana yogya sankhya key saath graph key liye ack pramaan detaa haye.
pasand parr nirbharta.
dee brune-erdos pramey key sabhi pramaan pasand key swayamsiddh key kissy naa kissy roop kaa upayog karate hain. iss dhaarana kaa kuchh roop aavashyak haye, kyonki ganit key aise model maujood hain jinamen pasand kaa swayamsiddh siddhant aur dee brune-erdos pramey donon galat hain. adhik sateek roop seey, yeh dikhaaya gayaa kii pramey booliyan prime ideal theoram kaa ack parinam haye, ack aisee sampatti joe pasand key swayamsiddh dwara nihit haye lekin pasand key poorna swayamsiddh seey kamjor haye, aur yeh dikhaaya kii dee brune-erdos theoram aur booliyan prime ideal theoram swayamsiddh shakti mein samkaksh hain. 
ganana yogya graph key liye dee brune-erdos pramey koo swayamsiddh shakti mein, dusare crum key ankganit key ack nishchit siddhant key bheetar, kamjor kanig key lemma key barabar bhee dikhaaya jaa sakata haye.
binaa kissy vikalp key sett siddhant key model mein pramey key prati-udaaharan key liye, sootra _ 2 koo ack anant graph honey dein jisamen sheersh sabhi sambhaavit vaastavik sankhyaon kaa pratinidhitva karate hain. sootra _ 2 mein, pratyek dou vaastavik sankhyaon sootra _ 40 aur sootra _ 41 koo ack kinare seey jodein jaba bhee moolya sootra _ 42 mein seey ack ack parimeya sankhya hoe. samatulya roop seey, iss graph mein, sabhi vaastavik sankhya sootra 40 aur formula 44 kii sabhi vaastavik sankhyaon key beach, parimeya sankhya sootra 45 key liye kinare maujood hain. iss graph mein pratyek path, kissy bhee vaastavik sankhya sootra 40 seey shuru hotaa haye,
ack parimeya sankhya dwara sootra _ 40 seey bhinn sankhyaaen aur sootra _ 48 key summ gunak key beach baari-baari seey
aur way sankhyaaen joe sootra _ 40 seey ack parimeya sankhya dwara bhinn hoti hain aur sootra _ 48 kaa ack visham gunak.
yeh parivartan sootra _ 2 koo visham lambai key kissy bhee chakr koo dhaaran karane seey rokta haye, isaliye isake pratyek seemit upgraph
kewal dou rangon kii aavashyakta hoti haye. haalaanki, soloway model mein jisamen vaastavik sankhyaon kaa pratyek sett maapane yogya haye, sootra _ 2 key liye anant roop seey kaee rangon kii aavashyakta hoti haye, kyonki iss mamle mein pratyek rung varg koo maapane yogya sett honah chaahiye aur yeh dikhaaya jaa sakata haye kii sootra _ 2 mein koee kinare naheen honey vaali vaastavik sankhyaon key pratyek maapane yogya sett mein shoonya honah chaahiye. isaliye, soloway model mein, sabhi sootra _ 2 kii (anant) varna sankhya isake parimit upgraph (adhikatam dou) kii varna sankhya seey bahut badee haye.
saamaanyikaran.
 nimnalikhit pramey koo saabit kartaa haye, jise dee brune-erdos pramey key saamaanyikaran key roop mein dekhaa jaa sakata haye. sootra _ 55 koo ack anant samooh honey dein, udaaharan key liye ack anant graph mein sheershon kaa samooh. sootra 55 key pratyek tatva sootra _ 56 key liye, sootra _ 58 koo rangon kaa ack seemit samooh honey dein. isake alawa, sootra _ 55 key pratyek parimit upasamuchchay sootra _ 59 key liye, sootra _ 59 kaa kuchh vishesh rung sootra _ 61 chunein, jisamen sootra _ 59 key pratyek tatva sootra _ 56 kaa rung sootra _ 58 seey sambandhit haye. phir iss guna key saath kii pratyek seemit sett sootra _ 59 kaa ack parimit superset sootra _ 69 haye, jisamen sootra _ 66 aur sootra _ 71 sahmat hain. vishesh roop seey, yadi humm ack anant graph sootra _ 2 key pratyek parimit upgraph key liye ack sootra _ 8-rung chunate hain, tou sootra _ 2 kaa ack sootra _ 8-rung haye jisamen pratyek seemit graph mein ack badaa supergraph hotaa haye jiska rung poore graph key rung seey sahmat hotaa haye.
yadi kissy graph mein seemit varna sankhya naheen haye, tou dee brune-erdos pramey kaa tatparya haye kii isamen pratyek sambhaavit seemit varna sankhya key seemit upgraph honey chaahiye. shodhkartaon ney upgraph parr anya sthitiyon kii bhee jaanch kii haye joe iss mamle mein honey key liye majboor hain. udaaharan key liye, aseemit rangeen graph mein ack upgraph key roop mein harr sambhav seemit dvidaliya graph bhee honah chaahiye. haalaanki, unake paas manmaane dhang seey badaa visham gher hoe sakata haye, aur isaliye way gair-dvidaliya upgraph key kissy bhee seemit sett seey butch sakate hain.
dee brune-erdos pramey seedhe hypergraph rung samasyaon parr bhee lagu hotaa haye, jahaan pratyek hyperase key ack seey adhik rangon key sheersh honey kii aavashyakta hoti haye. graph key liye, ack hypergraph kaa ack sootra _ 8-rung haye yadi aur kewal tabhi jaba isake pratyek seemit upa-hypergraph kaa ack sootra _ 8-rung haye. yeh curt godel key saghanata pramey kaa ack vishesh mamla haye, jisamen kahaa gayaa haye kii pratham-crum vaakyon key ack samooh mein ack model hotaa haye yadi aur kewal tabhi jaba isake pratyek parimit subset mein ack model hotaa haye. vishesh roop seey, dee brune-erdos pramey koo pratham-crum sanrachanaon kii saghanata key roop mein vyakhya kii jaa sakati haye jinake gair-taarkik moolya rangon kaa koee bhee seemit samooh hain aur jinka inn moolyon parr kewal ack hii anuman asamaanta haye.
pramey koo una sthitiyon key liye bhee saamaanyikrit kiya jaa sakata haye jinamen rangon kii sankhya ack anant cardinal sankhya haye. yadi sootra 78 ack majboot compact cardinal haye, tou pratyek graph sootra 2 aur cardinal sankhya sootra 80 key liye, sootra 2 mein adhikansh sootra 82 parr varna sankhya hoti haye yadi aur kewal yadi sootra 78 seey cumm cardinality key pratyek upgraph mein adhikansh sootra 82 parr chromatic sankhya hoti haye. mool dee brune-erdos pramey iss saamaanyikaran kaa cases sootra 85 haye, kyonki ack sett seemit haye yadi aur kewal yadi isaki cardinality sootra 86 seey cumm haye. haalaanki, kuchh dhaarana jaise kii ack majboot compact cardinal honey kii dhaarana aavashyak haih yadi pratyek anant cardinal sootra 80 key liye, tou cardinality sootra kaa ack graph 2 maujood haye, jaise kii sootra 78 key pratyek upgraph mein adhikansh sootra 82 parr chromatic sankhya haye.

