Satz von Bondy

Der Satz von Bondy in der Mathematik, Der Satz von Bondy ist eine Grenze für die Anzahl der Elemente, die erforderlich sind, um die Mengen in einer Mengenfamilie voneinander zu unterscheiden. Es gehört zum Gebiet der Kombinatorik, und ist nach John Adrian Bondy benannt, wer es veröffentlicht hat 1972.[1] Inhalt 1 Aussage 2 Beispiel 3 Lerntheoretische Anwendung 4 Notes Statement The theorem is as follows: Sei X eine Menge mit n Elementen und sei A1, A2, ..., An verschiedene Teilmengen von X sein. Then there exists a subset S of X with n − 1 elements such that the sets Ai ∩ S are all distinct.

Mit anderen Worten, wenn wir eine haben 0-1 Matrix mit n Zeilen und n Spalten, so dass jede Zeile verschieden ist, we can remove one column such that the rows of the resulting n × (n- 1) Matrix sind verschieden.[2][3] Example Consider the 4 × 4 Matrix {Anzeigestil {Start{bMatrix}1&1&0&1\0&1&0&1\0&0&1&1\0&1&1&0end{bMatrix}}} wobei alle Zeilen paarweise verschieden sind. Wenn wir löschen, zum Beispiel, die erste Spalte, die resultierende Matrix {Anzeigestil {Start{bMatrix}1&0&1\1&0&1\0&1&1\1&1&0end{bMatrix}}} hat diese Eigenschaft nicht mehr: die erste Reihe ist identisch mit der zweiten Reihe. Nichtsdestotrotz, nach dem Satz von Bondy wissen wir, dass wir immer eine Spalte finden können, die gelöscht werden kann, ohne identische Zeilen einzufügen. In diesem Fall, Wir können die dritte Spalte löschen: all rows of the 3 × 4 Matrix {Anzeigestil {Start{bMatrix}1&1&1\0&1&1\0&0&1\0&1&0end{bMatrix}}} sind verschieden. Eine andere Möglichkeit wäre gewesen, die vierte Spalte zu löschen.

Learning theory application From the perspective of computational learning theory, Der Satz von Bondy kann wie folgt umformuliert werden:[4] Sei C eine Konzeptklasse über einem endlichen Gebiet X. Dann gibt es eine Teilmenge S von X mit der höchsten Größe |C| − 1 such that S is a witness set for every concept in C.

Dies impliziert, dass jede endliche Konzeptklasse C ihre Lehrdimension durch begrenzt hat |C| − 1.

Anmerkungen ^ Bondy, J. EIN. (1972), "Induzierte Teilmengen", Zeitschrift für kombinatorische Theorie, Serie B, 12: 201–202, doi:10.1016/0095-8956(72)90025-1, HERR 0319773. ^ Yukna, Stase (2001), Extremale Kombinatorik mit Anwendungen in der Informatik, Springer, ISBN 978-3-540-66313-3, Abschnitt 12.1. ^ Klote, Peter; Remme, Jeffrey B. (1995), Machbare Mathematik II, Birkhäuser, ISBN 978-3-7643-3675-2, Abschnitt 4.1. ^ Kushilevitz, Eyal; linear, Nathan; Rabinowitsch, Juri; Saks, Michael (1996), "Zeugensätze für Familien binärer Vektoren", Zeitschrift für kombinatorische Theorie, Serie A, 73 (2): 376–380, doi:10.1016/S0097-3165(96)80015-X, HERR 1370141. Kategorien: Computational Learning TheoremeTheoreme der Kombinatorik