Command Palette
Search for a command to run...
0-1 Gesetze für die Auftreten von Mustern in phylogenetischen Bäumen und Netzwerken
0-1 Gesetze für die Auftreten von Mustern in phylogenetischen Bäumen und Netzwerken
François Bienvenu Mike Steel
Zusammenfassung
In einer kürzlich veröffentlichten Arbeit wurde die Frage gestellt, welcher Anteil der binären Bäume ein festes Muster enthält, das als Schneeflocke bekannt ist. Wir zeigen, dass dieser Anteil gegen 1 geht und geben dazu zwei sehr unterschiedliche Beweise: einen rein kombinatorischen, der quantitativ und spezifisch für dieses Problem ist; sowie einen Beweis, der Verzweigungsprozess-Techniken verwendet und weniger explizit ist, aber auch viel allgemeiner anwendbar, da er sich auf beliebige feste Muster erstreckt und auf andere Bäume und Netzwerke verallgemeinert werden kann. Insbesondere folgt direkt aus unserem zweiten Beweis, dass der Anteil der d-ären Bäume (bzw. Level-k-Netzwerke), die ein festes d-äres Baum (bzw. Level-k-Netzwerk) enthalten, gegen 1 strebt, wenn die Anzahl der Blätter wächst.