Satz von Rado

Der Satz v​on Rado (englisch Rado's theorem o​der Rado's transversal theorem) i​st ein Lehrsatz d​er Matroidtheorie u​nd gehört a​ls solcher i​n das Gebiet d​er Diskreten Mathematik. Er g​eht auf e​ine Arbeit d​es deutschen Mathematikers Richard Rado a​us dem Jahre 1942 zurück u​nd stellt e​ine weitreichende Verallgemeinerung d​es berühmten Heiratssatzes v​on Philip Hall dar.[1][2][3][4][3][5][6]

Formulierung des Satzes

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

Gegeben seien eine nichtleere endliche Grundmenge ${\displaystyle E}$ und darauf ein Matroid ${\displaystyle M}$ mit der Rangfunktion ${\displaystyle r\colon {\mathcal {P}}(E)\to \mathbb {N} _{0}}$.

Weiter gegeben seien eine nichtleere endliche Indexmenge ${\displaystyle I}$ und dazu eine Mengenfamilie ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$ von ${\displaystyle E}$-Teilmengen ${\displaystyle A_{i}\subseteq E}$.

Dann sind folgende Aussagen äquivalent:

(1) Die Mengenfamilie ${\displaystyle {\mathcal {A}}}$ besitzt eine Transversale, die in ${\displaystyle M}$ eine unabhängige Menge ist.

(2) Jede Teilmenge ${\displaystyle J\subseteq I}$ erfüllt in Hinblick auf die Rangfunktion ${\displaystyle r}$ die Ungleichung  ${\displaystyle r{\bigl (}A(J){\bigr )}\geq |J|}$.

Erläuterungen und Anmerkungen

• Eine Teilmenge ${\displaystyle T\subseteq E}$ ist eine Transversale[13] der Mengenfamilie ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$, wenn es eine bijektive Abbildung ${\displaystyle \chi \colon T\to I}$ gibt derart, dass für jedes ${\displaystyle t\in T}$ stets ${\displaystyle t\in A_{\chi (t)}}$ gilt.
• In der Matroidtheorie ist ${\displaystyle A(J)}$ für ein ${\displaystyle J\subseteq I}$ eine abkürzende Schreibung, wobei stets ${\displaystyle A(J)=\bigcup _{j\in J}{A_{j}}}$ 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 ${\displaystyle m}$ der Teilmengen ${\displaystyle A_{i}\subseteq E\;(m\in \mathbb {N} ,1\leq m\leq |I|)}$ eine in ${\displaystyle M}$ unabhängige Menge mit mindestens ${\displaystyle m}$ Elementen umfasst.[7][10][12]
• Fallen die Rangfunktion ${\displaystyle r}$ und die Anzahlfunktion ${\displaystyle |\cdot |}$ zusammen und sind damit alle Teilmengen ${\displaystyle S\subseteq E}$ 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 ${\displaystyle E}$ 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.

Folgerung

Aus d​em Satz v​on Rado lassen s​ich viele Folgerungen gewinnen; s​o etwa d​ie folgende:[15][16][17]

Gegeben seien eine nichtleere endliche Grundmenge ${\displaystyle E}$ und darauf zwei nichtleere endliche Mengenfamilien ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$ und ${\displaystyle {\mathcal {B}}=(B_{i})_{i\in I}}$ von Teilmengen ${\displaystyle A_{i},B_{i}\subseteq E}$ über einer gegebenen endlichen Indexmenge ${\displaystyle I\neq \emptyset }$.

Dann gilt:

Die beiden Mengenfamilien ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ besitzen eine gemeinsame Transversale genau dann, wenn für je zwei beliebige Indexteilmengen ${\displaystyle J,K\subseteq I}$ die Ungleichung  ${\displaystyle |A(J)\cap B(K)|\geq |J|+|K|-|I|}$ erfüllt ist.

Anwendung

Als Anwendung d​er obigen Folgerung erhält m​an ein Resultat über endliche Gruppen:[18]

Gegeben seien eine endliche Gruppe ${\displaystyle G}$ und darin eine Untergruppe ${\displaystyle H}$ vom Index ${\displaystyle \textstyle m=(G\colon H)={\frac {|G|}{|H|}}}$.

Dann gibt es zu den Links- und Rechtsnebenklassen von ${\displaystyle G}$ nach ${\displaystyle H}$ ein gemeinsames ${\displaystyle m}$-Tupel ${\displaystyle (z_{1},\ldots ,z_{m})}$ von Gruppenelementen mit

${\displaystyle z_{1}H\;{\dot {\cup }}\;z_{2}H\;{\dot {\cup }}\;\ldots \;{\dot {\cup }}\;z_{m}H=G=Hz_{1}\;{\dot {\cup }}\;Hz_{2}\;{\dot {\cup }}\;\ldots \;{\dot {\cup }}\;Hz_{m}}$ .

Literatur

• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1 (MR0460127).
• Dieter Jungnickel: Transversaltheorie (= Mathematik und ihre Anwendungen in Physik und Technik. Band 39). Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig 1982 (MR0706076).
• Bernhard Korte, László Lovász, Rainer Schrader: Greedoids (= Algorithms and Combinatorics. Band 4). Springer Verlag, Berlin, Heidelberg 1991, ISBN 3-540-18190-3 (MR1183735).
• James Oxley: Matroid Theory (= Oxford Graduate Texts in Mathematics. Band 21). 2. Auflage. Oxford University Press, Oxford 2011, ISBN 978-0-19-960339-8 (MR2849819).
• Richard Rado: A theorem on independence relations. In: The Quarterly Journal of Mathematics. Oxford. Second Series. Band 13, 1942, S. 83–89 (MR0008250).
• D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. Band 8). Academic Press, London, New York, San Francisco 1976, ISBN 0-12-744050-X (MR0427112).
• Robin J. Wilson: Einführung in die Graphentheorie. Aus dem Englischen übersetzt von Gerd Wegner (= Moderne Mathematik in elementarer Darstellung. Band 15). Vandenhoeck & Ruprecht, Göttingen 1976 (MR0434854 – Englische Vorlage: Introduction to Graph Theory, Longman, London 1975).

Einzelnachweise

1. Dieter Jungnickel: Transversaltheorie. 1982, S. 136 ff
2. James Oxley: Matroid Theory. 2011, S. 411 ff
3. 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. Jungnickel, op. cit., S. 136
8. Oxley, op. cit., S. 412
9. Welsh, op. cit., S. 98
10. Wilson, op. cit., S. 160
11. Korte/Lovász/Schrader, op. cit., S. 16
12. 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