Die Ungleichung von Fisher (, ) ist eine Ungleichung, die im Übergangsfeld zwischen der Endlichen Geometrie und der Theorie der Hypergraphen angesiedelt ist. Sie formuliert eine notwendige Bedingung für die Größenbeziehungen zweier Anzahlen bei gewissen endlichen Mengensystemen. Es handelt sich um ein grundlegendes Resultat, welches auf eine Publikation des Statistikers Ronald Aylmer Fisher aus dem Jahre 1940 zurückgeht.
Formulierung Die Ungleichung lässt sich in einer allgemeinen Fassung folgendermaßen formulieren:
Gegeben seien drei natürliche Zahlen mit und dazu die Grundmenge sowie paarweise verschiedene Teilmengen .
Hierbei soll für je zwei verschiedene Indizes die zugehörige Schnittmenge durchgängig die Gleichung erfüllen.Mit wird die Mächtigkeit einer Menge bezeichnet. Im Falle einer endlichen Menge ist diese Mächtigkeit gleich der Anzahl der in enthaltenen Elemente.
Dann gilt die Ungleichung .Für den Beweis identifiziert man die Teilmengen mit den ihnen zugehörigen Inzidenzvektoren im euklidischen Raum . Die Fisher-Ungleichung ergibt sich dann direkt unter Anwendung der aus der Linearen Algebra bekannten Tatsache, dass in einem Vektorraum die Mächtigkeit einer aus lauter linear unabhängigen Vektoren bestehenden Teilmenge stets durch die Dimension des Vektorraums nach oben begrenzt ist. (Vgl. Monographie von Jukna, a. a O.!)
Korollar Aus der oben dargestellten allgemeinen Fassung der Fisher’schen Ungleichung ergibt sich unmittelbar die bekannte Fisher-Ungleichung in der Theorie der Blockpläne:
In jedem Blockplan besteht die Ungleichung , ist also die Anzahl der Blöcke mindestens so groß wie die Anzahl der Punkte.Man gewinnt diese Fassung der Ungleichung, indem man und setzt, die Blockmenge ebenso wie die Punktmenge durchnummeriert:
und dann mit
weiter für
definiert.
Wegen der Blockplaneigenschaft ergibt sich nun für je zwei verschiedene Indizes die Gleichung
und mit weiter aus der allgemeinen Fassung der Ungleichung sogleich die Ungleichung für Blockpläne.
Dies gilt in gleicher Weise für jedes PBD, bei dem keiner der Blöcke alle Punkte enthält.
Der Satz von de Bruijn und Erdős In den hiesigen Kontext gehört ein weiterer verwandter Satz, der im Jahre 1948 von Nicolaas Govert de Bruijn und Paul Erdős geliefert wurde:
Gegeben seien eine nichtleere endliche Menge von Punkten und dazu ein Teilmengensystem Mit bezeichnet man die Potenzmenge einer Menge . von Blöcken derart, dass eine Inzidenzgeometrie vorliegt, in der jeder Block stets Punkte enthält.
Dann hat man die Ungleichung
und es gilt die Gleichheit
genau für den Fall, dass je zwei verschiedene Blöcke exakt einen Punkt gemeinsam haben.
Das Resultat von Ray-Chaudhuri und Wilson Im Jahre 1975 publizierten die beiden Mathematiker Dijen K. Ray-Chaudhuri und Richard M. Wilson eine der Ungleichung von Fisher verwandte Ungleichung, mit der die zu Grunde liegende Fragestellung in einen allgemeineren Zusammenhang gebracht wird und die folgendermaßen formuliert werden kann:
Gegeben seien zwei natürliche Zahlen und mit sowie eine endliche Menge nichtnegativer ganzer Zahlen. Gegeben sei weiter die Grundmenge und dazu ein Mengensystem derart, dass jedes aus exakt Elementen besteht. Dabei gelte und weiter, dass für je zwei verschiedene deren Schnittmenge die Beziehung erfüllen möge.
Dann besteht die Ungleichung .
Der Fall der nicht-uniformen Mengensysteme Die naheliegende Frage, ob das Resultat von Ray-Chaudhuri und Wilson ein Analogon hat für den Fall, dass die Uniformität der betrachteten Mengensysteme ausgeklammert wird, haben im Jahre 1981 Wilson und Peter Frankl beantwortet:
Gegeben seien eine natürliche Zahl sowie eine endliche Teilmenge der nichtnegativen ganzen Zahlen. Gegeben sei weiter eine Grundmenge der Mächtigkeit und dazu ein Mengensystem derart, dass für je zwei verschiedene deren Schnittmenge die Beziehung erfüllen möge.
Dann besteht die Ungleichung .
Siehe auch Blockplan Satz von de Bruijn-Erdős (Inzidenzgeometrie)
Quellen und Literatur
Einzelnachweise
Anmerkungen und Hinweise
Fisher, Ungleichung von Fisher, Ungleichung von Fisher, Ungleichung von