www.wikidata.de-de.nina.az

Satz von Rado Der englisch Rado s theorem oder Rado s transversal theorem ist ein Lehrsatz der Matroidtheorie und gehört

Satz von Rado

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.

Formulierung des Satzes Bearbeiten

Der Satz lässt sich folgendermaßen formulieren:

Erläuterungen und Anmerkungen Bearbeiten

  • Eine Teilmenge ist eine Transversale 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.
  • 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.
  • 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.
  • 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 Bearbeiten

Aus dem Satz von Rado lassen sich viele Folgerungen gewinnen; so etwa die folgende:

Anwendung Bearbeiten

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

Literatur Bearbeiten

  • 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 Bearbeiten

  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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Satz von Rado englisch Rado s theorem oder Rado s transversal theorem ist ein Lehrsatz der Matroidtheorie und gehort als solcher in das Gebiet der Diskreten Mathematik Er geht auf eine Arbeit des deutschen Mathematikers Richard Rado aus dem Jahre 1942 zuruck und stellt eine weitreichende Verallgemeinerung des beruhmten Heiratssatzes von Philip Hall dar 1 2 3 4 3 5 6 Inhaltsverzeichnis 1 Formulierung des Satzes 2 Erlauterungen und Anmerkungen 3 Folgerung 3 1 Anwendung 4 Literatur 5 EinzelnachweiseFormulierung des Satzes BearbeitenDer Satz lasst sich folgendermassen formulieren 7 8 9 10 11 12 Gegeben seien eine nichtleere endliche Grundmenge E displaystyle E nbsp und darauf ein Matroid M displaystyle M nbsp mit der Rangfunktion r P E N0 displaystyle r colon mathcal P E to mathbb N 0 nbsp Weiter gegeben seien eine nichtleere endliche Indexmenge I displaystyle I nbsp und dazu eine Mengenfamilie A Ai i I displaystyle mathcal A A i i in I nbsp von E displaystyle E nbsp Teilmengen Ai E displaystyle A i subseteq E nbsp Dann sind folgende Aussagen aquivalent 1 Die Mengenfamilie A displaystyle mathcal A nbsp besitzt eine Transversale die in M displaystyle M nbsp eine unabhangige Menge ist 2 Jede Teilmenge J I displaystyle J subseteq I nbsp erfullt in Hinblick auf die Rangfunktion r displaystyle r nbsp die Ungleichung r A J J displaystyle r bigl A J bigr geq J nbsp dd Erlauterungen und Anmerkungen BearbeitenEine Teilmenge T E displaystyle T subseteq E nbsp ist eine Transversale 13 der Mengenfamilie A Ai i I displaystyle mathcal A A i i in I nbsp wenn es eine bijektive Abbildung x T I displaystyle chi colon T to I nbsp gibt derart dass fur jedes t T displaystyle t in T nbsp stets t Ax t displaystyle t in A chi t nbsp gilt In der Matroidtheorie ist A J displaystyle A J nbsp fur ein J I displaystyle J subseteq I nbsp eine abkurzende Schreibung wobei stets A J j JAj displaystyle A J bigcup j in J A j nbsp 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 m displaystyle m nbsp der Teilmengen Ai E m N 1 m I displaystyle A i subseteq E m in mathbb N 1 leq m leq I nbsp eine in M displaystyle M nbsp unabhangige Menge mit mindestens m displaystyle m nbsp Elementen umfasst 7 10 12 Fallen die Rangfunktion r displaystyle r nbsp und die Anzahlfunktion displaystyle cdot nbsp zusammen und sind damit alle Teilmengen S E displaystyle S subseteq E nbsp unabhangig so fallt die Rado Bedingung mit der Hall Bedingung zusammen und man erhalt den Heiratssatz 9 Der Satz von Rado lasst sich ausdehnen auf den transfiniten Fall der ein unendliches Matroid voraussetzt also eine Matroidstruktur mit unendlicher Grundmenge E displaystyle E nbsp und zusatzlichen Endlichkeitsbedingungen 14 Auf Richard Rado geht ein weiterer wichtiger Lehrsatz zuruck namlich 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 Rado zuruckgehenden Rado schen Satzen in der Analysis verwechselt werden sollte Folgerung BearbeitenAus dem Satz von Rado lassen sich viele Folgerungen gewinnen so etwa die folgende 15 16 17 Gegeben seien eine nichtleere endliche Grundmenge E displaystyle E nbsp und darauf zwei nichtleere endliche Mengenfamilien A Ai i I displaystyle mathcal A A i i in I nbsp und B Bi i I displaystyle mathcal B B i i in I nbsp von Teilmengen Ai Bi E displaystyle A i B i subseteq E nbsp uber einer gegebenen endlichen Indexmenge I displaystyle I neq emptyset nbsp Dann gilt Die beiden Mengenfamilien A displaystyle mathcal A nbsp und B displaystyle mathcal B nbsp besitzen eine gemeinsame Transversale genau dann wenn fur je zwei beliebige Indexteilmengen J K I displaystyle J K subseteq I nbsp die Ungleichung A J B K J K I displaystyle A J cap B K geq J K I nbsp erfullt ist dd Anwendung Bearbeiten Als Anwendung der obigen Folgerung erhalt man ein Resultat uber endliche Gruppen 18 Gegeben seien eine endliche Gruppe G displaystyle G nbsp und darin eine Untergruppe H displaystyle H nbsp vom Index m G H G H displaystyle textstyle m G colon H frac G H nbsp Dann gibt es zu den Links und Rechtsnebenklassen von G displaystyle G nbsp nach H displaystyle H nbsp ein gemeinsames m displaystyle m nbsp Tupel z1 zm displaystyle z 1 ldots z m nbsp von Gruppenelementen mitz1H z2H zmH G Hz1 Hz2 Hzm 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 nbsp dd Literatur BearbeitenMartin 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 amp Portig K G Leipzig 1982 MR0706076 Bernhard Korte Laszlo Lovasz 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 Einfuhrung in die Graphentheorie Aus dem Englischen ubersetzt von Gerd Wegner Moderne Mathematik in elementarer Darstellung Band 15 Vandenhoeck amp Ruprecht Gottingen 1976 MR0434854 Englische Vorlage Introduction to Graph Theory Longman London 1975 Einzelnachweise Bearbeiten 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 Einfuhrung in die Graphentheorie 1976 S 159 ff Korte Lovasz 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 Lovasz 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 Abgerufen von https de wikipedia org w index php title Satz von Rado amp oldid 240827492