Eine kombinatorische Version für die Polynom-Hirsch-Vermutung

Betrachten disjoint Familien von Teilmengen von {1,2, ..., n}, .$t$${\cal F}_1,{\cal F_2},\dots {\cal F_t}$

Nehme an, dass

(*)

Für jedes und jedes und gibt es das .$i \lt j \lt k$$R \in {\cal F}_i$$T \in {\cal F}_k$$S \in {\cal F}_j$$R \cap T$

Die Grundfrage ist:

Wie groß kann nicht sein ???

Was bekannt ist

Die bekannteste Obergrenze ist das Quasi-Polynom .$t \le n^{\log n+1}$

Die bekannteste Untergrenze ist (bis zu einem logarithmischen Faktor) quadratisch.

Diese abstrakte Einstellung stammt aus der Arbeit Diameter of Polyhedra: Die Grenzen der Abstraktion von Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov und Thomas Rothvoss . Die quadratische Untergrenze sowie ein Beweis der Obergrenze sind in ihrer Arbeit zu finden.

Motivation

Jede Obergrenze gilt für den Durchmesser von Diagrammen von d-dimensionalen Polytopen mit n Facetten. Um dies zu sehen , Sie jedem Scheitelpunkt die Menge der Facetten zu, die ihn enthalten. Dann , ausgehend von einem Scheitelpunkt let die Sätze werden entsprechend Vertices des Polytops der Abstand von .$v$$S_v$$w$${\cal F}_r$$r+1$$w$

Mehr

Dieses Problem ist Gegenstand von polymath3 . Aber ich dachte, es kann nützlich sein, es hier und auf MO zu präsentieren, obwohl es ein offenes Problem ist. Wenn das Projekt zu bestimmten Teilproblemen führt, kann ich (oder andere) versuchen, sie ebenfalls zu befragen.

(Update; 5. Oktober :) Ein spezielles Problem, das von besonderem Interesse ist, besteht darin, die Aufmerksamkeit auf Mengen der Größe d zu beschränken. Sei f (d, n) der Maximalwert von t, wenn alle Mengen in allen Familien die Größe d haben. Sei f * (d, n) der Maximalwert von t, wenn wir Mehrfachmengen der Größe d zulassen. Das Verständnis von f * (3, n) kann entscheidend sein.

Problem: Verhält sich f * (3, n) wie 3n oder wie 4n?

Die bekannten unteren und oberen Grenzen sind 3n-2 bzw. 4n-1. und da die 3 der Anfang der Folge 'd' ist, während die 4 der Anfang der Folge ist, kann entscheiden, ob die Wahrheit 3 ​​oder 4 ist, und von Bedeutung sein. Siehe den zweiten Thread .$2^{d-1}$

Ein Freund von mir und ich haben beschlossen, die Brute-Force-Methode auszuprobieren und einige Werte von für kleine Werte von und berechnen . Ohne Beschneiden ist dies völlig unmöglich, und wir hoffen, dass die gefundenen Tricks einen Einblick in den Rest des Problems geben. Bisher ist es uns nicht gelungen, die doppelt exponentielle Laufzeit der Brute-Force-Methode signifikant zu verkürzen (ungefähr ist unsere bisher beste Grenze), und daher haben wir unser ursprüngliches Ziel, irgendwie, noch nicht erreicht Vorhersage der Funktion hinter$t$$n$$d$$3^{2^n}$$f$von seinen ersten Werten. Wir haben auch nicht alle Kommentare der vorherigen Threads im Detail untersucht, sodass einige davon möglicherweise bereits bekannt sind. Wir hatten im Grunde genommen Spaß daran, unseren Code schnell zu machen, und wollten unsere Ergebnisse irgendwo veröffentlichen, wenn ich eine funktionierende LaTeX-Umgebung hätte Legen Sie dies auf dem ArXiV.

Code (es ist nicht genau Produktionscode ...): http://pastebin.com/bSetW8JS . Werte:

f(d=2, n)=2n-1 for n <= 6

f(d=3, n=3) = 6
{} {0} {01} {012} {12} {2}

f(d=4, n=4) = 8
f(d=3, n=4) = 8
{} {0} {01} {1,02,03} {2,13} {123} {23} {3}
{} {0} {01} {2,013} {1,02,03} {023} {23} {3}

f(d=5, n=5) = 11
f(d=4, n=5) = 11
f(d=3, n=5) = 11
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {012,3} {02,12,013,014} {13,023,04,124} {123,024} {23,24} {234} {34} {4}
{} {0} {01} {012,13} {02,12,013} {03,123,014,024} {023,124} {23,24} {234} {34} {4}

Wir sagen , dass die Folge ist konvex , wenn (*) hält. Unser Ansatz konstruiert konvexe Sequenzen, indem Familien an kürzere konvexe Sequenzen wird im verwendet: Wenn konvex ist, dann ist konvex. Wir stellen fest , dass ist konvex , wenn und nur dann , wenn für alle wir , dass ist konvex. Wir sagen, dass mit kompatibel ist, wenn${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_t$$A \in {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$$A$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$ist konvex - wir sparen Rechenzeit, indem wir die mit einer Sequenz kompatiblen Mengen berechnen und dann die Elemente ihres Potenzsatzes als neues , anstatt zu bestimmen, ob ist direkt konvex.${\cal F}_t$${\cal F}_1, ..., {\cal F}_t$

Unsere nächste Beschleunigung ist im Wesentlichen die dynamische Programmierung. Wir versuchen, eine Äquivalenzrelation auf konvexen Sequenzen mit den folgenden zwei Eigenschaften zu finden. Erstens, wenn für zwei konvexe Folgen ist, dann ist kompatibel mit genau dann, wenn es mit kompatibel ist . Zweitens, wenn und ist konvex, dann$\sim$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$$A$${\cal F}_1, ..., {\cal F}_t$${\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1} \sim {\cal F}'_1, ..., {\cal F}'_t, {\cal F}_{t+1}$. Darüber hinaus möchten wir, dass wir feststellen können, ob eine Menge mit Elementen aus einer Äquivalenzklasse kompatibel ist, und einen Vertreter der Äquivalenzklasse von gegeben und ein Vertreter der Äquivalenzklasse von . Der daraus resultierende dynamische Programmieralgorithmus ist dann offensichtlich. Die Anzahl der Äquivalenzklassen (zusammen mit der Zeit, die die obigen beiden Operationen benötigen) ergibt dann eine Grenze für die Laufzeit des offensichtlichen dynamischen Programmieralgorithmus.${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t$

Für die Äquivalenz, die wir verwenden, um unsere Bindung zu erhalten, verwenden wir eine Charakterisierung der Konvexität, die wie folgt auf "Intervallen" basiert. Bei einer Untergruppe des , sagen wir ist angrenzend in Bezug auf eine (nicht notwendigerweise konvex) Sequenz wenn für einige ganze Zahlen . Wir sagen, dass das Intervall für bezüglich dieser Sequenz ist. Es ist leicht zu erkennen, dass genau dann konvex ist, wenn alle Teilmengen von$A$$\{ 1, \dots, n \}$$A$${\cal F}_1, ..., {\cal F}_t$$\{ k \mid \exists B \in {\cal F}_k : A \subseteq B \} = \{ i, \dots, j \}$$1 \leq i \leq j \leq n$$(i, j)$$A$${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$ sind in Bezug auf die Reihenfolge zusammenhängend.

Bei einer konvexen Folge markieren wir nun alle Teilmengen von wie folgt als nicht berührt , nicht erlaubt oder aktiv : all Elemente von sind aktiv, alle Elemente von sind unzulässig und alle Obermengen von Mengen deren Intervall in Bezug auf ist mit sind ebenfalls nicht zulässig. Es ist unmittelbar, dass eine Menge${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$${\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$$B$$A$${\cal F}_1, ..., {\cal F}_{t-1}$$(i, j)$$j < t - 1$$A$ist genau dann mit der Sequenz kompatibel, wenn sie als nicht berührt markiert ist. Wir definieren zwei Sequenzen als äquivalent unter wenn ihre Markierung gleich ist. Es ist leicht zu erkennen, dass diese Äquivalenzbeziehung unsere beiden Eigenschaften erfüllt. Um zu berechnen, ob eine Menge durch die Intervallbedingung nicht zugelassen werden soll, können wir die äquivalente Bedingung verwenden, 'es gibt eine Menge so dass für keine Menge , '. ist eine unmittelbare Grenze für die Anzahl der Äquivalenzklassen.$\sim$$B$$C \in {\cal F}_t$$D \in {\cal F}_{t+1}$$B \cap C \subseteq D$$3^{2^n}$

Wir verwenden auch verschiedene zusätzliche Schnitte. Wir betrachten nur Antichains für und wir fordern, dass die Elemente seiner Elemente aus . Zuletzt verwenden wir die Optimierung, die für optimal lange Sequenzen (und ähnliches für und ). Wir stellen uns vor, dass die Untersuchung des Verhaltens von drastischeren Einsparungen führen kann.${\cal F}_{t+1}$${1, \dots, i}$${\cal F}_1 = \{ \{ 1 \} \}, {\cal F}_2 = \{ \{ 1, 2 \} \}$${\cal F}_{t-1}$${\cal F}_t$${\cal F}_3$