O estado da arte do sistema de girassol

11

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. k A i A iA j = Y i j Y A i - YUkAiAiAj=YijYAiY

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

Erdos e Rado provou que para um familiar uniforme de conjuntos , deve conter um -óleos pétalas sistema se .F F k | F | > s ! ( k - 1 ) ssFFk|F|>s!(k1)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)c k c s k s FkckckssF

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 | você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 .s F U c 1 c 2 c 3 s F 3 | F | > c s i | U | = iusFUc1c2c3sF3|F|> cis|U|=i

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

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

Yao Wang
fonte
1
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
cii=|U|ci=2i|U|
|U||U|F2iϵ
brevemente, estou perguntando se podemos melhorar o limite inferior.
Yao Wang

Respostas:

7

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