O estado da arte do sistema de girassol

Eu sou interessante no sistema de girassol e suas aplicações na ciência da computação.

Dado um universo e uma coleção de define é chamado de um sistema de k-girassol se para todos . E é chamado como o núcleo e é chamado de pétalas. $U$ $k$ $A_i$ $A_i \cap A_j = Y$ $i \neq j$ $Y$ $A_i - Y$

Uma família de conjuntos é chamada -uniforme é todos os conjuntos que contém possuem elementos. $F$ $s$ $s$

Erdos e Rado provou que para um familiar uniforme de conjuntos , deve conter um -óleos pétalas sistema se . $s$ $F$ $F$ $k$ $|F| > s!(k-1)^s$

Este resultado é chamado lema do girassol e tem muitas aplicações importantes.

Erdos conjecturado que para cada existe uma constante tal que o limite superior deve ser cada família -uniform . (A conjectura de girassol) $k$ $c_k$ $c_k^s$ $s$ $F$

Infelizmente, essa conjectura ainda está aberta para . $k=3$

Aqui está o que eu quero saber.

Se limitarmos o número de elementos no universo Suponha= . Então o problema é: $U$ $|U|$ $u$

Dado um universo com elementos e família uniforme de conjuntos contendo os elementos em , supomos que podemos encontrar a sequência das constantes , , , ... de modo que toda família uniforme contenha um girassol sistema se e . $u$ $s$ $F$ $U$ $c_1$ $c_2$ $c_3$ $s$ $F$ $3$ $|F|>$ $c_i^s$ $|U|=i$

Além disso, se pudermos provar que a sequência converge para uma constante , parece que podemos provar a conjectura do girassol. $c_i$ $c$

Mas não consigo encontrar esse resultado. Pode ser que essa abordagem seja estúpida ou muito difícil.

Alguém poderia fornecer o estado da arte do lema do girassol e a conjectura (a versão finita também é aceitável).

Aqui estão alguns que eu posso fornecer. Há um capítulo no livro de Junka, The Extremal Combinatorics.

O documento acima é uma de suas aplicações (versão finita)

Sobre girassóis e multiplicação de matrizes N Alon et.al

co.combinatorics set-theory Yao Wang
fonte

não parece haver muito trabalho direto sobre ele além de novas aplicações e trabalhos recentes citados, o que pode aumentar o interesse e é provavelmente o melhor lugar para começar para referências (o livro juknas também é imbatível). Aqui está um bom resumo das interconexões de kalai em seu blog

vzn

c_{i}

$c_i$

i = | U |

$i = |U|$

c_{i} = 2^{i}

$c_i = 2^i$

| U |

$|U|$

| U |

$|U|$

| U |

$|U|$

F

$F$

2^{i - ϵ}

$2^{i-\epsilon}$

brevemente, estou perguntando se podemos melhorar o limite inferior.

Yao Wang

Respostas:

a conjectura de girassol de Erdos parece ser muito difícil depois de mais de meio século (!) de abertura. você já listou algumas das melhores e mais recentes referências sobre o assunto que seriam muito difíceis de derrotar (artigo recente de Alons, livro de Juknas sobre combinatória). o artigo de Alon é altamente notável por vincular recentemente a conjectura a limites mais baixos na multiplicação de matrizes, uma área que viu avanços recentes nos resultados de Williams. [4]

você pode encontrar algum tratamento adicional, principalmente aplicações à teoria dos circuitos extremais (limites inferiores do circuito descobertos por Razborov e estendidos por outros), no excelente livro de Jukna [1].

uma referência recente notável / relacionada ao longo dessas linhas, aparentemente não tão amplamente conhecida ou citada até agora, é [2] por Rossman com uma nova direção de aplicação (gráficos aleatórios Erdos-Renyi sobre circuitos monótonos) e quem prova resultados estendidos e / ou mais fortes em girassóis "quase". o artigo é resultado de sua tese de doutorado [3]. do resumo do artigo

Introduzimos uma nova variante de girassóis e provamos um análogo do lema do girassol que pode ser de interesse independente.

[1] Complexidade da função booleana, avanços e fronteiras

[2] A complexidade monótona de k-Clique em gráficos aleatórios (2009) Rossman

[3] Complexidade média de casos de detecção de panelinhas de Rossman

[4] Comentário sobre a descoberta da Williams no blog de limite inferior RJ Liptons Godels Lost Letter do produto da matriz

[5] Materiais detalhados sobre girassóis

vzn
fonte