Bondys teoremi - Bondys theorem - Wikipedia

Matematikte, Bondy teoremi bir kümedeki kümeleri ayırt etmek için gereken öğe sayısına bağlıdır. set ailesi birbirinden. Alanına aittir kombinatorik ve adını almıştır John Adrian Bondy, 1972'de yayınlayan.[1]

Beyan

Teorem aşağıdaki gibidir:

İzin Vermek X ile set olmak n elemanlar ve izin ver Bir1, Bir2, ..., Birn farklı alt kümeleri olmak X. Sonra bir alt küme var S nın-nin X ile n - 1 öğe öyle ki setler Birben ∩ S hepsi farklı.

Diğer bir deyişle, 0-1 matris ile n satırlar ve n her satır ayrı olacak şekilde sütunlar, bir sütunu kaldırabiliriz, böylece ortaya çıkan satırlar n × (n - 1) matris farklıdır.[2][3]

Misal

4 × 4 matrisi düşünün

burada tüm satırlar çift olarak farklıdır. Örneğin, ilk sütunu silersek, sonuç matrisi

artık bu özelliğe sahip değildir: ilk satır ikinci satırla aynıdır. Bununla birlikte, Bondy'nin teoremine göre, herhangi bir özdeş satır eklemeden silinebilecek bir sütun bulabileceğimizi biliyoruz. Bu durumda, üçüncü sütunu silebiliriz: 3 × 4 matrisin tüm satırları

farklıdır. Başka bir olasılık dördüncü sütunu silmek olabilirdi.

Öğrenme teorisi uygulaması

Bakış açısından hesaplamalı öğrenme teorisi Bondy'nin teoremi aşağıdaki gibi yeniden ifade edilebilir:[4]

İzin Vermek C olmak konsept sınıfı sınırlı bir alan üzerinden X. Sonra bir alt küme var S nın-nin X en fazla boyutta |C| - 1 öyle ki S bir tanık seti içindeki her konsept için C.

Bu, her sonlu kavram sınıfının C Lara sahip öğretim boyutu sınırlandırılmış |C| − 1.

Notlar

  1. ^ Bondy, J. A. (1972), "Uyarılmış alt kümeler", Kombinatoryal Teori Dergisi, B Serisi, 12: 201–202, doi:10.1016/0095-8956(72)90025-1, BAY  0319773.
  2. ^ Jukna, Stasys (2001), Bilgisayar Bilimlerinde Uygulamalar ile Aşırı KombinatorikSpringer, ISBN  978-3-540-66313-3Bölüm 12.1.
  3. ^ Clote, Peter; Remmel, Jeffrey B. (1995), Uygulanabilir Matematik II, Birkhäuser, ISBN  978-3-7643-3675-2Bölüm 4.1.
  4. ^ Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael (1996), "İkili vektörlerin aileleri için tanık setleri", Kombinatoryal Teori Dergisi, Seri A, 73 (2): 376–380, doi:10.1016 / S0097-3165 (96) 80015-X, BAY  1370141.