Vés al contingut

Teorema de De Bruijn–Erdős (teoria de grafs): diferència entre les revisions

De la Viquipèdia, l'enciclopèdia lliure
Contingut suprimit Contingut afegit
m Bot elimina paràmetre innecessari des del 2020.
m Ampliació d'article
Línia 1: Línia 1:
En [[teoria de grafs]], el '''teorema de De Bruijn-Erdős''', demostrat per [[Nicolaas de Bruijn|Nicolaas Govert de Bruijn]] i [[Paul Erdős]] el 1951,{{sfn|de Bruijn|Erdős|1951}} estableix que, per a cada [[graf infinit]] ''G'' i enter finit ''k'', es pot [[coloració de grafs|acolorir]] ''G'' amb ''k'' colors (de manera que cap parell de vèrtexs adjacents tingui el mateix color) si i només si tots els seus subgrafs finits es poden acolorir amb ''k'' colors. És a dir, cada [[graf crític|graf ''k''-crític]] (és a dir, cada graf que requereix ''k'' colors però per al qual tots els subgrafs requereixen un nombre menor de colors) ha de tenir un nombre finit de vèrtexs.
En [[teoria de grafs]], el '''teorema de De Bruijn–Erdős''' relaciona la [[coloració de grafs]] d'un [[Graf (matemàtiques)|graf]] infinit amb el mateix problema dels seus subgrafs finits. Afirma que, quan es poden acolorir tots els subgrafs finits amb <math>c</math> colors, el mateix passa amb tot el graf. El teorema va ser demostrat per [[Nicolaas de Bruijn]] i [[Paul Erdős]] (1951),{{sfn|De Bruijn|Erdős|1951}} dels quals rep el nom.

El teorema de De Bruijn–Erdős té diverses demostracions diferents, totes depenent d'alguna manera de l'[[axioma de l'elecció]]. Les seves aplicacions inclouen estendre el [[teorema dels quatre colors]] i el [[teorema de Dilworth]] de grafs finits i [[Conjunt parcialment ordenat|conjunts parcialment ordenats]] a infinits, i reduir el [[Problema de Hadwiger–Nelson|problema de Hadwiger-Nelson]] sobre el [[Coloració de grafs|nombre cromàtic]] del [[Graf pla|pla]] a un problema sobre gràfics finits. Es pot generalitzar des de nombres finits de colors fins a conjunts de colors la [[cardinalitat]] dels quals és un [[cardinal fortament compacte]].

== Definicions i enunciat ==
Un [[graf no dirigit]] és un [[objecte matemàtic]] format per un conjunt de [[Vèrtex (teoria de grafs)|vèrtexs]] i un conjunt d'[[Aresta (teoria de grafs)|arestes]] que enllacen parells de vèrtexs. Els dos vèrtexs associats a cada aresta s'anomenen ''«extrems»''. El graf és finit quan els seus vèrtexs i arestes formen [[Conjunt finit|conjunts finits]], i infinits en cas contrari. Una [[coloració de grafs]] associa cada vèrtex amb un [[color]] extret d'un conjunt de colors, de manera que cada aresta té dos colors diferents als seus extrems. Un objectiu freqüent en la coloració de gràfics és minimitzar el nombre total de colors que s'utilitzen; el ''«nombre cromàtic»'' d'un graf és aquest nombre mínim de colors.<ref group="Nota">Per a aquestes definicions bàsiques, vegeu [Jensen, Toft 1995, p. 1-2]</ref> El [[teorema dels quatre colors]] estableix que cada graf finit que es pot dibuixar sense encreuaments en el [[Geometria euclidiana|pla euclidià]] necessita com a màxim quatre colors; tanmateix, alguns grafs amb connectivitat més complicada requereixen més de quatre colors.{{sfn|Jensen|Toft|1995|p=5}} És una conseqüència de l'[[axioma de l'elecció]] que el nombre cromàtic està [[ben definit]] per a grafs infinits, però per a aquests grafs el nombre cromàtic podria ser en si mateix un [[nombre cardinal]] infinit.{{sfn|Komjáth|2011}}

Un subgraf d'un graf és un altre graf obtingut a partir d'un [[subconjunt]] dels seus vèrtexs i d'un subconjunt de les seves arestes. Si el graf més gran està acolorit, es pot utilitzar el mateix color per al subgraf. Per tant, el nombre cromàtic d'un subgraf no pot ser més gran que el nombre cromàtic de tot el graf. El teorema de De Bruijn-Erdős es refereix als nombres cromàtics de grafs infinits, i mostra que (de nou, assumint l'[[axioma de l'elecció]]) es poden calcular a partir dels nombres cromàtics dels seus subgrafs finits. Afirma que, si els nombres cromàtics dels subgrafs finits d'un graf <math>G</math> tenen un valor màxim finit <math>c</math>, el nombre cromàtic de <math>G</math> és exactament <math>c</math>. D'altra banda, si no hi ha cap [[Fita superior|límit superior]] finit en els nombres cromàtics dels subgrafs finits de <math>G</math>, el nombre cromàtic de <math>G</math> ha de ser [[infinit]].{{sfn|Jensen|Toft|1995|p=2 (teorema 1)}}

== Aplicacions ==
La motivació original d'Erdős a l'hora d'estudiar aquest problema va ser estendre dels grafs finits a infinits el teorema que, sempre que un graf tingui una [[Orientació (teoria de grafs)|orientació]] amb un grau <math>k</math> superior finit, també té una <math>(2k+1)</math>-[[Coloració de grafs|coloració]]. Per als grafs finits això succeeix perquè aquests grafs sempre tenen un [[Vèrtex (teoria de grafs)|vèrtex]] de grau <math>2k</math> com a màxim, que es pot acolorir amb un de <math>2k+1</math> colors després que tots els vèrtexs restants s'acoloreixin de manera [[Recursivitat|recursiva]]. Els grafs infinits amb aquesta orientació no sempre tenen un vèrtex de baix grau (per exemple, les [[Xarxa de Bethe|xarxes de Bethe]] tenen <math>k=1</math>, però un grau mínim arbitràriament gran), de manera que aquest argument requereix que el graf sigui finit. Però el teorema de De Bruijn-Erdős mostra que existeix una <math>(2k+1)</math>-coloració fins i tot per a grafs infinits.<ref group="Nota">[Erdős 1950], en particular a la pàgina 137, on el teorema de De Bruijn-Erdős s'anuncia per primera vegada (però no demostrat) amb una pista que el [[lema de Kőnig]] es pot utilitzar per a grafs comptables.</ref>

[[Fitxer:Hadwiger-Nelson.svg|miniatura|Un [[Graf pla|pla]] de set colors i el [[graf de Moser]] de quatre cromàtics dibuixats com a graf de distància unitat en el pla, proporcionant límits superiors i inferiors per al [[Problema de Hadwiger–Nelson|problema de Hadwiger-Nelson]]]]
Una altra aplicació del teorema de De Bruijn-Erdős és al [[Problema de Hadwiger–Nelson|problema de Hadwiger-Nelson]], que pregunta quants colors es necessiten per acolorir els punts del [[Geometria euclidiana|pla euclidià]] de manera que cada dos punts que es troben a una distància unitat tinguin colors diferents. Aquest és un problema de [[coloració de grafs]] per a un graf infinit que té un [[Vèrtex (teoria de grafs)|vèrtex]] per a cada punt del pla i una [[Aresta (teoria de grafs)|aresta]] per cada dos punts la [[distància euclidiana]] dels quals és exactament una. Els subgrafs d'aquest grafs s'anomenen ''«[[Graf de distància unitat|grafs de distància unitat]]»''. Un graf de distància unitat de set vèrtex, el [[graf de Moser]], requereix quatre colors; el 2018, es van trobar grafs de distància d'unitats molt més grans que requereixen cinc colors.{{sfn|Lamb|2018}} Tot el graf infinit té una coloració coneguda amb set colors basat en un mosaic hexagonal del pla. Per tant, el nombre cromàtic del pla ha de ser 5, 6 o 7, però no se sap quin d'aquests tres nombres és el valor correcte. El teorema de De Bruijn-Erdős mostra que, per a aquest problema, existeix un graf de distància unitat finita amb el mateix nombre cromàtic que tot el pla, de manera que si el nombre cromàtic és superior a cinc, aquest fet es pot demostrar mitjançant un càlcul finit.{{sfn|Soifer|2008|p=39}}

El teorema de De Bruijn-Erdős també es pot utilitzar per estendre el [[teorema de Dilworth]] de [[Conjunt parcialment ordenat|conjunts parcialment ordenats]] finits a infinits. El teorema de Dilworth estableix que l'amplada d'un ordre parcial (el nombre màxim d'elements en un conjunt d'elements mútuament incomparables) és igual al nombre mínim de cadenes (subconjunts [[Ordre total|totalment ordenats]]) en què es pot dividir l'ordre parcial. Una partició en cadenes es pot interpretar com una coloració del [[Gràfic de comparabilitat|graf d'incomparabilitat]] de l'ordre parcial. Aquest és un graf amb un vèrtex per a cada element de l'ordre i una aresta per a cada parell d'elements incomparables. Utilitzant aquesta interpretació de color, juntament amb una demostració separada del teorema de Dilworth per a conjunts parcialment ordenats finits, és possible demostrar que un conjunt parcialment ordenat infinit té una amplada finita <math>w</math> [[si i només si]] té una partició en <math>w</math> cadenes.{{sfn|Harzheim|2005|p=60 (teorema 5.6)}}

De la mateixa manera, el teorema de De Bruijn-Erdős amplia el [[teorema dels quatre colors]] des de [[Graf pla|grafs planars]] finits fins a grafs planars infinits. Cada graf pla finit es pot pintar amb quatre colors, segons el teorema dels quatre colors. Aleshores, el teorema de De Bruijn-Erdős mostra que cada graf que es pot dibuixar sense encreuaments en el pla, finit o infinit, es pot pintar amb quatre colors. De manera més general, cada graf infinit per al qual tots els subgrafs finits són plans pot tornar a ser de quatre colors.<ref group="Nota">[Nash-Williams 1967] afirma el mateix resultat per al teorema dels cinc colors per als gràfs planars comptables, ja que el teorema dels quatre colors encara no s'havia demostrat quan va publicar la seva investigació, i com que la demostració del teorema de De Bruijn-Erdős que dóna només s'aplica als grafs comptables. Per a la generalització a gràfs en què cada subgraf finit és pla (provat directament mitjançant el teorema de compacitat de Gödel). Vegeu [Rautenberg 2010].</ref>{{sfn|Barnette|1983}}

== Demostracions ==
La demostració original del teorema de De Bruijn-Erdős, de De Bruijn, utilitzava la [[inducció transfinita]].{{sfn|Soifer|2008|p=236}}

[Gottschalk 1951] va proporcionar la següent demostració molt breu, basada en el [[Teorema de Tíkhonov|teorema de compacitat]] de [[Andrei Tíkhonov|Tíkhonov]] en [[topologia]]. Suposem que, per al graf infinit donat <math>G</math>, cada subgraf finit és <math>k</math>-[[Coloració de grafs|colorable]], i fem que <math>X</math> sigui l'espai de totes les tasques dels <math>k</math>-colors als vèrtexs de <math>G</math> (independentment de si formen una coloració vàlida). Aleshores <math>X</math> es pot donar una [[topologia]] com a [[Topologia producte|espai de producte]] <math>k^{V(G)}</math>, on <math>V(G)</math> denota el conjunt de vèrtexs del graf. Segons el teorema de Tychonoff, aquest espai topològic és [[Espai compacte|compacte]]. Per a cada subgraf finit <math>F</math> de <math>G</math>, fem que <math>X_F</math> sigui el subconjunt de <math>X</math> consistent en assignacions de colors que acoloreixin vàlidament <math>F</math>. Llavors, el sistema de conjunts <math>X_F</math> és una família de [[Conjunt tancat|conjunts tancats]] amb la [[propietat de la intersecció finita]], de manera que per compacitat té una intersecció no buida. Cada membre d'aquesta intersecció és un color vàlid de <math>G</math>.<ref group="Nota">Gottschalk afirma la seva demostració de manera més general com una demostració del teorema de [Rado 1949] que generalitza el teorema de De Bruijn–Erdős.</ref>{{sfn|Jensen|Toft|1995}}

Una prova diferent utilitzant el [[lema de Zorn]] va ser donada per [[Lajos Pósa]], i també en la [[tesi doctoral]] [[Philosophiæ doctor|Ph.D]]. de 1951 de [[Gabriel Andrew Dirac]]. Si <math>G</math> és un graf infinit en el qual es troba cada subgraf finit <math>k</math>-colorable, llavors pel lema de Zorn és un subgraf d'un graf [[Maximal i minimal (elements)|màxim]] <math>M</math> amb la mateixa propietat (una a la qual no es poden afegir més arestes sense fer que algun subgraf finit requereixi més de <math>k</math> colors). La [[Relació|relació binària]] de no adjacència en <math>M</math> és una [[relació d'equivalència]] i les seves classes d'equivalència proporcionen una <math>k</math>-coloració de <math>G</math>. Tanmateix, aquesta demostració és més difícil de generalitzar que la prova de compacitat.<ref group="Nota">[Jensen, Toft 1995] atribueixen a [[Gert Sabidussi]] l'observació que la demostració de Gottschalk és més fàcil de generalitzar. [Soifer 2008, pàg. 238-239] dóna la mateixa prova mitjançant el lema de Zorn, redescobert el 2005 per l'estudiant de grau Dmytro Karabash.</ref>{{sfn|Harzheim|2005}}

El teorema també es pot demostrar mitjançant [[Ultrafiltra|ultrafiltres]]{{sfn|Luxemburg|1962}} o [[Anàlisi no estàndard|anàlisis no estàndard]].{{sfn|Hurd|Loeb|1985}}{{sfn|Nash-Williams|1967}} Dóna una demostració per a grafs amb un nombre comptable de vèrtexs basat en el [[Lema de Kőnig|lema de l'infinit de Kőnig]].

== Dependència de l'elecció ==
Totes les demostracions del teorema de De Bruijn-Erdős utilitzen alguna forma de l'[[axioma de l'elecció]]. És necessària alguna forma d'aquesta suposició, ja que existeixen [[Teoria de models|models]] de [[matemàtiques]] en què tant l'axioma de l'elecció com el teorema de De Bruijn-Erdős són falsos. Més precisament, [Mycielski 1961]{{sfn|Mycielski|1961}} va demostrar que el teorema és una conseqüència del [[Teorema de l'ideal primer en àlgebra de Boole|teorema de l'ideal primer booleà]], una propietat que està implicada per l'axioma de l'elecció però més feble que l'axioma complet de l'elecció, i [Läuchli 1971]{{sfn|Läuchli|1971}} va demostrar que el teorema de De Bruijn-Erdős i el teorema de l'ideal primer booleà són equivalents en potència axiomàtica.<ref group="Nota">Per a aquesta història, vegeu [Cowen Hechler Mihók, 2002]. Per a la demostració simplificada del teorema de Läuchli per Mycielski, vegeu [Cowen 1990].</ref>

També es pot demostrar que el teorema de De Bruijn-Erdős per a grafs comptables és equivalent en poder axiomàtic, dins d'una teoria de l'[[Aritmètica de segon ordre|aritmètica de segon ordre,]] al [[Lema de Kőnig|lema de l'infinit de Kőnig]].{{sfn|Schmerl|2000}}

Per a un [[contraexemple]] del teorema en models de [[teoria de conjunts]] sense elecció, fem que <math>G</math> sigui un graf infinit en què els vèrtexs representen tots els [[Nombre real|nombres reals]] possibles. En <math>G</math>, es connecta cada dos nombres reals <math>x</math> i <math>y</math>  per una vora sempre que un dels valors <math>|x-y|\pm\sqrt2</math>  és un [[nombre racional]]. De manera equivalent, en aquest graf existeixen [[Aresta (teoria de grafs)|arestes]] entre tots els nombres reals <math>x</math> i tots els nombres reals de la forma <math>x+q\pm\sqrt2</math>, per a nombres racionals <math>q</math>. Cada [[Camí (teoria de grafs)|camí]] d'aquest graf, començant per qualsevol nombre real <math>x</math>, alterna números que difereixen de <math>x</math> per un nombre racional més un [[múltiple]] parell de <math>\sqrt2</math> i números que difereixen de <math>x</math> per un nombre racional més un múltiple senar de <math>\sqrt2</math>.

Aquesta alternança evita que <math>G</math> contingui qualsevol cicle de longitud senar, de manera que cadascun dels seus subgrafs finits només requereix dos colors. Tanmateix, en el [[model de Solovay]] en què cada conjunt de [[Nombre real|nombres reals]] és [[Mesura de Lebesgue|mesurable per Lebesgue]], <math>G</math> requereix [[Infinit|infinits]] colors, ja que en aquest cas cada classe de color ha de ser un conjunt mesurable i es pot demostrar que cada conjunt mesurable de nombres reals sense arestes en <math>G</math> ha de tenir la mesura zero. Per tant, en el model de Solovay, el nombre cromàtic (infinit) de tots <math>G</math> és molt més gran que el nombre cromàtic dels seus subgrafs finits (com a màxim dos).{{sfn|Shelah|Soifer|2003}}{{sfn|Soifer|2008|p=541-542}}

==Generalitzacions==
[Rado 1949] demostra el següent teorema, que es pot veure com una generalització del teorema de De Bruijn-Erdős. Fem que <math>V</math> siguir un conjunt infinit, per exemple el conjunt de vèrtexs en un gràfic infinit. Per a cada element <math>v</math> de <math>V</math>, fem que <math>c_v</math> sigui un conjunt finit de colors. A més, per a cada subconjunt finit <math>S</math>  de <math>V</math>, s'escull algun color en particular <math>C_S</math> de <math>S</math>, en què el color de cada element <math>v</math> de <math>S</math>  pertany a <math>c_v</math>. Aleshores hi ha una coloració global <math>\chi</math> de tots <math>V</math> amb la propietat que tot conjunt finit <math>S</math> té un superconjunt finit <math>T</math> en la qual <math>\chi</math>  i <math>C_T</math> es consenteixen. En particular, si escollim una <math>k</math>-coloració per a cada subgraf finit d'un graf infinit <math>G</math>, llavors hi ha a <math>k</math>-coloració de <math>G</math> en què cada graf finit té un supergraf més gran la coloració del qual coincideix amb la coloració de tot el graf.<ref group="Nota">Per a aquesta connexió entre el lema de Rado i el teorema de De Bruijn–Erdős vegeu, per exemple, la discussió seguint el teorema A de [Nash-Williams 1967].</ref>

Si un graf no té un nombre cromàtic finit, aleshores el teorema de De Bruijn-Erdős implica que ha de contenir subgrafs finits de tots els nombres cromàtics finits possibles. Els investigadors també han investigat altres condicions sobre els subgrafs que es veuen obligats a produir-se en aquest cas. Per exemple, els grafs cromàtics sense límits també han de contenir tots els possibles [[Graf bipartit|grafs bipartits]] finits com a subgraf. Tanmateix, poden tenir un [[Cintura (teoria de grafs)|cinturó]] imparell arbitràriament gran i, per tant, poden evitar qualsevol conjunt finit de subgrafs no bipartits.{{sfn|Komjáth|2011}}{{sfn|Erdős|Hajnal|1966}}

El teorema de De Bruijn-Erdős també s'aplica directament als problemes de coloració d'[[Hipergraf|hipergrafs]], on es requereix que cada hiperaresta tingui vèrtexs de més d'un color. Pel que fa als grafs, un hipergraf té una <math>k</math>-coloració [[si i només si]] cadascun dels seus subhipergrafs finits té una <math>k</math>-coloració.{{sfn|Soifer|2008|p=239}} És un cas especial del [[teorema de compacitat]] de [[Kurt Gödel]], que afirma que un conjunt de sentències de [[Lògica de primer ordre|primer ordre]] té un model [[si i només si]] cada [[subconjunt]] finit té un [[Teoria de models|model]].{{sfn|Lake|1975|p=171: ''«És senzill demostrar [el teorema de De Bruijn–Erdős] utilitzant el teorema de compacitat per a la lògica de primer ordre»''}} Més concretament, el teorema de De Bruijn-Erdős es pot interpretar com la compacitat de les [[Estructura (lògica metemàtica)|estructures]] de primer ordre els valors no lògics de les quals són qualsevol conjunt finit de colors i l'únic predicat de les quals sobre aquests valors és la [[Desigualtat matemàtica|desigualtat]].{{sfn|Rorabaugh|Tardif|Wehlau|2017}}

El teorema també es pot generalitzar a situacions en què el nombre de colors és un [[nombre cardinal]] infinit. Si <math>\kappa</math> és un [[cardinal fortament compacte]], llavors per a cada graf <math>G</math> i número cardinal <math>\mu<\kappa</math>, <math>G</math>  té un nombre cromàtic com a màxim <math>\mu</math> [[si i només si]] cadascun dels seus subgrafs de cardinalitat és inferior a <math>\kappa</math> té un nombre cromàtic com a màxim <math>\mu</math>.<ref group="Nota">Això es desprèn immediatament de la definició d'un [[Nombre cardinal|cardinal]] fortament compacte
<math>\kappa</math> com a cardinal tal que cada col·lecció de fórmules de [[lògica infinitària]] cada una de longitud inferior a <math>\kappa</math>, que és satisfactori per a cada subcol·lecció de menys de <math>\kappa</math> fórmules, és globalment satisfacible. Vegeu per exemple [Kanamori 2008].</ref> El teorema original de De Bruijn-Erdős és el cas <math>\kappa=\aleph_0</math> d'aquesta generalització, ja que un conjunt és finit [[si i només si]] la seva [[cardinalitat]] és menor que <math>\aleph_0</math>. No obstant això, cal supòsits com el de ser un cardinal fortament compacte: si la [[Hipòtesi del continu|hipòtesi del continu generalitzat]] és certa, aleshores per a cada cardinal infinit <math>\gamma</math>, existeix un graf <math>G</math> de cardinalitat <math>(2^\gamma)^+</math> tal que el nombre cromàtic de <math>G</math> és més gran que <math>\gamma</math>, però de manera que cada subgraf de <math>G</math> el conjunt de vèrtexs del qual té una potència menor que <math>G</math> té un nombre cromàtic com a màxim <math>\gamma</math>.{{sfn|Erdős|Hajnal|1968}}{{sfn|Lake|1975}}

[Lake 1975] caracteritza els grafs infinits que obeeixen a una generalització del teorema de De Bruijn–Erdős, ja que el seu nombre cromàtic és igual al nombre cromàtic màxim dels seus subgrafs estrictament més petits.

== Notes ==
<references group="Nota"/>


== Referències ==
== Referències ==
{{Referències}}
{{referències}}


== Bibliografia ==
== Bibliografia ==
{{Div col|cols=2}}
* {{ref-publicació
* {{ref-llibre | cognom = Barnette| nom = David| isbn = 978-0-88385-309-2| pàgina = 160 | editorial = Mathematical Association of America| col·lecció = Dolciani Mathematical Expositions| títol = Map Coloring, Polyhedra, and the Four-Color Problem| volum = 8| any = 1983 |llengua=anglès}}
| cognom = de Bruijn | nom = Nicolaas Govert | enllaçautor = Nicolaas Govert de Bruijn
* {{ref-publicació | cognom = Cowen | nom = Robert H| doi = 10.1305/ndjfl/1093635418| publicació = Notre Dame Journal of Formal Logic | mr = 1058424| pàgina = 232-240| article= Two hypergraph theorems equivalent to BPI| volum = 31(2) | any = 1990 |llengua=anglès }}
| cognom2 = Erdős | nom2 = Paul | enllaçautor2 = Paul Erdős
* {{ref-publicació| cognom = Cowen | nom = Robert| cognom2 = Hechler | nom2 = Stephen H| cognom3 = Mihók | nom3 = Peter| citeseerx = 10.1.1.23.1521 | publicació = Scientiae Mathematicae Japonicae| mr = 1922784 | pàgina = 213-223| article = Graph coloring compactness theorems equivalent to BPI| volum = 56(2) |llengua=anglès | any = 2002}}
| títol = A colour problem for infinite graphs and a problem in the theory of relations
* {{ref-publicació| cognom = De Bruijn| nom = N. G| enllaçautor = Nicolaas Govert de Bruijn| cognom2 = Erdős | nom2 = P | enllaçautor2 = Paul Erdős | article = A colour problem for infinite graphs and a problem in the theory of relations| publicació = Indagationes Mathematicae. Nederl. Akad. Wetensch. Proc. Ser. A| volum = 54| pàgina = 371-373| any = 1951| mr = 0046630| url = https://web.archive.org/web/20160310003706/http://www.math-inst.hu/~p_erdos/1951-01.pdf | format={{PDF}}| doi = 10.1016/S1385-7258(51)50053-7 |llengua=anglès}}
| publicació = [[Indagationes Mathematicae|Nederl. Akad. Wetensch. Proc. Ser. A]]
* {{ref-publicació | cognom = Erdős | nom = Paul| enllaçautor = Paul Erdős | doi = 10.2307/2031913 | publicació = Proceedings of the American Mathematical Society | mr = 0035809| pàgina = 127-141 | article = Some remarks on set theory| url = https://users.renyi.hu/~p_erdos/1950-13.pdf | volum = 1(2) |format={{PDF}} | any = 1950| jstor = 2031913 |llengua=anglès}}
| volum = 54
* {{ref-publicació | cognom = Erdős | nom = Paul | cognom2 = Hajnal | nom2 = András | enllaçautor2= András Hajnal | doi = 10.1007/BF02020444 | publicació = Acta Mathematica Academiae Scientiarum Hungaricae | mr = 0193025 | pàgina = 61-99 | article = On chromatic number of graphs and set-systems | url = http://www.renyi.hu/~p_erdos/1966-07.pdf | volum = 17(1)-17(2) |format={{PDF}}| any = 1966| s2cid = 189780485 |llengua=anglès}}
| pàgines = 371–373
* {{ref-publicació | cognom=Erdős |nom=Paul |nom2=András |cognom2=Hajnal |lloc = Nova York | mr = 0263693 | pàgina = 83-98 | any = 1968| editorial = [[Academic Press]] | publicació= Theory of Graphs Proc. Colloq. |lloc=Tihany |article= On chromatic number of infinite graphs | url = http://www.renyi.hu/~p_erdos/1968-04.pdf |format={{PDF}} |llengua=anglès }}
| url = http://www.math-inst.hu/~p_erdos/1951-01.pdf
* {{ref-publicació | cognom = Gottschalk | nom = W. H | enllaçautor = Walter Gottschalk | publicació = Proceedings of the American Mathematical Society | mr = 0040376 | pàgina = 172 | article= Choice functions and Tychonoff's theorem | volum = 2(1) | any = 1951 | doi=10.2307/2032641| jstor = 2032641 |llengua=anglès}}
| any = 1951
* {{ref-llibre | cognom = Harzheim | nom = Egbert | isbn = 978-0-387-24219-8 | lloc = Nova York | mr = 2127991 | pàgina = 59 (teorema 5.5) | editorial = [[Springer Science+Business Media|Springer]] | col·lecció = Advances in Mathematics | títol = Ordered sets | volum = 7 | any = 2005 |llengua=anglès}}
}}.
* {{ref-llibre | cognom = Hurd | nom = Albert E | cognom2 = Loeb | nom2 = Peter A | enllaçautor2= Peter A. Loeb | pàgina = 92 (teorema 5.14) | isbn = 978-0-12-362440-1 | lloc = Orlando, FL | mr = 806135 | editorial = Academic Press | col·lecció = Pure and Applied Mathematics | títol = An introduction to nonstandard real analysis | volum = 118 | any = 1985 |llengua=anglès}}

* {{ref-llibre | cognom = Jensen | nom = Tommy R | cognom2 = Toft | nom2 = Bjarne | isbn = 978-0-471-02865-7 | lloc = Nova York | mr = 1304254 | pàgina = 2-3 (teorema 1) | editorial = John Wiley & Sons Inc | col·lecció = Wiley-Interscience Series in Discrete Mathematics and Optimization | títol = Graph coloring problems| any = 1995 |llengua=anglès}}
{{Esborrany de matemàtiques}}
* {{ref-llibre |títol=The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings |col·lecció=Springer Monographs in Mathematics |nom=Akihiro |cognom=Kanamori |enllaçautor=Akihiro Kanamori |editorial=Springer-Verlag|year=2008 |isbn=978-3-540-88866-6 |pàgina= 37 |llengua=anglès}}
* {{ref-publicació | enllaçautor = Péter Komjáth | cognom = Komjáth | nom = Péter | doi = 10.1016/j.disc.2010.11.004 | publicació = Discrete Mathematics | pàgina = 1448-1450 | article = The chromatic number of infinite graphs. A survey | url = http://matmod.elte.hu/~kope/offp50.pdf | volum = 311(15) |format={{PDF}} | any = 2011|llengua=anglès}}
* {{ref-publicació| cognom = Lake | nom = John | publicació = [[Journal of Combinatorial Theory]] | col·lecció = Series B| mr = 0360335| pàgina = 170-174| article= A generalization of a theorem of de Bruijn and Erdős on the chromatic number of infinite graphs| volum = 18(2) | any = 1975| doi=10.1016/0095-8956(75)90044-1|llengua=anglès}}
* {{ref-publicació| cognom = Lamb | nom = Evelyn| data = 17 d'abril de 2018| publicació = [[Quanta Magazine]]| article = Decades-old graph problem yields to amateur mathematician| url = https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/ |llengua=anglès}}
* {{ref-publicació | cognom = Läuchli | nom = H| doi = 10.1007/BF02771458 | doi-access = free| publicació = Israel Journal of Mathematics | mr = 0288051 | pàgina = 422-429 | article = Coloring infinite graphs and the Boolean prime ideal theorem| volum = 9(4)| any = 1971 |llengua=anglès}}
* {{ref-publicació | cognom = Luxemburg | nom = W. A. J | enllaçautor = Wilhelmus Luxemburg| publicació = [[Indagationes Mathematicae]]| mr = 0140435| pàgina = 343-345 | article= A remark on a paper by N. G. de Bruijn and P. Erdős| volum = 24| any = 1962| doi = 10.1016/S1385-7258(62)50033-4 |llengua=anglès}}
* {{ref-publicació| cognom = Mycielski | nom = Jan | enllaçautor = Jan Mycielski| doi = 10.1007/BF02066677| publicació = Acta Mathematica Academiae Scientiarum Hungaricae| mr = 0130686| pàgina = 125-129 | article = Some remarks and problems on the colouring of infinite graphs and the theorem of Kuratowski| volum = 12(1)-12(2) | any = 1961| s2cid = 120141460 |llengua=anglès}}
* {{ref-publicació| cognom = Nash-Williams | nom = C. St. J. A | enllaçautor= Crispin Nash-Williams| publicació = [[Journal of Combinatorial Theory]]| mr = 0214501| pàgina = 286-301| article = Infinite graphs. Asurvey| volum = 3(3) | any = 1967| doi=10.1016/s0021-9800(67)80077-2|llengua=anglès}}
* {{ref-publicació| cognom = Rado | nom = R | enllaçautor= Richard Rado| publicació = Canadian Journal of Mathematics| pàgina = 337-343| article = Axiomatic treatment of rank in infinite sets| volum = 1(4)| any = 1949| doi=10.4153/cjm-1949-031-1| s2cid = 124598982 |llengua=anglès}}
* {{ref-llibre | cognom = Rautenberg | nom = Wolfgang | enllaçautor = Wolfgang Rautenberg | isbn = 978-1-4419-1220-6 | pàgina = 32 | editorial = [[Springer Science+Business Media|Springer-Verlag]] | col·lecció = Universitext | títol = A Concise Introduction to Mathematical Logic| any = 2010| doi = 10.1007/978-1-4419-1221-3 |llengua=anglès}}
* {{ref-publicació | cognom = Rorabaugh | nom = Danny | cognom2 = Tardif | nom2 = Claude | cognom3 = Wehlau | nom3 = David| arxiv = 1609.05221 | doi = 10.23638/LMCS-13(1:1)2017| publicació = [[Logical Methods in Computer Science]]| mr = 3607036 | pàgina = 1:1-1:11| article = Logical compactness and constraint satisfaction problems| volum = 13(1)| any = 2017| s2cid = 31135533 |llengua=anglès}}
* {{ref-publicació | cognom = Schmerl | nom = James H | doi = 10.1002/1521-3870(200010)46:4<543::AID-MALQ543>3.0.CO;2-E | publicació = Mathematical Logic Quarterly| mr = 1791549 | pàgina = 543-548 | títol = Graph coloring and reverse mathematics | volum = 46(4) | any = 2000 |llengua=anglès}}
* {{ref-publicació | cognom = Shelah | nom = Saharon | enllaçautor= Saharon Shelah | cognom2 = Soifer | nom2 = Alexander | enllaçautor= Alexander Soifer | doi = 10.1016/S0097-3165(03)00102-X | publicació = [[Journal of Combinatorial Theory]] | col·lecció = Series A | mr = 1996076 | pàgina = 387-391 | títol = Axiom of choice and chromatic number of the plane| volum = 103(2) | any = 2003 |llengua=anglès }}
* {{ref-llibre | cognom = Soifer | nom = Alexander | enllaçautor = Alexander Soifer | isbn = 978-0-387-74640-1 | lloc = Nova York York | editorial = [[Springer Science+Business Media|Springer]] | títol = The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators | any = 2008 |llengua=anglès |p=cap. II.5 "De Bruin–Erdős reduction to finite sets and results near the lower bound", p. 39-42; cap. V.26 "De Bruin–Erdős's theorem and its history", p. 236–241}}
{{Div col end}}


{{autoritat}}
{{ORDENA:Teorema De De Bruijnerdos Teoria De Grafs}}
{{ORDENA:De Bruijn-Erdos, Teorema de}}
[[Categoria:Teoremes de teoria de grafs|De Bruijn–Erdős]]
[[Categoria:Teoremes de teoria de grafs|De Bruijn–Erdős]]

Revisió del 17:58, 1 gen 2024

En teoria de grafs, el teorema de De Bruijn–Erdős relaciona la coloració de grafs d'un graf infinit amb el mateix problema dels seus subgrafs finits. Afirma que, quan es poden acolorir tots els subgrafs finits amb  colors, el mateix passa amb tot el graf. El teorema va ser demostrat per Nicolaas de Bruijn i Paul Erdős (1951),[1] dels quals rep el nom.

El teorema de De Bruijn–Erdős té diverses demostracions diferents, totes depenent d'alguna manera de l'axioma de l'elecció. Les seves aplicacions inclouen estendre el teorema dels quatre colors i el teorema de Dilworth de grafs finits i conjunts parcialment ordenats a infinits, i reduir el problema de Hadwiger-Nelson sobre el nombre cromàtic del pla a un problema sobre gràfics finits. Es pot generalitzar des de nombres finits de colors fins a conjunts de colors la cardinalitat dels quals és un cardinal fortament compacte.

Definicions i enunciat

Un graf no dirigit és un objecte matemàtic format per un conjunt de vèrtexs i un conjunt d'arestes que enllacen parells de vèrtexs. Els dos vèrtexs associats a cada aresta s'anomenen «extrems». El graf és finit quan els seus vèrtexs i arestes formen conjunts finits, i infinits en cas contrari. Una coloració de grafs associa cada vèrtex amb un color extret d'un conjunt de colors, de manera que cada aresta té dos colors diferents als seus extrems. Un objectiu freqüent en la coloració de gràfics és minimitzar el nombre total de colors que s'utilitzen; el «nombre cromàtic» d'un graf és aquest nombre mínim de colors.[Nota 1] El teorema dels quatre colors estableix que cada graf finit que es pot dibuixar sense encreuaments en el pla euclidià necessita com a màxim quatre colors; tanmateix, alguns grafs amb connectivitat més complicada requereixen més de quatre colors.[2] És una conseqüència de l'axioma de l'elecció que el nombre cromàtic està ben definit per a grafs infinits, però per a aquests grafs el nombre cromàtic podria ser en si mateix un nombre cardinal infinit.[3]

Un subgraf d'un graf és un altre graf obtingut a partir d'un subconjunt dels seus vèrtexs i d'un subconjunt de les seves arestes. Si el graf més gran està acolorit, es pot utilitzar el mateix color per al subgraf. Per tant, el nombre cromàtic d'un subgraf no pot ser més gran que el nombre cromàtic de tot el graf. El teorema de De Bruijn-Erdős es refereix als nombres cromàtics de grafs infinits, i mostra que (de nou, assumint l'axioma de l'elecció) es poden calcular a partir dels nombres cromàtics dels seus subgrafs finits. Afirma que, si els nombres cromàtics dels subgrafs finits d'un graf  tenen un valor màxim finit , el nombre cromàtic de és exactament . D'altra banda, si no hi ha cap límit superior finit en els nombres cromàtics dels subgrafs finits de , el nombre cromàtic de ha de ser infinit.[4]

Aplicacions

La motivació original d'Erdős a l'hora d'estudiar aquest problema va ser estendre dels grafs finits a infinits el teorema que, sempre que un graf tingui una orientació amb un grau superior finit, també té una -coloració. Per als grafs finits això succeeix perquè aquests grafs sempre tenen un vèrtex de grau com a màxim, que es pot acolorir amb un de colors després que tots els vèrtexs restants s'acoloreixin de manera recursiva. Els grafs infinits amb aquesta orientació no sempre tenen un vèrtex de baix grau (per exemple, les xarxes de Bethe tenen , però un grau mínim arbitràriament gran), de manera que aquest argument requereix que el graf sigui finit. Però el teorema de De Bruijn-Erdős mostra que existeix una -coloració fins i tot per a grafs infinits.[Nota 2]

Un pla de set colors i el graf de Moser de quatre cromàtics dibuixats com a graf de distància unitat en el pla, proporcionant límits superiors i inferiors per al problema de Hadwiger-Nelson

Una altra aplicació del teorema de De Bruijn-Erdős és al problema de Hadwiger-Nelson, que pregunta quants colors es necessiten per acolorir els punts del pla euclidià de manera que cada dos punts que es troben a una distància unitat tinguin colors diferents. Aquest és un problema de coloració de grafs per a un graf infinit que té un vèrtex per a cada punt del pla i una aresta per cada dos punts la distància euclidiana dels quals és exactament una. Els subgrafs d'aquest grafs s'anomenen «grafs de distància unitat». Un graf de distància unitat de set vèrtex, el graf de Moser, requereix quatre colors; el 2018, es van trobar grafs de distància d'unitats molt més grans que requereixen cinc colors.[5] Tot el graf infinit té una coloració coneguda amb set colors basat en un mosaic hexagonal del pla. Per tant, el nombre cromàtic del pla ha de ser 5, 6 o 7, però no se sap quin d'aquests tres nombres és el valor correcte. El teorema de De Bruijn-Erdős mostra que, per a aquest problema, existeix un graf de distància unitat finita amb el mateix nombre cromàtic que tot el pla, de manera que si el nombre cromàtic és superior a cinc, aquest fet es pot demostrar mitjançant un càlcul finit.[6]

El teorema de De Bruijn-Erdős també es pot utilitzar per estendre el teorema de Dilworth de conjunts parcialment ordenats finits a infinits. El teorema de Dilworth estableix que l'amplada d'un ordre parcial (el nombre màxim d'elements en un conjunt d'elements mútuament incomparables) és igual al nombre mínim de cadenes (subconjunts totalment ordenats) en què es pot dividir l'ordre parcial. Una partició en cadenes es pot interpretar com una coloració del graf d'incomparabilitat de l'ordre parcial. Aquest és un graf amb un vèrtex per a cada element de l'ordre i una aresta per a cada parell d'elements incomparables. Utilitzant aquesta interpretació de color, juntament amb una demostració separada del teorema de Dilworth per a conjunts parcialment ordenats finits, és possible demostrar que un conjunt parcialment ordenat infinit té una amplada finita  si i només si té una partició en cadenes.[7]

De la mateixa manera, el teorema de De Bruijn-Erdős amplia el teorema dels quatre colors des de grafs planars finits fins a grafs planars infinits. Cada graf pla finit es pot pintar amb quatre colors, segons el teorema dels quatre colors. Aleshores, el teorema de De Bruijn-Erdős mostra que cada graf que es pot dibuixar sense encreuaments en el pla, finit o infinit, es pot pintar amb quatre colors. De manera més general, cada graf infinit per al qual tots els subgrafs finits són plans pot tornar a ser de quatre colors.[Nota 3][8]

Demostracions

La demostració original del teorema de De Bruijn-Erdős, de De Bruijn, utilitzava la inducció transfinita.[9]

[Gottschalk 1951] va proporcionar la següent demostració molt breu, basada en el teorema de compacitat de Tíkhonov en topologia. Suposem que, per al graf infinit donat , cada subgraf finit és -colorable, i fem que  sigui l'espai de totes les tasques dels -colors als vèrtexs de  (independentment de si formen una coloració vàlida). Aleshores es pot donar una topologia com a espai de producte , on  denota el conjunt de vèrtexs del graf. Segons el teorema de Tychonoff, aquest espai topològic és compacte. Per a cada subgraf finit de , fem que sigui el subconjunt de  consistent en assignacions de colors que acoloreixin vàlidament . Llavors, el sistema de conjunts és una família de conjunts tancats amb la propietat de la intersecció finita, de manera que per compacitat té una intersecció no buida. Cada membre d'aquesta intersecció és un color vàlid de .[Nota 4][10]

Una prova diferent utilitzant el lema de Zorn va ser donada per Lajos Pósa, i també en la tesi doctoral Ph.D. de 1951 de Gabriel Andrew Dirac. Si  és un graf infinit en el qual es troba cada subgraf finit -colorable, llavors pel lema de Zorn és un subgraf d'un graf màxim  amb la mateixa propietat (una a la qual no es poden afegir més arestes sense fer que algun subgraf finit requereixi més de  colors). La relació binària de no adjacència en  és una relació d'equivalència i les seves classes d'equivalència proporcionen una -coloració de . Tanmateix, aquesta demostració és més difícil de generalitzar que la prova de compacitat.[Nota 5][11]

El teorema també es pot demostrar mitjançant ultrafiltres[12] o anàlisis no estàndard.[13][14] Dóna una demostració per a grafs amb un nombre comptable de vèrtexs basat en el lema de l'infinit de Kőnig.

Dependència de l'elecció

Totes les demostracions del teorema de De Bruijn-Erdős utilitzen alguna forma de l'axioma de l'elecció. És necessària alguna forma d'aquesta suposició, ja que existeixen models de matemàtiques en què tant l'axioma de l'elecció com el teorema de De Bruijn-Erdős són falsos. Més precisament, [Mycielski 1961][15] va demostrar que el teorema és una conseqüència del teorema de l'ideal primer booleà, una propietat que està implicada per l'axioma de l'elecció però més feble que l'axioma complet de l'elecció, i [Läuchli 1971][16] va demostrar que el teorema de De Bruijn-Erdős i el teorema de l'ideal primer booleà són equivalents en potència axiomàtica.[Nota 6]

També es pot demostrar que el teorema de De Bruijn-Erdős per a grafs comptables és equivalent en poder axiomàtic, dins d'una teoria de l'aritmètica de segon ordre, al lema de l'infinit de Kőnig.[17]

Per a un contraexemple del teorema en models de teoria de conjunts sense elecció, fem que sigui un graf infinit en què els vèrtexs representen tots els nombres reals possibles. En , es connecta cada dos nombres reals  i   per una vora sempre que un dels valors  és un nombre racional. De manera equivalent, en aquest graf existeixen arestes entre tots els nombres reals  i tots els nombres reals de la forma , per a nombres racionals . Cada camí d'aquest graf, començant per qualsevol nombre real , alterna números que difereixen de  per un nombre racional més un múltiple parell de  i números que difereixen de  per un nombre racional més un múltiple senar de .

Aquesta alternança evita que contingui qualsevol cicle de longitud senar, de manera que cadascun dels seus subgrafs finits només requereix dos colors. Tanmateix, en el model de Solovay en què cada conjunt de nombres reals és mesurable per Lebesgue, requereix infinits colors, ja que en aquest cas cada classe de color ha de ser un conjunt mesurable i es pot demostrar que cada conjunt mesurable de nombres reals sense arestes en  ha de tenir la mesura zero. Per tant, en el model de Solovay, el nombre cromàtic (infinit) de tots  és molt més gran que el nombre cromàtic dels seus subgrafs finits (com a màxim dos).[18][19]

Generalitzacions

[Rado 1949] demostra el següent teorema, que es pot veure com una generalització del teorema de De Bruijn-Erdős. Fem que siguir un conjunt infinit, per exemple el conjunt de vèrtexs en un gràfic infinit. Per a cada element de , fem que sigui un conjunt finit de colors. A més, per a cada subconjunt finit   de , s'escull algun color en particular  de , en què el color de cada element  de   pertany a . Aleshores hi ha una coloració global  de tots amb la propietat que tot conjunt finit té un superconjunt finit en la qual   i es consenteixen. En particular, si escollim una -coloració per a cada subgraf finit d'un graf infinit , llavors hi ha a -coloració de en què cada graf finit té un supergraf més gran la coloració del qual coincideix amb la coloració de tot el graf.[Nota 7]

Si un graf no té un nombre cromàtic finit, aleshores el teorema de De Bruijn-Erdős implica que ha de contenir subgrafs finits de tots els nombres cromàtics finits possibles. Els investigadors també han investigat altres condicions sobre els subgrafs que es veuen obligats a produir-se en aquest cas. Per exemple, els grafs cromàtics sense límits també han de contenir tots els possibles grafs bipartits finits com a subgraf. Tanmateix, poden tenir un cinturó imparell arbitràriament gran i, per tant, poden evitar qualsevol conjunt finit de subgrafs no bipartits.[3][20]

El teorema de De Bruijn-Erdős també s'aplica directament als problemes de coloració d'hipergrafs, on es requereix que cada hiperaresta tingui vèrtexs de més d'un color. Pel que fa als grafs, un hipergraf té una -coloració si i només si cadascun dels seus subhipergrafs finits té una -coloració.[21] És un cas especial del teorema de compacitat de Kurt Gödel, que afirma que un conjunt de sentències de primer ordre té un model si i només si cada subconjunt finit té un model.[22] Més concretament, el teorema de De Bruijn-Erdős es pot interpretar com la compacitat de les estructures de primer ordre els valors no lògics de les quals són qualsevol conjunt finit de colors i l'únic predicat de les quals sobre aquests valors és la desigualtat.[23]

El teorema també es pot generalitzar a situacions en què el nombre de colors és un nombre cardinal infinit. Si  és un cardinal fortament compacte, llavors per a cada graf  i número cardinal ,   té un nombre cromàtic com a màxim  si i només si cadascun dels seus subgrafs de cardinalitat és inferior a té un nombre cromàtic com a màxim .[Nota 8] El teorema original de De Bruijn-Erdős és el cas d'aquesta generalització, ja que un conjunt és finit si i només si la seva cardinalitat és menor que . No obstant això, cal supòsits com el de ser un cardinal fortament compacte: si la hipòtesi del continu generalitzat és certa, aleshores per a cada cardinal infinit , existeix un graf  de cardinalitat  tal que el nombre cromàtic de és més gran que , però de manera que cada subgraf de el conjunt de vèrtexs del qual té una potència menor que  té un nombre cromàtic com a màxim .[24][25]

[Lake 1975] caracteritza els grafs infinits que obeeixen a una generalització del teorema de De Bruijn–Erdős, ja que el seu nombre cromàtic és igual al nombre cromàtic màxim dels seus subgrafs estrictament més petits.

Notes

  1. Per a aquestes definicions bàsiques, vegeu [Jensen, Toft 1995, p. 1-2]
  2. [Erdős 1950], en particular a la pàgina 137, on el teorema de De Bruijn-Erdős s'anuncia per primera vegada (però no demostrat) amb una pista que el lema de Kőnig es pot utilitzar per a grafs comptables.
  3. [Nash-Williams 1967] afirma el mateix resultat per al teorema dels cinc colors per als gràfs planars comptables, ja que el teorema dels quatre colors encara no s'havia demostrat quan va publicar la seva investigació, i com que la demostració del teorema de De Bruijn-Erdős que dóna només s'aplica als grafs comptables. Per a la generalització a gràfs en què cada subgraf finit és pla (provat directament mitjançant el teorema de compacitat de Gödel). Vegeu [Rautenberg 2010].
  4. Gottschalk afirma la seva demostració de manera més general com una demostració del teorema de [Rado 1949] que generalitza el teorema de De Bruijn–Erdős.
  5. [Jensen, Toft 1995] atribueixen a Gert Sabidussi l'observació que la demostració de Gottschalk és més fàcil de generalitzar. [Soifer 2008, pàg. 238-239] dóna la mateixa prova mitjançant el lema de Zorn, redescobert el 2005 per l'estudiant de grau Dmytro Karabash.
  6. Per a aquesta història, vegeu [Cowen Hechler Mihók, 2002]. Per a la demostració simplificada del teorema de Läuchli per Mycielski, vegeu [Cowen 1990].
  7. Per a aquesta connexió entre el lema de Rado i el teorema de De Bruijn–Erdős vegeu, per exemple, la discussió seguint el teorema A de [Nash-Williams 1967].
  8. Això es desprèn immediatament de la definició d'un cardinal fortament compacte com a cardinal tal que cada col·lecció de fórmules de lògica infinitària cada una de longitud inferior a , que és satisfactori per a cada subcol·lecció de menys de fórmules, és globalment satisfacible. Vegeu per exemple [Kanamori 2008].

Referències

Bibliografia