Strukturell Ramsey-teori

I matematik är strukturell Ramsey-teorin en kategorisk generalisering av Ramsey-teorin , med rötter i idén att många viktiga resultat av Ramsey-teorin har "liknande" logisk struktur. Den viktigaste observationen är att notera att dessa Ramsey-typsatser kan uttryckas som påståendet att en viss kategori (eller klass av ändliga strukturer) har Ramsey- egenskapen (definierad nedan).

Nešetřils och Rödls arbete, och är intimt kopplad till Fraïssé-teorin . Den fick en del förnyat intresse i mitten av 2000-talet på grund av upptäckten av Kechris-Pestov-Todorčević-korrespondensen, som kopplade strukturell Ramsey-teori till topologisk dynamik .

Historia

Leeb [ de ] får kredit för att han uppfann idén om en Ramsey-fastighet i början av 70-talet, och den första publiceringen av denna idé verkar vara Graham , Leeb och Rothschilds 1972-uppsats i ämnet. Nyckelutvecklingen av dessa idéer gjordes av Nešetřil och Rödl i deras serie av artiklar från 1977 och 1983, inklusive den berömda Nešetřil–Rödl-satsen. Detta resultat motbevisades oberoende av Abramson och Harrington och generaliserades ytterligare av Prömel [ de ] . På senare tid har Mašulović och Solecki gjort en del banbrytande arbete på området.

Motivering

Den här artikeln kommer att använda den mängdteoretiska konventionen att varje naturligt tal $n\in \mathbb {N}$ kan betraktas som mängden av alla naturliga tal mindre än det: dvs $n=\{0,1,\ldots ,n-1\}$ . För varje uppsättning ${\displaystyle A} är$ en $r$ -färgning av $A$ en tilldelning av en av $r$ etiketter till varje element i $A$ . Detta kan representeras som en funktion $\Delta :A\to r$ som mappar varje element till dess etikett i $r=\{0 ,1,\ldots ,r-1\}$ (som den här artikeln kommer att använda), eller motsvarande som en partition av $A=A_{0}\sqcup \cdots \ sqcup A_{r-1}$ i $r$ bitar.

Här är några av de klassiska resultaten av Ramsey-teorin:

(Finite) Ramseys sats : för varje ${\displaystyle k\leq m,r\in \mathbb {N} } ,$ finns det $n\in \mathbb {N}$ så att för varje $r$ -färgning $\Delta :[n]^{(k)}\to r$ av alla $k$ -element delmängder av ${\displaystyle n=\{0,1,\ldots ,n-1\}} ,$ det finns en delmängd $A\subseteq n$ , med $|A|=m$ , så att $[A]^{(k)}$ är $\Delta$ -monokromatisk.
(Finite) van der Waerdens sats : för varje $m,r\in \mathbb {N}$ , finns det $n\in \mathbb {N}$ så att för varje $r$ -färgning $\Delta :n\to r$ av $n$ , det finns en $\Delta$ -monokromatisk aritmetisk progression $\{a,a+d,a+2d,\ldots ,a+(m-1)d\}\ subseteq n$ av längden $m$ .
Graham–Rothschilds sats : fixa ett ändligt alfabet $L=\{a_{0},a_{1},\ldots ,a_{d-1} \}$ . A $k$ - parameterord med längden $n$ över $L$ är ett element ${ \ displaystyle w\in (L\cup \{x_{0},x_{1},\ldots ,x_{k-1}\})^{n}} , så att alla$ x $\displaystyle x_{ i}}$ visas, och deras första framträdanden är i ökande ordning. Mängden av alla $k$ -parameterord med längden $n$ över $L$ betecknas med $\textstyle [L]{\binom { n}{k}}$ . Givet $\textstyle w\in [L]{\binom {n}{m}}$ och $\textstyle v\in [L]{\binom {m}{k}}$ , vi bildar deras sammansättning $\textstyle w\circ v\in [L]{\binom {n} {k}}$ genom att ersätta varje förekomst av $x_{i}$ i $w$ med $i$ :e posten i $v$ . Sedan säger Graham–Rothschild-satsen att för varje ${\displaystyle k\leq m,r\in \mathbb {N} } ,$ finns det $n\in \mathbb { N}$ så att för varje $r$ -färgning $\textstyle \Delta :[L]{\binom {n}{k}}\to r$ av alla $k$ -parameterord med längden $n$ , finns $\textstyle w\in [L]{\binom {n} {m}}$ , så att ${\displaystyle \textstyle w\circ [L]{\binom {m} {k}}=\{w\circ v:v\in [L]{\binom {m}{k}}\}} (dvs alla k {\displaystyle k} -parameters underord$ för ${$ \ $w }$ ) är $\Delta$ -monokromatisk.
(Finite) Folkmans teorem : för varje $m,r\in \mathbb {N}$ , finns det $n\in \mathbb {N}$ så att för varje $r$ -färgning $\Delta :n\to r$ av $n$ , det finns en delmängd $A\subseteq n$ , med $|A|=m$ , så att $\textstyle {\big (}\summa _{k\in A}k{\big )}<n$ , och $\textstyle \operatörsnamn {FS} (A)=\{\summa _{k\in B} k:B\in {\mathcal {P}}(A)\setminus \varnothing \}$ är $\Delta$ -monokromatisk.

Dessa "Ramsey-typ"-satser har alla en liknande idé: vi fixar två heltal $k$ och $m$ , och en uppsättning färger $r$ . Sedan vill vi visa att det finns några $n$ tillräckligt stora, så att för varje $r$ -färgning av "understrukturerna" av storleken $k$ inuti $n$ , kan vi hitta en lämplig "struktur" $A$ inuti $n$ , av storleken $m$ , så att alla "understrukturerna" $B$ av $A$ med storlek $k$ har samma färg.

Vilka typer av strukturer som är tillåtna beror på satsen i fråga, och detta visar sig vara praktiskt taget den enda skillnaden mellan dem. Denna idé om en "Ramsey-typsats" leder sig till den mer exakta uppfattningen om Ramsey-egenskapen (nedan).

Fastigheten Ramsey

Låt $\mathbf {C}$ vara en kategori . $\mathbf {C}$ har Ramsey-egenskapen if för varje naturligt tal $r$ , och alla objekt $A,B$ i $\mathbf {C}$ , det finns ett annat objekt $D$ i $\mathbf {C}$ , så att för varje $r$ -färgning $\ Delta :\operatörsnamn {Hom} (A,D)\to r$ , det finns en morfism $f:B\to D$ som är $\Delta$ -monokromatisk, dvs. uppsättning

f\circ \operatörsnamn {Hom} (A,B)={\big \{}f\ circ g:g\in \operatörsnamn {Hom} (A,B){\big \}}

är $\Delta$ -monokromatisk.

Ofta anses $\mathbf {C}$ vara en klass av ändliga ${\mathcal {L}}$ -strukturer över något fast språk ${\mathcal {L}}$ , med inbäddningar som morfismer. I det här fallet, istället för att färglägga morfismer, kan man tänka på att färglägga "kopior" av $A$ i ${\displaystyle D} ,$ och sedan hitta en kopia av $B$ i $D$ , så att alla kopior av $A$ i denna kopia av $B$ är monokromatiska. Detta kan lämpa sig mer intuitivt för den tidigare idén om en "Ramsey-typsats".

Det finns också en föreställning om en dubbel Ramsey-egendom; $\mathbf {C}$ har den dubbla Ramsey-egenskapen om dess dubbla kategori $\mathbf {C} ^{\mathrm {op} }$ har Ramsey-egenskapen enligt ovan. Mer konkret har ${\displaystyle \mathbf {C} } den$ dubbla Ramsey-egenskapen if för varje naturligt tal $r$ , och alla objekt $A,B$ i $\mathbf {C}$ , det finns ett annat objekt $D$ i $\mathbf {C}$ , så att för varje $r$ -färgning $\Delta :\operatörsnamn {Hom} (D,A)\to r$ , det finns en morfism $f:D\to B$ för vilken $\operatorname {Hom} (B,A)\circ f$ är $\Delta$ -monokromatisk.

Exempel

Ramseys teorem: klassen av alla ändliga kedjor , med ordningsbevarande kartor som morfismer, har Ramsey-egenskapen.
van der Waerdens teorem: i kategorin vars objekt är ändliga ordinaler och vars morfismer är affina kartor $x\mapsto a+dx$ för ${\displaystyle a,d\$ , $d\neq 0$ , Ramsey-egenskapen gäller för $A=1$ .
Hales–Jewetts sats : låt $L$ vara ett ändligt alfabet, och för varje ${\displaystyle k\in \mathbb {N} } ,$ låt $X_{k}=\{x_{0},\ldots ,x_{k-1}\}$ vara en uppsättning av $k$ variabler. Låt $\mathbf {GR}$ vara kategorin vars objekt är $A_{k}=L\cup X_{k}$ för varje $k \in \mathbb {N}$ , och vars morfismer $A_{n}\to A_{k}$ , för $n\geq k$ , är funktioner $f:X_{n}\to A_{k}$ som är stela och surjektiva på $X_{k}\subseteq A_{k}=\ operatörsnamn {codom} f$ . Sedan $\mathbf {GR}$ den dubbla Ramsey-egenskapen för $A=A_{0}$ (och $B=A_{1}$ , beroende på på formuleringen).
Graham–Rothschilds sats: kategorin $\mathbf {GR}$ definierad ovan har den dubbla Ramsey-egenskapen.

Korrespondensen Kechris–Pestov–Todorčević

År 2005 upptäckte Kechris , Pestov och Todorčević följande korrespondens (hädanefter kallad KPT-korrespondensen ) mellan strukturell Ramsey-teori, Fraïssé-teori och idéer från topologisk dynamik.

Låt $G$ vara en topologisk grupp . För ett topologiskt utrymme ${\displaystyle X} är$ ett $G$ -flöde (betecknat $G\curvearrowright X$ ) en kontinuerlig åtgärd av $G$ på $X$ . Vi säger att $G$ är extremt mottaglig om något $G$ -flöde $G\curvearrowright X$ på ett kompakt utrymme $X$ tillåter en fast punkt $x\in X$ , dvs stabilisatorn för $x$ är själva ${\displaystyle G} .$

För en Fraïssé-struktur ${\displaystyle \mathbf {F} } kan$ dess automorfismgrupp $\operatorname {Aut} (\mathbf {F} )$ betraktas som en topologisk grupp, givet topologin för punktvis konvergens , eller ekvivalent, subrymdstopologin inducerad på $\operatorname {Aut} (\mathbf {F} )$ av mellanrummet ${\displaystyle \$ med produkttopologin . Följande teorem illustrerar KPT-korrespondensen:

Teorem (KPT). För en Fraïssé-struktur $\mathbf {F}$ är följande likvärdiga:

Gruppen $\operatorname {Aut} (\mathbf {F} )$ av automorfismer av $\mathbf {F}$ är extremt mottaglig.

Klassen $\operatorname {Age} (\mathbf {F} )$ har Ramsey-egenskapen.

Se även