pariteitsstelling

Pariteitsstelling, of pariteitstelling, is een term uit de wiskunde die verwijst naar uitspraken die berusten op pariteit: het onderscheid tussen even en oneven. Vaak gaat het om stellingen die aantonen dat een bepaalde hoeveelheid of configuratie uitsluitend onder een bepaalde pariteit kan voorkomen.

Kenmerkend zijn pariteitsargumenten: door objecten in paren te koppelen of door een kleuringsregel toe te passen, wordt de totale telling of het bestaan van een constructie beperkt tot een bepaalde pariteit. Pariteit kan invarianten opleveren die niet veranderen onder bewerkingen die in het probleem voorkomen.

Voorbeelden: Handshake-lemma in de grafentheorie stelt dat in elke eindige graaf het aantal knopen met een oneven graad even is. Een bekend akoestisch en visueel voorbeeld is de domino-tiling van een schaakbord: als twee tegenoverliggende hoeken van een bord verwijderd zijn en deze vakjes dezelfde kleur hebben, kan het bord niet volledig worden bedekt met domino’s, omdat elke domino één wit en één zwart vakje bedekt. Ook in de theorie van permutaties speelt pariteit een rol: de parity van een permutatie bepaalt of deze even of oneven is, en de signatuur daarvan vormt een homomorfie van de symmetrische groep naar {+1, -1}.

Toepassingen van pariteitsstellingen liggen onder meer in het aantonen van onmogelijke constructies, het tellen van objecten (het aantal oplossingen is bijvoorbeeld even of oneven), en het afdwingen van invarianten in bewijzen en algoritmen.

Zie ook: Pariteit, Pariteitsargument, Handshake-lemma, Permutaties, Grafentheorie.