Najnowocześniejszy system słonecznika

Interesuje mnie system słonecznika i jego zastosowania w informatyce.

Biorąc pod uwagę Wszechświat i zbiór zbiorów nazywa się układem k-słonecznika, jeśli dla wszystkich . A nazywa się rdzeniem, a nazywa się płatkami. $U$ $k$ $A_i$ $A_i \cap A_j = Y$ $i \neq j$ $Y$ $A_i - Y$

Rodzina zestawy nazywa -uniform to wszystkie zbiory zawierała ona posiadać elementy. $F$ $s$ $s$

Erdos i Rado udowodnił, że dla jednolite rodziny zbiorów , musi zawierać -sunflower płatków systemowych jeśli . $s$ $F$ $F$ $k$ $|F| > s!(k-1)^s$

Ten wynik nazywa się lemem słonecznikowym i ma wiele ważnych zastosowań.

Erdosa Przypuszcza się, że dla każdego istnieje stała tak, że górna granica powinna co -uniform rodziny . (Hipoteza słonecznika) $k$ $c_k$ $c_k^s$ $s$ $F$

Niestety, ta hipoteza jest nadal otwarta dla . $k=3$

Oto, co chcę wiedzieć.

Jeśli ograniczymy liczbę elementów we wszechświecie Załóżmy = . Problemem okazuje się: $U$ $|U|$ $u$

Biorąc pod uwagę wszechświat z elementami i jednorodną rodziną zbiorów zawierających elementy w , przypuszczalnie możemy znaleźć ciąg stałych , , , ... tak, że każdy $u$ $s$ $F$ $U$ $c_1$ $c_2$ $c_3$ jednorodna rodzina zawieraSystem słonecznikowy, jeśli i . $s$ $F$ $3$ $|F|>$ $c_i^s$ $|U|=i$

Co więcej, jeśli moglibyśmy udowodnić, że sekwencja zbieżna ze stałą , to wydaje się, że możemy udowodnić hipotezę słonecznika. $c_i$ $c$

Ale nie mogę znaleźć takiego wyniku. Być może takie podejście jest zbyt głupie lub zbyt trudne.

Czy ktoś mógłby przedstawić najnowszą wiedzę na temat lematu słonecznikowego i przypuszczeń (wersja skończona jest również OK).

Oto kilka, które mogę zapewnić. Istnieje rozdział w książce Junki The Extremal Combinatorics.

Powyższy artykuł jest jednym z jego zastosowań (wersja skończona)

On Sunflowers and Matrix Multiplication N Alon i in

co.combinatorics set-theory

— Yao Wang
źródło

wydaje się, że nie ma dużo bezpośredniej pracy nad tym poza nowymi aplikacjami i alonami, które ostatnio cytowałeś, co może zwiększyć zainteresowanie i jest prawdopodobnie najlepszym miejscem, aby zacząć od referencji (i książka Juknas jest również nie do pobicia). tutaj jest ładne podsumowanie wzajemnych połączeń Kalai na jego blogu

— dniu

myślę, że posiadanie

zależy od

sprawia, że problem jest trywialny, ponieważ można ustawić

c_{i}

$c_i$

i = | U |

$i = |U|$

. mam też wrażenie, że nie jestem zależny od

jest interesująca w lemacie

c_{i} = 2^{i}

$c_i = 2^i$

| U |

$|U|$

— Sasho Nikolov,

@SashoNikolov. Dzięki za odpowiedź Tak, chcemy, żeby nie zależało od

. ale jeśli mamy

, wówczas możemy jawnie zbudować maksymalną rodzinę

| U |

$|U|$

| U |

$|U|$

. Zastanawiam się, że jeśli ten wyraźny budynek może pokazać coś interesującego dla problemu. Na przykład możemy znaleźć rodzinę z

która wciąż nie zawiera systemu słonecznika. Próbowałem zbudować taką maksymalną rodzinę, ale wydaje się to takie trudne. Nie mogę stworzyć większej, większej rodziny, niż przykład z książki Junki (Cha7).

F

$F$

2^{i - ϵ}

$2^{i-\epsilon}$

— Yao Wang,

krótko pytam, czy możemy poprawić dolną granicę.

— Yao Wang,

w Erdős słonecznik przypuszczenie wydaje się być bardzo trudne teraz, po ponad pół wieku (!) bycia otwartym. wymieniłeś już jedne z najlepszych i najnowszych referencji na temat subj, które byłyby bardzo trudne do pokonania (najnowszy artykuł Alonsa, książka Juknas na temat kombinatoryki). artykuł Alona jest bardzo godny uwagi ze względu na nowe powiązanie hipotezy z dolnymi granicami mnożenia macierzy, w obszarze, w którym ostatnio przełomowy postęp w wynikach Williamsa [4]

można znaleźć dalsze leczenie, głównie zastosowania w teorii ekstremalnych obwodów (dolne granice obwodu 1. odkryte przez Razborova i rozszerzone przez innych), w znakomitej książce Jukny [1].

jeden znaczący / związany z tym niedawny odnośnik według tych linii, najwyraźniej nie tak powszechnie znany lub cytowany do tej pory, jest [2] przez Rossmana z nowym kierunkiem zastosowania (losowe wykresy Erdosa-Renyi dla obwodów monotonicznych) i kto dowodzi rozszerzone i / lub mocniejsze wyniki dla słoneczników „quasi”. praca jest wynikiem jego pracy doktorskiej [3]. z papierowego streszczenia

Wprowadzamy nowy wariant słoneczników i udowadniamy, że analog słonecznika jest dla nas niezależny.

[1] Złożoność funkcji boolowskich, postępy i granice

[2] Monotoniczna złożoność k-Clique na wykresach losowych (2009) Rossman

[3] Średnia złożoność przypadków wykrywania klików przez Rossmana

[4] Komentarz na temat przełomu Williamsa na blogu RJ Liptons Godels Lost Letter w dolnej części produktu matrycowego

[5] Szczegółowe materiały na temat słoneczników

— vzn
źródło