\(2kn-\binom{2k+1}{2}\). A note on extremal combinatorics of cyclic split systems (Q5949814): Difference between revisions

Mit Beschränkung auf (gemeinsam) zyklische Zweiteilungen einer \(n\)-Menge \(M\) werden Maximalzahlen von unverträglichen Anteilen in jeder genügend großen Menge solcher Teilungen abhängig von deren Anzahl angegeben und bewiesen. Damit werden bisher bekannte Grenzen und Maximalzahlen verschärft und Vermutungen für weitere Abschätzungen und genaue Werte bewiesen bzw. nahegelegt. Als Vermutung ergibt sich, dass eine etwas schärfere Verträglichkeitsbeschränkung bei gegebenen Maximalzahlen bereits nur zyklische Teilungen zulässt. Die Beschränkung auf gemeinsam zyklische Teilungen ermöglicht eine einfache geometrische Darstellung, welche benutzt wird, um die abstrakten Abhängigkeiten in und zwischen den Mengen leicht durchschaubar zu machen, und zu weiteren Folgerungen anregt. Die Ergebnisse sind u.a. bei der Optimierung von Systemen mit Viel-Komponenten-Strömen (multicommodity flows) verwendbar.