„Satz von Rado“ – Versionsunterschied
Zur Navigation springen
Zur Suche springen
[gesichtete Version] | [gesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
Weitere Literatur- und Quellenangaben. Anwendung der Folgerung. Kleinere Anpassungen. |
|||
Zeile 1: | Zeile 1: | ||
Der '''Satz von Rado''' ({{enS|Rado's theorem oder Rado's transversal theorem}}) ist ein [[Lehrsatz]] der [[Matroid]]theorie und gehört als solcher in das [[Teilgebiete der Mathematik|Gebiet]] der [[Diskrete Mathematik|Diskreten Mathematik]]. Er geht auf eine Arbeit des deutschen [[Mathematiker]]s [[Richard Rado]] aus dem Jahre 1942 zurück und stellt eine weitreichende Verallgemeinerung des berühmten [[Heiratssatz]]es von [[Philip Hall]] dar.<ref name="DJ-001">Dieter Jungnickel: ''Transversaltheorie.'' 1982, S. 136 ff</ref><ref name="JO-001">James Oxley: ''Matroid Theory.'' 2011, S. 411 ff</ref><ref name="DJAW-001">D. J. A. Welsh: ''Matroid Theory.'' 1976, S. 97 ff</ref><ref name="RJW-001">Robin J. Wilson: ''Einführung in die Graphentheorie.'' 1976, S. 159 ff</ref><ref name="DJAW-001">D. J. A. Welsh: ''Matroid Theory.'' 1976, S. 97 ff</ref><ref name="BK-LL-RS-001">Korte/Lovász/Schrader: ''Greedoids.'' 1991, S. 1 ff, S. 16</ref> |
Der '''Satz von Rado''' ({{enS|Rado's theorem oder Rado's transversal theorem}}) ist ein [[Lehrsatz]] der [[Matroid]]theorie und gehört als solcher in das [[Teilgebiete der Mathematik|Gebiet]] der [[Diskrete Mathematik|Diskreten Mathematik]]. Er geht auf eine Arbeit des deutschen [[Mathematiker]]s [[Richard Rado]] aus dem Jahre 1942 zurück und stellt eine weitreichende Verallgemeinerung des berühmten [[Heiratssatz]]es von [[Philip Hall]] dar.<ref name="DJ-001">Dieter Jungnickel: ''Transversaltheorie.'' 1982, S. 136 ff</ref><ref name="JO-001">James Oxley: ''Matroid Theory.'' 2011, S. 411 ff</ref><ref name="DJAW-001">D. J. A. Welsh: ''Matroid Theory.'' 1976, S. 97 ff</ref><ref name="RJW-001">Robin J. Wilson: ''Einführung in die Graphentheorie.'' 1976, S. 159 ff</ref><ref name="DJAW-001">D. J. A. Welsh: ''Matroid Theory.'' 1976, S. 97 ff</ref><ref name="BK-LL-RS-001">Korte/Lovász/Schrader: ''Greedoids.'' 1991, S. 1 ff, S. 16</ref><ref name="MA-001">Martin Aigner: ''Kombinatorik II.'' 1976, S. 244 ff</ref> |
||
== Formulierung des Satzes == |
== Formulierung des Satzes == |
||
Der Satz lässt sich folgendermaßen formulieren:<ref name="DJ-002">Jungnickel, op. cit., S. 136</ref><ref name="JO-002">Oxley, op. cit., S. 412</ref><ref name="DJAW-002">Welsh, op. cit., S. 98</ref><ref name="RJW-002">Wilson, op. cit., S. 160</ref><ref name="BK-LL-RS-002">Korte/Lovász/Schrader, op. cit., S. 16</ref> |
Der Satz lässt sich folgendermaßen formulieren:<ref name="DJ-002">Jungnickel, op. cit., S. 136</ref><ref name="JO-002">Oxley, op. cit., S. 412</ref><ref name="DJAW-002">Welsh, op. cit., S. 98</ref><ref name="RJW-002">Wilson, op. cit., S. 160</ref><ref name="BK-LL-RS-002">Korte/Lovász/Schrader, op. cit., S. 16</ref><ref name="MA-002">Aigner, op. cit., S. 246</ref> |
||
: ''Gegeben seien eine [[nichtleer]]e [[Endliche Menge|endlich]]e [[Grundmenge]] <math>E</math> und darauf ein [[Matroid]] <math>M</math> mit der Rangfunktion <math>r \colon \mathcal P(E) \to \N_0</math>.'' |
: ''Gegeben seien eine [[nichtleer]]e [[Endliche Menge|endlich]]e [[Grundmenge]] <math>E</math> und darauf ein [[Matroid]] <math>M</math> mit der Rangfunktion <math>r \colon \mathcal P(E) \to \N_0</math>.'' |
||
: ''Weiter gegeben seien eine nichtleere endliche [[Indexmenge (Mathematik)|Indexmenge]] <math>I</math> und dazu eine [[Mengenfamilie]] <math>\mathcal A = (A_i)_{i \in I}</math> von <math>E</math>-[[Teilmenge]]n <math>A_i \subseteq E</math>.'' |
: ''Weiter gegeben seien eine nichtleere endliche [[Indexmenge (Mathematik)|Indexmenge]] <math>I</math> und dazu eine [[Mengenfamilie]] <math>\mathcal A = (A_i)_{i \in I}</math> von <math>E</math>-[[Teilmenge]]n <math>A_i \subseteq E</math>.'' |
||
Zeile 12: | Zeile 12: | ||
* Eine Teilmenge <math>T \subseteq E</math> ist eine ''Transversale''<ref>Anderswo, etwa in der Geometrie, hat der Begriff der [[Transversale]] eine andere Bedeutung.</ref> der Mengenfamilie <math>\mathcal A</math>, wenn es eine [[bijektive Abbildung]] <math>\chi \colon T \to I</math> gibt derart, dass für jedes <math>t \in T</math> stets <math>t \in A_{\chi(t)}</math> gilt. |
* Eine Teilmenge <math>T \subseteq E</math> ist eine ''Transversale''<ref>Anderswo, etwa in der Geometrie, hat der Begriff der [[Transversale]] eine andere Bedeutung.</ref> der Mengenfamilie <math>\mathcal A</math>, wenn es eine [[bijektive Abbildung]] <math>\chi \colon T \to I</math> gibt derart, dass für jedes <math>t \in T</math> stets <math>t \in A_{\chi(t)}</math> gilt. |
||
* In der Matroidtheorie ist <math>A(J)</math> für ein <math>J \subseteq I</math> eine abkürzende Schreibung, wobei stets <math>A(J)=\bigcup_{j\in J} {A_j}</math> gilt. |
* In der Matroidtheorie ist <math>A(J)</math> für ein <math>J \subseteq I</math> eine abkürzende Schreibung, wobei stets <math>A(J)=\bigcup_{j\in J} {A_j}</math> gilt. |
||
* Die obige Bedingung '''(2)''' nennen manche Autoren auch – in Analogie zur ''Hall-Bedingung'' |
* 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 <math>m</math> der Teilmengen <math>A_i \subseteq E \;(m \in \N, 1 \leq m \leq |I|)</math> eine in <math>M</math> unabhängige Menge mit mindestens <math>m</math> [[Element (Mathematik)|Elementen]] [[Obermenge|umfasst]].<ref name="DJ-002" /><ref name="RJW-002" /><ref name="MA-002" /> |
||
* Fallen die Rangfunktion <math>r</math> und die [[Mächtigkeit (Mathematik)#Mächtigkeit bei endlichen_Mengen|Anzahlfunktion]] <math>| \cdot |</math> zusammen und sind damit alle Teilmengen <math>S \subseteq E</math> unabhängig, so fällt die Rado-Bedingung mit der Hall-Bedingung zusammen und man erhält den Heiratssatz.<ref name="DJAW-002" /> |
* Fallen die Rangfunktion <math>r</math> und die [[Mächtigkeit (Mathematik)#Mächtigkeit bei endlichen_Mengen|Anzahlfunktion]] <math>| \cdot |</math> zusammen und sind damit alle Teilmengen <math>S \subseteq E</math> unabhängig, so fällt die Rado-Bedingung mit der Hall-Bedingung zusammen und man erhält den Heiratssatz.<ref name="DJAW-002" /> |
||
* Der Satz von Rado lässt sich ausdehnen auf den ''transfiniten Fall'', der ein [[unendliches Matroid]] voraussetzt, also eine Matroidstruktur mit [[unendlich]]er Grundmenge <math>E</math> und zusätzlichen Endlichkeitsbedingungen.<ref name="DJ-003">Jungnickel, op. cit., S. 138 ff</ref> |
* Der Satz von Rado lässt sich ausdehnen auf den ''transfiniten Fall'', der ein [[unendliches Matroid]] voraussetzt, also eine Matroidstruktur mit [[unendlich]]er Grundmenge <math>E</math> und zusätzlichen Endlichkeitsbedingungen.<ref name="DJ-003">Jungnickel, op. cit., S. 138 ff</ref> |
||
Zeile 18: | Zeile 18: | ||
== Folgerung == |
== Folgerung == |
||
Aus dem Satz von Rado lässt sich viele Folgerungen gewinnen; so etwa die folgende:<ref name="DJAW-003">Welsh, op. cit., S. 106 ff</ref><ref name="RJW-003">Wilson, op. cit., S. 161 ff</ref> |
Aus dem Satz von Rado lässt sich viele Folgerungen gewinnen; so etwa die folgende:<ref name="DJAW-003">Welsh, op. cit., S. 106 ff</ref><ref name="RJW-003">Wilson, op. cit., S. 161 ff, S. 130</ref><ref name="MA-003">Aigner, op. cit., S. 251</ref> |
||
: ''Gegeben seien eine nichtleere endliche Grundmenge <math>E</math> und darauf zwei nichtleere endliche Mengenfamilien <math>\mathcal A = (A_i)_{i \in I}</math> und <math>\mathcal B = (B_i)_{i \in I}</math> von Teilmengen <math>A_i, B_i \subseteq E</math> über einer gegebenen Indexmenge <math>I \neq \emptyset</math>.'' |
: ''Gegeben seien eine nichtleere endliche Grundmenge <math>E</math> und darauf zwei nichtleere endliche Mengenfamilien <math>\mathcal A = (A_i)_{i \in I}</math> und <math>\mathcal B = (B_i)_{i \in I}</math> von Teilmengen <math>A_i, B_i \subseteq E</math> über einer gegebenen endlichen Indexmenge <math>I \neq \emptyset</math>.'' |
||
: '''''Dann gilt:''''' |
: '''''Dann gilt:''''' |
||
:: '' |
:: ''Die beiden Mengenfamilien <math>\mathcal A</math> und <math>\mathcal B</math> besitzen eine '''gemeinsame Transversale''' genau dann, wenn <math>I</math> für je zwei beliebige Indexteilmengen <math>J,K \subseteq I</math> die Ungleichung <math>| A(J) \cap B(K)| \geq |J|+|K|-|I|</math> erfüllt ist.'' |
||
=== Anwendung === |
|||
Als Anwendung der obigen Folgerung erhält man ein Resultat über [[endliche Gruppe]]n:<ref name="RJW-004">Wilson, op. cit., S. 131</ref> |
|||
: ''Gegeben seien eine endliche [[Gruppe (Mathematik)|Gruppe]] <math>G</math> und darin eine [[Untergruppe]] <math>H</math> vom [[Index (Gruppentheorie)|Index]] <math>m=(G\colon H) = \frac{|G|}{|H|}</math>.'' |
|||
: ''Dann gibt es zu den [[Gruppentheorie#Nebenklassen|Links- und Rechtsnebenklassen]] von <math>G</math> nach <math>H</math> ein gemeinsames <math>m</math>-[[Tupel]] <math>(z_1, \ldots, z_m)</math> von Gruppenelementen mit'' |
|||
:: <math>z_1 H \;\dot{\cup}\; z_2 H \;\dot{\cup}\; \ldots \;\dot{\cup}\; z_m H = G = H z_1 \;\dot{\cup}\; H z_2 \;\dot{\cup}\; \ldots \;\dot{\cup}\; H z_m </math> . |
|||
== Literatur == |
== Literatur == |
||
* {{Literatur |
|||
|Autor=[[Martin Aigner]] |
|||
|Titel=Kombinatorik II: Matroide und Transversaltheorie |
|||
|Reihe=Hochschultext |
|||
|Verlag=[[Springer_Science%2BBusiness_Media|Springer Verlag]] |
|||
|Ort=Berlin (u. a.) |
|||
|Jahr=1976 |
|||
|ISBN=3-540-07949-1 |
|||
|Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Aigner&s5=Kombinatorik&s6=&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=1&mx-pid=460127 MR0460127]}} |
|||
* {{Literatur |
* {{Literatur |
||
|Autor=[[Dieter Jungnickel]] |
|Autor=[[Dieter Jungnickel]] |
||
Zeile 38: | Zeile 53: | ||
|Reihe=Algorithms and Combinatorics |
|Reihe=Algorithms and Combinatorics |
||
|BandReihe=4 |
|BandReihe=4 |
||
|Verlag= |
|Verlag=Springer Verlag |
||
|Ort=Berlin, Heidelberg |
|Ort=Berlin, Heidelberg |
||
|Datum=1991 |
|Datum=1991 |
Version vom 16. Juli 2018, 21:05 Uhr
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
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
- 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]
- Der hiesige Satz hat nichts mit den auf den ungarischen Mathematiker Tibor Radó zurückgehenden Radó'schen Sätzen in der Analysis zu tun.
Folgerung
Aus dem Satz von Rado lässt 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.
Anwendung
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
- .
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
- ↑ Dieter Jungnickel: Transversaltheorie. 1982, S. 136 ff
- ↑ James Oxley: Matroid Theory. 2011, S. 411 ff
- ↑ a b D. J. A. Welsh: Matroid Theory. 1976, S. 97 ff
- ↑ Robin J. Wilson: Einführung in die Graphentheorie. 1976, S. 159 ff
- ↑ Korte/Lovász/Schrader: Greedoids. 1991, S. 1 ff, S. 16
- ↑ Martin Aigner: Kombinatorik II. 1976, S. 244 ff
- ↑ a b Jungnickel, op. cit., S. 136
- ↑ Oxley, op. cit., S. 412
- ↑ a b Welsh, op. cit., S. 98
- ↑ a b Wilson, op. cit., S. 160
- ↑ Korte/Lovász/Schrader, op. cit., S. 16
- ↑ a b Aigner, op. cit., S. 246
- ↑ Anderswo, etwa in der Geometrie, hat der Begriff der Transversale eine andere Bedeutung.
- ↑ Jungnickel, op. cit., S. 138 ff
- ↑ Welsh, op. cit., S. 106 ff
- ↑ Wilson, op. cit., S. 161 ff, S. 130
- ↑ Aigner, op. cit., S. 251
- ↑ Wilson, op. cit., S. 131