Der Stand der Technik für Sonnenblumen

Ich interessiere mich für das Sonnenblumensystem und seine Anwendungen in der Informatik.

Wenn ein Universum und eine Sammlung von k Mengen A i gegeben sind, wird es als k-Sonnenblumen-System bezeichnet, wenn A i ∩ A j = Y für alle i ≠ j ist . Und Y heißt als Kern und A i - Y heißt Blütenblätter. $U$$k$$A_i$$A_i \cap A_j = Y$$i \neq j$$Y$$A_i - Y$

Eine Familie von Mengen heißt s- uniform. Alle darin enthaltenen Mengen besitzen s Elemente.$F$$s$$s$

Erdos und Rado bewiesen , dass für eine einheitliche Familie von Mengen F , F ein enthalten k -sonnenblumenöl System Blütenblätter , wenn | F | > s ! ( k - 1 ) s .$s$$F$$F$$k$$|F| > s!(k-1)^s$

Dieses Ergebnis wird als Sonnenblumen-Lemma bezeichnet und hat viele wichtige Anwendungen.

Erdos vermutete, dass es für jedes eine Konstante c k gibt, so dass die Obergrenze c s k für jede s- einheitliche Familie F sein sollte . (Die Sonnenblumen-Vermutung)$k$$c_k$$c_k^s$$s$$F$

Leider ist diese Vermutung für noch offen .$k=3$

Folgendes möchte ich wissen.

Wenn wir die Anzahl der Elemente im Universum begrenzen .Suppose | U | = u . Dann stellt sich das Problem heraus:$U$$|U|$$u$

Bei einem gegebenen Universum mit Elementen und einer s- einheitlichen Familie F von Mengen, die die Elemente in U enthalten , können wir eine Folge von Konstanten c $u$$s$$F$$U$$c_1$ , , c 3 , ... finden, so dass jede s- einheitliche Familie F a enthält 3- Sonnenblumensystem wenn | F | > c s $c_2$$c_3$$s$$F$$3$$|F|>$ $c_i^s$ und .$|U|=i$

Wenn wir außerdem beweisen könnten, dass die Sequenz gegen eine Konstante c konvergiert , dann können wir anscheinend die Sonnenblumen-Vermutung beweisen.$c_i$$c$

Aber ich kann ein solches Ergebnis nicht finden. Es könnte sein, dass dieser Ansatz zu dumm oder zu hart ist.

Könnte jemand den Stand der Technik der Sonnenblumen-Deckspelze und die Vermutung liefern (endliche Version ist auch in Ordnung).

Hier sind einige, die ich zur Verfügung stellen kann. Es gibt ein Kapitel in Junkas Buch The Extremal Combinatorics.

Das obige Papier ist eine seiner Anwendungen (endliche Version)

Über Sonnenblumen und Matrixmultiplikation N Alon et al

Die Erdos-Sonnenblumen-Vermutung scheint nach über einem halben Jahrhundert (!) der Offenheit sehr schwierig zu sein. Sie haben bereits einige der besten und neuesten Refs auf dem Thema aufgelistet, die sehr schwer zu schlagen wären (Alons jüngstes Papier, Juknas Buch über Kombinatorik). Das Alon-Papier ist sehr bemerkenswert, da es die Vermutung neu mit unteren Grenzen der Matrixmultiplikation verknüpft, einem Bereich, in dem die Williams-Ergebnisse kürzlich bahnbrechende Fortschritte gemacht haben. [4]

In Juknas herausragendem Buch [1] finden Sie eine weitere Behandlung, hauptsächlich Anwendungen für die Theorie extremer Schaltkreise (Schaltkreisuntergrenzen 1. von Razborov entdeckt und von anderen erweitert).

Ein bemerkenswerter / verwandter neuerer Hinweis in dieser Richtung, der anscheinend bisher nicht so bekannt oder zitiert war, ist [2] von Rossman mit einer neuen Anwendungsrichtung (Erdos-Renyi-Zufallsgraphen über monotone Schaltkreise) und wer beweist verlängerte und / oder stärkere Ergebnisse bei "quasi" Sonnenblumen. Die Arbeit ist ein Ergebnis seiner Doktorarbeit [3]. aus dem Papier Abstract

Wir stellen eine neue Variante von Sonnenblumen vor und beweisen ein Analogon zum Sonnenblumen-Lemma, das von unabhängigem Interesse sein kann.

[1] Komplexität, Fortschritte und Grenzen der Booleschen Funktion

[2] Die monotone Komplexität von k-Clique auf Zufallsgraphen (2009) Rossman

[3] Durchschnittliche Komplexität der Erkennung von Cliquen durch Rossman

[4] Kommentar zum Williams-Durchbruch bei der Untergrenze des Matrixprodukts RJ Liptons Godels Lost Letter-Blog

[5] Detaillierte Materialien zu Sonnenblumen