Satz von Rado

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Satz von Rado (englisch Rado's theorem oder Rado's transversal theorem) ist ein Lehrsatz der Matroidtheorie und gehört als solcher in das Gebiet der Diskreten Mathematik. Er geht auf eine Arbeit des deutschen Mathematikers Richard Rado aus dem Jahre 1942 zurück und stellt eine weitreichende Verallgemeinerung des berühmten Heiratssatzes von Philip Hall dar.[1][2][3][4][3][5][6]

Formulierung des Satzes

[Bearbeiten | Quelltext bearbeiten]

Der Satz lässt sich folgendermaßen formulieren:[7][8][9][10][11][12]

Gegeben seien eine nichtleere endliche Grundmenge und darauf ein Matroid mit der Rangfunktion .
Weiter gegeben seien eine nichtleere endliche Indexmenge und dazu eine Mengenfamilie von -Teilmengen .
Dann sind folgende Aussagen äquivalent:
(1) Die Mengenfamilie besitzt eine Transversale, die in eine unabhängige Menge ist.
(2) Jede Teilmenge erfüllt in Hinblick auf die Rangfunktion die Ungleichung  .

Erläuterungen und Anmerkungen

[Bearbeiten | Quelltext bearbeiten]
  • Eine Teilmenge ist eine Transversale[13] der Mengenfamilie , wenn es eine bijektive Abbildung gibt derart, dass für jedes stets gilt.
  • In der Matroidtheorie ist für ein eine abkürzende Schreibung, wobei stets gilt.
  • Die obige Bedingung (2) nennen manche Autoren auch – in Analogie zur Hall-Bedingung (bzw. zu Hall’s Bedingung) im Heiratssatz – die Rado-Bedingung oder Rado’s Bedingung. Sie besagt, dass die Vereinigungsmenge von je der Teilmengen eine in unabhängige Menge mit mindestens Elementen umfasst.[7][10][12]
  • Fallen die Rangfunktion und die Anzahlfunktion zusammen und sind damit alle Teilmengen unabhängig, so fällt die Rado-Bedingung mit der Hall-Bedingung zusammen und man erhält den Heiratssatz.[9]
  • Der Satz von Rado lässt sich ausdehnen auf den transfiniten Fall, der ein unendliches Matroid voraussetzt, also eine Matroidstruktur mit unendlicher Grundmenge und zusätzlichen Endlichkeitsbedingungen.[14]
  • Auf Richard Rado geht ein weiterer wichtiger Lehrsatz zurück, nämlich der Rado'sche Satz in der Ramseytheorie. Es ist in diesem Zusammenhang auch festzuhalten, dass der hiesige Satz nicht mit den auf den ungarischen Mathematiker Tibor Radó zurückgehenden Radó'schen Sätzen in der Analysis verwechselt werden sollte.

Aus dem Satz von Rado lassen sich viele Folgerungen gewinnen; so etwa die folgende:[15][16][17]

Gegeben seien eine nichtleere endliche Grundmenge und darauf zwei nichtleere endliche Mengenfamilien und von Teilmengen über einer gegebenen endlichen Indexmenge .
Dann gilt:
Die beiden Mengenfamilien und besitzen eine gemeinsame Transversale genau dann, wenn für je zwei beliebige Indexteilmengen die Ungleichung   erfüllt ist.

Als Anwendung der obigen Folgerung erhält man ein Resultat über endliche Gruppen:[18]

Gegeben seien eine endliche Gruppe und darin eine Untergruppe vom Index .
Dann gibt es zu den Links- und Rechtsnebenklassen von nach ein gemeinsames -Tupel von Gruppenelementen mit
.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Dieter Jungnickel: Transversaltheorie. 1982, S. 136 ff
  2. James Oxley: Matroid Theory. 2011, S. 411 ff
  3. a b D. J. A. Welsh: Matroid Theory. 1976, S. 97 ff
  4. Robin J. Wilson: Einführung in die Graphentheorie. 1976, S. 159 ff
  5. Korte/Lovász/Schrader: Greedoids. 1991, S. 1 ff, S. 16
  6. Martin Aigner: Kombinatorik II. 1976, S. 244 ff
  7. a b Jungnickel, op. cit., S. 136
  8. Oxley, op. cit., S. 412
  9. a b Welsh, op. cit., S. 98
  10. a b Wilson, op. cit., S. 160
  11. Korte/Lovász/Schrader, op. cit., S. 16
  12. a b Aigner, op. cit., S. 246
  13. Anderswo, etwa in der Geometrie, hat der Begriff der Transversale eine andere Bedeutung.
  14. Jungnickel, op. cit., S. 138 ff
  15. Welsh, op. cit., S. 106 ff
  16. Wilson, op. cit., S. 161 ff, S. 130
  17. Aigner, op. cit., S. 251
  18. Wilson, op. cit., S. 131