Anti-Ramsey forbidden poset problems

Dit artikel onderzoekt anti-Ramsey-getallen voor poset-verbod in de machtsverzameling van $\{1, \dots, n\}$, legt verbanden met extremale getallen en bepaalt asymptotisch de waarden voor boom-posets en kroon-posets.

De kern

De Kleurrijke Wiskunde van Verboden Patronen: Een Uitleg

Stel je voor dat je een enorme bibliotheek hebt, maar dan niet met boeken, maar met verzamelingen. Je hebt een doos met nummers van 1 tot $n$ (bijvoorbeeld 1 tot 100). Elke verzameling is een selectie van deze nummers. Je kunt een verzameling kiezen als {1, 5, 99} of {2, 3, 4, 5}. Er zijn enorm veel mogelijke combinaties.

Deze wiskundigen (Balázs Patkós) spelen een spelletje met deze verzamelingen. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het Spel: Kleuren en Patronen

Stel je voor dat je elke mogelijke verzameling in je bibliotheek een eigen kleur geeft. Je hebt een doos met duizenden verfkleuren.

• Het doel: Je wilt zo veel mogelijk verschillende kleuren gebruiken.
• De regel: Je mag geen "regenboog-patroon" maken.

Wat is een "regenboog-patroon"?
Stel je voor dat je een specifiek patroon zoekt, bijvoorbeeld een "klimop" (een boomstructuur) of een "kroon" (een cirkel). Als je in je gekleurde verzamelingen een groepje kunt vinden dat precies dat patroon vormt, en elk stukje van dat patroon een andere kleur heeft, dan heb je een "regenboog-kopie" gevonden. Dat mag niet!

De vraag van de auteurs is: Hoeveel kleuren kun je maximaal gebruiken voordat je per ongeluk toch zo'n regenboog-patroon creëert? Dit noemen ze het anti-Ramsey-getal.

2. De Twee Manieren om te Kijken: "Zwak" vs. "Sterk"

In de wiskunde is het belangrijk hoe precies je bent. De auteurs kijken naar twee soorten patronen:

• De Zwakke Kopie (De "Vriendelijke" Regels):
  Stel je voor dat je een groep mensen hebt die in een hiërarchie staan (een baas, een medewerker, een stagiair). Als de baas "kleiner" is dan de medewerker (in de zin van rang), dan moet de verzameling van de baas ook "kleiner" zijn (in de zin van inhoud) dan die van de medewerker.

  • Regel: Als A < B, dan moet verzameling A in verzameling B zitten.
  • Maar: Als A en B niets met elkaar te maken hebben, maakt het niet uit of hun verzamelingen overlappen of niet. Het is een wat losser patroon.

• De Sterke Kopie (De "Strenge" Regels):
  Hier zijn de regels veel strakker. Als A < B, dan moet A in B zitten. Maar ook het omgekeerde geldt: als A in B zit, dan moet A < B zijn.

  • Regel: De relatie tussen de mensen en de relatie tussen de verzamelingen moeten exact overeenkomen. Geen enkele uitzondering.

3. De Grote Ontdekkingen

De auteurs hebben gekeken naar verschillende vormen van patronen (zoals bomen, kronen en diamanten) en hebben ontdekt hoe het aantal kleuren zich gedraagt.

De "Boom" (Tree Posets):
Stel je een stamboom voor. De auteurs hebben bewezen dat als je een boom-patroon wilt vermijden, het maximale aantal kleuren dat je kunt gebruiken bijna gelijk is aan het maximale aantal verzamelingen dat je kunt hebben zonder dat je überhaupt een boom-patroon hebt (ongeacht de kleuren).

• Analogie: Het is alsof je zegt: "Als je niet meer dan X mensen in een kamer kunt hebben zonder dat er een familieband is, dan kun je ook niet meer dan X kleuren gebruiken zonder dat er een regenboog-familieband is." De grens is bijna hetzelfde.

De "Kroon" (Crown Posets):
Dit is een patroon dat lijkt op een cirkel van mensen die elkaar afwisselend "beheren" (A beheert B, B beheert C, C beheert D, D beheert A).

• Voor deze specifieke vormen hebben ze bewezen dat het aantal kleuren dat je kunt gebruiken ook een heel specifiek, voorspelbaar patroon volgt. Het is alsof je een kroon probeert te bouwen met gekleurde blokken; zodra je te veel kleuren gebruikt, valt de kroon in elkaar of vormt hij per ongeluk de verboden vorm.

4. Waarom is dit interessant?

Vroeger wisten wiskundigen alleen hoeveel verzamelingen je maximaal kunt hebben zonder een verboden patroon (dit heet het Turán-probleem). Dit nieuwe werk kijkt naar de kleuren.

Het is als een puzzel:

• Oud probleem: "Hoeveel lego-blokken mag ik stapelen voordat de toren omvalt?"
• Nieuw probleem (Anti-Ramsey): "Hoeveel verschillende kleuren verf mag ik op die lego-blokken gebruiken voordat ik per ongeluk een regenboog-patroon creëer dat de toren doet omvallen?"

De auteurs laten zien dat voor veel vormen (zoals bomen), het antwoord op het nieuwe probleem (kleuren) bijna hetzelfde is als het oude probleem (aantal blokken). Maar voor andere vormen (zoals de "kroon") is het net even anders, en ze hebben de exacte formules gevonden om dit te voorspellen.

Samenvattend

Deze paper is een reis door de wereld van vermijden. Ze zeggen eigenlijk: "Als je probeert zo kleurrijk mogelijk te zijn zonder een specifiek geheim patroon te vormen, is er een limiet. En voor veel patronen is die limiet verrassend nauw verbonden aan de limiet van het aantal objecten dat je überhaupt kunt hebben."

Het is een mooi voorbeeld van hoe wiskundigen proberen de grenzen van de chaos te vinden: hoe chaotisch (kleurrijk) kun je zijn voordat de orde (het verboden patroon) zich vanzelf voordoet?

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Anti-Ramsey Forbidden Poset Problems" van Balázs Patkós, geschreven in het Nederlands.

Titel: Anti-Ramsey Verboden Poset Problemen

Auteur: Balázs Patkós
Onderwerp: Extremale Combinatoriek, Poset-theorie, Anti-Ramsey theorie

---

1. Probleemstelling en Context

Het artikel onderzoekt een variant van het klassieke Turán-probleem binnen de extremale combinatoriek, specifiek gericht op verboden subposets (forbidden subposets) in de verzameling van alle deelverzamelingen van $\{1, 2, \dots, n\}$, genoteerd als $2^{[n]}$.

• Traditioneel probleem: Bepaal de maximale grootte van een familie $F \subseteq 2^{[n]}$ die geen kopie bevat van een gegeven geordende verzameling (poset) $P$. Dit wordt aangeduid als $La(n, P)$ (voor zwakke kopieën) en $La^*(n, P)$ (voor sterke kopieën).
• Anti-Ramsey variant: In plaats van de grootte van de familie te maximaliseren, wordt het aantal kleuren gemaximaliseerd in een kleuring van $2^{[n]}$met de voorwaarde dat er **geen regenboog-kopie** (rainbow copy) van$P$ bestaat.
  • Een familie $G$ is een zwakke kopie van $P$ als er een bijectie $f: P \to G$ bestaat zodanig dat $p \le q \implies f(p) \subseteq f(q)$.
  • Een familie $G$ is een sterke kopie van $P$ als $p \le q \iff f(p) \subseteq f(q)$.
  • Een kopie is regenboog als alle elementen in de kopie verschillende kleuren hebben.
• Doel: Het bepalen van de anti-Ramsey getallen $ar(n, P)$ en $ar^*(n, P)$, gedefinieerd als het maximum aantal kleuren in een kleuring van $2^{[n]}$zonder een regenboog-zwakke respectievelijk regenboog-sterke kopie van$P$.

De auteur bouwt een brug tussen deze nieuwe anti-Ramsey getallen en de reeds bestudeerde extremale getallen $La(n, P)$ en $La^*(n, P)$.

---

2. Methodologie

De paper combineert verschillende geavanceerde technieken uit de extremale verzamelingstheorie:

1. Convexe Families en Lagere/Bovenste Grenzen:

   • Er wordt een verband gelegd tussen $ar(n, P)$ en het maximale formaat van een convexe $P$-vrije familie ($La_{con}(n, P)$). Een familie is convex als voor elke $F, F' \in \mathcal{F}$ met $F \subseteq G \subseteq F'$, ook $G \in \mathcal{F}$.
   • Propositie 1.1 en 1.2 geven fundamentele ongelijkheden die $ar(n, P)$ begrenzen door $La(n, P \setminus \{m\})$ waar $m$ een maximaal of minimaal element is.

2. Inbeddingstechnieken (Embedding Results):

   • De kern van de bewijzen voor de hoofdstellingen ligt in het inbedden van specifieke poset-structuren in grote families van verzamelingen.
   • Er wordt gebruik gemaakt van Lubell-massa ($\lambda_n(F)$), een maat voor de gemiddelde hoeveelheid verzamelingen uit een familie die voorkomen in een willekeurige maximale keten in $2^{[n]}$.
   • Supersaturation: Het bewijs maakt gebruik van het idee dat als een familie groot genoeg is (bepaald door de extremale drempel), deze niet alleen een kopie bevat, maar een kopie met extra eigenschappen (zoals disjunctie van specifieke elementen).

3. Probabilistische en Combinatorische Argumenten:

   • Voor het bewijs van inbeddingstheorema's (Theorema 2.1 en 2.2) worden bipartiete grafen geconstrueerd en eigenschappen van gemiddelde en minimale graad gebruikt (Observatie 2.5).
   • Er wordt gewerkt met specifieke subposets zoals spinnen ($S_{k,\ell}$) en kronen ($O_{2k}$).
   • De bewijzen gebruiken een iteratieve inbeddingsstrategie (gebaseerd op werk van Bukh en Boehnlein/Jiang) waarbij een boom-poset stap voor stap wordt ingebouwd in de familie, waarbij "obstakels" (reeds ingebouwde elementen) worden omzeild.

4. Analyse van Specifieke Classes:

   • Boom-posets (Tree posets): Posets waarvan het Hasse-diagram een boom is.
   • Kronen (Crown posets $O_{2k}$): Posets met een georiënteerd Hasse-diagram dat een antigeoriënteerde cyclus vormt.

---

3. Belangrijkste Resultaten

De paper levert asymptotische bepalingen voor de anti-Ramsey getallen voor twee belangrijke klassen van posets:

A. Boom-posets (Tree Posets)

Voor elke boom-poset $T$ met hoogte $h(T)$ (lengte van de langste keten):

• Stelling 1.5: $ar^*(n, T) = (1 + o(1)) La^*((n, P \setminus \{m\}))$, waarbij $m$ een element is dat in alle langste ketens voorkomt.
• Gezien de bekende resultaten van Bukh en Boehnlein/Jiang dat $La^*(n, T) \sim (h(T)-1)\binom{n}{\lfloor n/2 \rfloor}$, volgt hieruit dat voor boom-posets de anti-Ramsey getallen asymptotisch gelijk zijn aan de extremale getallen van de poset met één element verwijderd (of de hoogte verminderd met 1).
• Dit geldt zelfs voor complexe boom-posets die een minimaal/maximaal element bevatten dat in alle langste ketens zit, maar niet het absolute minimum of maximum is van de hele poset.

B. Kronen (Crown Posets $O_{2k}$)

Voor de kroon-poset $O_{2k}$ (met $k \ge 3$):

• Stelling 1.6: $ar^*(n, O_{2k}) = (1 + o(1)) \binom{n}{\lfloor n/2 \rfloor}$.
• Dit is een verrassend resultaat omdat de extremale getallen $La^*(n, O_{2k})$ voor $k \ge 3$ nog niet volledig zijn vastgesteld, maar de anti-Ramsey variant wel bepaald kan worden. Het resultaat suggereert dat de "moeilijkheid" van het vermijden van een regenboog-kopie van een kroon vergelijkbaar is met het vermijden van een enkele laag in de middelste niveaus van de Boolean lattice.
• Voor het specifieke geval van de "butterfly" poset ($O_4$ of $\triangleright\triangleleft$), wordt bewezen dat $ar^*(n, \triangleright\triangleleft) = (2+o(1))\binom{n}{\lfloor n/2 \rfloor}$, wat overeenkomt met de som van de twee middelste lagen.

C. Kleine Posets en Specifieke Constructies

• Propositie 1.3: Exacte formules worden gegeven voor specifieke kleine posets zoals de "fork" ($\vee_s$), "broom" ($\wedge_s$) en antichains ($A_k$).
  • Bijvoorbeeld: $ar^*(n, \vee_s) = (s-1)(n-1) + 2$.
• Er wordt aangetoond dat als een poset $P$ geen zwakke kopie bevat van $2C_2$(twee ongerelateerde kopieën van een keten van lengte 2), dan is$ar(n, P) = |P| - 1$.

---

4. Significantie en Bijdrage

1. Verbinding tussen Gebieden: Het artikel slaat een brug tussen de klassieke extremale theorie van posets (Turán-type problemen) en de anti-Ramsey theorie. Het toont aan dat voor veel poset-structuren de anti-Ramsey getallen asymptotisch worden bepaald door de extremale getallen van gerelateerde, iets kleinere posets.
2. Oplossing voor Open Problemen: Het biedt de eerste asymptotische resultaten voor anti-Ramsey getallen van sterke kopieën van boom-posets en kronen, klassen die centraal staan in de extremale poset-theorie.
3. Technische Innovatie: De methode om inbeddingen te construeren met extra restricties (zoals het vermijden van specifieke unies of doorsneden van reeds ingebouwde elementen) is een krachtige verrijking van de toolkit voor het bestuderen van regenboog-varianten van extremale problemen.
4. Contraintuïtieve Resultaten: Het resultaat voor de kroon-poset $O_{2k}$ is opmerkelijk omdat het laat zien dat de anti-Ramsey drempel lager kan liggen dan wat men misschien zou verwachten op basis van de complexe structuur van de kroon, en dat deze volledig wordt bepaald door de grootte van de middelste laag van de Boolean lattice.

Kortom, dit werk definieert een nieuwe subdiscipline binnen de extremale combinatoriek en biedt een robuust raamwerk voor het analyseren van kleuringsproblemen in de context van geordende verzamelingen.