Hat guessing with proper colorings

Dit artikel introduceert en analyseert het hoedengokgetal van een graaf onder de beperking dat de tegenstander alleen een juiste kleuring mag gebruiken, waarbij bewezen wordt dat dit getal voor volledige grafen $2n-1$ bedraagt, voor bomen gelijk is aan 4, en dat exacte waarden voor grafen tot vier knopen worden bepaald.

De kern

Stel je voor dat je deelneemt aan een gek spelletje met vrienden in een kamer. Iedereen heeft een hoed op, maar niemand mag zijn eigen hoed zien. Je kunt alleen de hoeden van je directe buren zien. Het doel is om tegelijkertijd te raden welke kleur hoed jij zelf draagt. Als ten minste één persoon het goed heeft, winnen jullie allemaal.

Dit is het klassieke "hoedjesgokspel". Maar in dit nieuwe artikel van een groep wiskundigen (Sam, Peter, Anurag en hun collega's) wordt de spelregels iets aangescherpt.

Het Nieuwe Spel: "De Strikte Kleurcode"

In het oude spel kon de "boze meester" (de adversary) elke willekeurige kleur op elke hoed plakken, zelfs als twee buren dezelfde kleur kregen.

In dit nieuwe variant mag de boze meester alleen hoedjes geven die voldoen aan een strenge regel: Twee buren mogen nooit dezelfde kleur hebben. Dit noemen wiskundigen een "propre kleuring" (een nette, correcte kleuring).

De vraag die deze wiskundigen zich stellen is: Hoeveel verschillende kleuren (laten we zeggen, van 1 tot q) kunnen we maximaal gebruiken, zodat jullie nog steeds een strategie hebben om zeker te winnen?

Dit maximum noemen ze het HGP (Hat Guessing Number met Proper coloring).

De Grote Ontdekkingen

Hier zijn de belangrijkste resultaten, vertaald naar alledaagse taal:

1. De "Perfecte" Groep (Volledige Grafieken)

Stel je een groep voor waar iedereen met iedereen bevriend is (een "kliek"). Iedereen ziet dus de hoedjes van iedereen anders.

• In het oude spel was het maximum aantal kleuren gelijk aan het aantal mensen.
• Het nieuwe resultaat: Omdat de kleuren zo streng verdeeld moeten zijn (niemand mag dezelfde kleur als zijn buur hebben), kunnen jullie met een slimme strategie bijna het dubbele van het aantal mensen aan kleuren aan!
• Als er n mensen zijn, kunnen jullie winnen met 2n - 1 kleuren.
• De analogie: Het is alsof je in een groep van 10 mensen, met een slimme code, kunt gokken op 19 verschillende kleuren, terwijl je in het oude spel maar op 10 kon gokken. De wiskundigen gebruiken hiervoor een trucje met "perfecte matchings" (zoals het perfect koppelen van schoenen in een grote schoenendoos) om te weten welke kleur je moet raden.

2. De Bomen (Struiken zonder lussen)

Stel je een familieboom voor of een takkenstructuur waar geen cirkels in zitten (geen mensen die in een kring zitten).

• Het resultaat is verrassend simpel: Voor elke boom met 3 of meer mensen, is het maximale aantal kleuren altijd 4.
• Het maakt niet uit of de boom klein is of gigantisch groot. Zodra je meer dan 4 kleuren probeert, is het onmogelijk om een strategie te vinden die altijd werkt.
• De analogie: Het is alsof je in een bos met bomen kunt gokken op 4 kleuren, maar als je een 5e kleur toevoegt, wordt het spel te chaotisch om te winnen.

3. Het "Boek" (Book Graphs)

Stel je een boek voor: een ruggengraat (een groep mensen die allemaal met elkaar bevriend zijn) en pagina's (mensen die alleen met de ruggengraat bevriend zijn, maar niet met elkaar).

• Hier ontdekten ze dat als je heel veel pagina's hebt, het aantal kleuren waar je op kunt gokken, relatief klein blijft. Het groeit niet oneindig, maar wordt "gebreid" door de grootte van de ruggengraat.

Hoe hebben ze dit bewezen?

De wiskundigen gebruiken twee hoofdgereedschappen:

1. Slimme Strategieën (De Ondergrens): Ze bouwen een plan op. Bijvoorbeeld: "Als ik de kleuren van mijn buren zie als een rij getallen, tel ik ze op en raad ik het resultaat." Voor de grote groepen gebruiken ze een heel ingewikkeld maar elegant systeem gebaseerd op het sorteren van combinaties (zoals het ordenen van kaarten in een deck).
2. De "Verwachte Winnaar" (De Bovengrens): Ze denken na: "Stel dat we q kleuren hebben. Als we willekeurig een geldige verdeling van hoedjes kiezen, hoeveel mensen raden er dan gemiddeld goed?" Als dit gemiddelde getal kleiner is dan 1, dan is het onmogelijk om altijd te winnen. Ze gebruiken dit om te bewijzen dat je niet te veel kleuren kunt hebben.

Waarom is dit interessant?

Vroeger dachten wiskundigen dat de regels van het spel (of je nu mag gokken op willekeurige kleuren of alleen op nette kleuren) niet zo'n groot verschil maakten. Dit artikel laat zien dat de regels het spel volledig veranderen.

• In het oude spel was het moeilijk om te winnen bij grote groepen.
• In dit nieuwe spel met de "nette kleuren" regel, blijkt dat je bij grote groepen juist veel meer kleuren kunt hanteren en dus een beter spel kunt spelen!

Conclusie

Deze paper is als het vinden van een nieuwe, slimmere manier om een raadsel op te lossen. Ze hebben laten zien dat door de regels iets strenger te maken (geen dubbele kleuren bij buren), het paradoxaal genoeg makkelijker wordt om een winnende strategie te vinden voor grote groepen mensen. Voor bomen is het antwoord simpel (4 kleuren), maar voor dichte groepen is het antwoord verrassend groot (bijna het dubbele van het aantal mensen).

Het is een mooi voorbeeld van hoe wiskundigen spelen met logica en strategieën om de grenzen van wat mogelijk is, te verkennen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Hat guessing with proper colorings" in het Nederlands.

Titel: Hoedgokken met juiste kleuringen (Hat guessing with proper colorings)

Auteurs: Sam Adriaensen, Peter Bentley, Anurag Bishnoi, et al.

---

1. Probleemstelling en Context

Het artikel introduceert een nieuwe variant van het klassieke "hoedgokspel" (hat guessing game) op grafen.

• Het klassieke spel: Op een graaf $G=(V, E)$ zit op elke hoek een speler met een hoed van een kleur uit een vaste set $[q] = \{1, ..., q\}$. Spelers zien de kleuren van hun buren, maar niet hun eigen kleur. Ze moeten gelijktijdig een gok doen over hun eigen kleur. Een strategie is winnend als er voor elke mogelijke toewijzing van kleuren (inclusief die waarbij buren dezelfde kleur hebben) minstens één speler correct gokt. Het "hoedgokgetal" $HG(G)$ is het maximale $q$ waarvoor een winnende strategie bestaat.
• De nieuwe variant (Proper Hat Guessing): De tegenstander (adversary) is hier beperkt tot het toewijzen van hoedkleuren die een juiste kleuring (proper coloring) van de graaf vormen. Dit betekent dat geen twee aangrenzende spelers dezelfde hoedkleur mogen hebben.
• Definitie: Het "propre hoedgokgetal", genoteerd als $HGP(G)$, is het grootste aantal kleuren $q$ waarvoor er een strategie bestaat die garandeert dat, voor elke juiste kleuring met $q$ kleuren, minstens één speler correct gokt.
• Relatie: Duidelijk geldt dat $HG(G) \leq HGP(G)$, omdat de verzameling van geldige situaties in de nieuwe variant een deelverzameling is van de klassieke variant.

2. Methodologie

De auteurs combineren verschillende wiskundige technieken om $HGP(G)$ te analyseren:

• Combinatorische constructies: Voor volledige grafen ($K_n$) wordt gebruikgemaakt van de structuur van de Boolese tralies (Boolean lattices). Specifiek wordt een strategie gebaseerd op het vinden van perfecte matchings tussen de middelste lagen van de Boolese tralies van dimensie $2n-1$.
• Hall's Matching Theorem: Dit wordt gebruikt om het bestaan van de benodigde perfecte matchings te garanderen, wat leidt tot een niet-constructief bewijs voor de ondergrens, hoewel expliciete constructies (zoals die van Greene en Kleitman) ook worden besproken.
• Lineaire Programmering (ILP): Voor kleine grafen wordt het probleem geformuleerd als een Integer Linear Programming (ILP) probleem (een haalbaarheidsprobleem) om exacte waarden te berekenen of grenzen te bepalen.
• Probabilistische methoden en telargumenten: Voor boekgrafiek (book graphs) en algemene bovenkanten worden tellingen van juiste kleuringen en de unie-bounds (union bound) gebruikt om te bepalen wanneer een winnende strategie onmogelijk is.
• Inductie en subgraaf-eigenschappen: Voor bomen wordt gebruikgemaakt van inductie en het verwijderen van bladeren (vertices met graad 1) om de resultaten te generaliseren.

3. Belangrijkste Resultaten

A. Volledige Grafen (Cliques)

• Stelling 1.1: Voor elke volledige graaf $K_n$ met $n \geq 2$ geldt:
  $$HGP(K_n) = 2n - 1$$
• Significantie: Dit is ongeveer het dubbele van het klassieke hoedgokgetal van een volledige graaf, dat gelijk is aan $n$.
• Bewijs: De ondergrens wordt bewezen door een strategie te construeren die correspondeert met een perfecte matching tussen $(n-1)$-elementige en $n$-elementige deelverzamelingen van $\{1, ..., 2n-1\}$. De bovengrens volgt uit een algemene ongelijkheid (zie hieronder).

B. Algemene Bovengrenzen

• Lemma 1.2: Voor elke graaf $G$ met $n$ vertices en chromatisch getal $\chi(G)$:
  $$HGP(G) \leq n + \chi(G) - 1$$
  Dit impliceert dat $HGP(G) = 2n-1$ dan en slechts dan als $G = K_n$ (aangezien $\chi(K_n)=n$).
• Propositie 2.2: Een relatie met het klassieke getal: $HGP(G) < \chi(G)(HG(G) + 1)$.
• Corollary 2.3: Een bovengrens gebaseerd op het maximale graad $\Delta(G)$: $HGP(G) < \lceil e\Delta(G) \rceil (\Delta(G) + 1)$.

C. Bomen (Trees)

• Stelling 1.3: Voor elke boom $T$ met $n \geq 3$ vertices geldt:
  $$HGP(T) = 4$$
• Details: De auteurs tonen aan dat voor de pad $P_3$ (3 vertices) de waarde 4 is. Via een inductief argument (Lemma 4.2 en Corollary 4.3) wordt bewezen dat het verwijderen van een blad (graad 1) de waarde niet verandert zolang de waarde $\geq 5$ is, maar voor bomen is de waarde begrensd door 4.

D. Boekgrafiek (Book Graphs)

• Een boekgraaf $B_{k,n}$ bestaat uit een clique van grootte $k$ (de "ruggengraat") verbonden met een onafhankelijke set van grootte $n$ (de "pagina's").
• Stelling 1.4: Als $n > e^{2k}$, dan geldt een scherpe bovengrens die afhangt van $n$ en $k$.
• Stelling 5.2: Als $k = O(n^{1-\varepsilon})$, dan is $HGP(B_{k,n}) = O(n / \ln n)$. Dit staat in contrast met het klassieke geval waar $HG(B_{k,n})$ constant blijft voor vaste $k$ en grote $n$.

E. Kleine Grafen

De auteurs hebben exacte waarden of nauwkeurige grenzen bepaald voor alle verbonden grafen met maximaal 5 vertices (zie Tabel 1 in het artikel):

• K1: 1
• K2: 3
• P3: 4
• K3: 5
• C4: 4
• K4: 7
• K5: 9
• Voor andere grafen (zoals $C_5$, $K_{2,3}$, "House", "Wheel") worden intervallen gegeven (bijv. $4 \leq HGP(C_5) \leq 7$).

4. Significatie en Toekomstperspectief

• Theoretische bijdrage: Het artikel vestigt een nieuw onderzoeksgebied binnen de combinatoriek en speltheorie. Het toont aan dat de beperking tot juiste kleuringen de complexiteit en de mogelijke waarden van het gokgetal aanzienlijk verandert.
• Contrast met klassiek spel: De resultaten tonen aan dat $HGP(G)$ vaak veel hoger is dan $HG(G)$ (bijv. bij cliques), maar dat de structuur van de graaf (zoals bij bomen) de waarde kan beperken tot een constante.
• Open vragen: De auteurs formuleren belangrijke open problemen:
  1. Is $HGP(G)$ begrensd door een lineaire functie van de maximale graad $\Delta(G)$? (Voor het klassieke spel geldt $HG(G) \leq e\Delta(G)$).
  2. Wat zijn de exacte waarden voor cycli, wielen en windmolengrafen?
  3. Wat is het maximum van $HGP(B_{k,n})$ als $n \to \infty$ voor vaste $k$?
  4. Hoe verandert het getal als men edges verwijdert uit een volledige graaf?

Conclusie

Dit werk biedt een grondige analyse van het hoedgokspel onder de restrictie van juiste kleuringen. Het levert exacte formules voor volledige grafen en bomen, verbeterde bovengrenzen voor boekgrafiek, en een uitgebreide dataset voor kleine grafen via ILP. De resultaten suggereren dat de interactie tussen de structuur van de graaf en de beperkingen van de kleuring leidt tot rijke en soms verrassende wiskundige patronen die verschillen van het klassieke geval.