El estado del arte para el sistema de girasol

Me interesa el sistema de girasol y sus aplicaciones en informática.

Dado un Universo y una colección de conjuntos se llama sistema k-girasol si para todo . Y se llama como núcleo y se llama pétalos. $U$ $k$ $A_i$ $A_i \cap A_j = Y$ $i \neq j$ $Y$ $A_i - Y$

Una familia de conjuntos se llama uniforme; todos los conjuntos que contiene poseen elementos . $F$ $s$ $s$

Erdos y Rado demostraron que para una familia uniforme de conjuntos , debe contener un sistema de pétalos de girasol si . $s$ $F$ $F$ $k$ $|F| > s!(k-1)^s$

Este resultado se llama lema del girasol y tiene muchas aplicaciones importantes.

Erdos conjeturó que para cada existe una constante de tal manera que el límite superior debe ser cada familia Uniform . (La conjetura del girasol) $k$ $c_k$ $c_k^s$ $s$ $F$

Desafortunadamente, esta conjetura todavía está abierta para . $k=3$

Esto es lo que quiero saber.

Si limitamos el número de elementos en el universo .Suppose = . Entonces el problema resulta ser: $U$ $|U|$ $u$

$u$ $s$ $F$ $U$ $c_1$ $c_2$ $c_3$ $s$ $F$ $3$ $|F|>$ $c_i^s$ $|U|=i$

$c_i$ $c$

Pero no puedo encontrar ese resultado. Puede ser que este enfoque sea demasiado estúpido o demasiado difícil.

¿Alguien podría proporcionar el estado del arte del lema de girasol y la conjetura (la versión finita también está bien).

Aquí hay algunos que puedo proporcionar. Hay un capítulo en el libro de Junka The Extremal Combinatorics.

El artículo anterior es una de sus aplicaciones (versión finita)

Sobre girasoles y multiplicación de matrices N Alon et.al

co.combinatorics set-theory Yao Wang
fuente

no parece haber mucho trabajo directo sobre él, aparte de las nuevas aplicaciones y solo el artículo reciente que usted cita, lo que podría aumentar el interés y es probablemente el mejor lugar para comenzar a obtener referencias (y el libro juknas también es inmejorable). Aquí hay un buen resumen de las interconexiones de Kalai en su 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, pregunto si podemos mejorar el límite inferior.

Yao Wang

Respuestas:

la conjetura del girasol Erdos parece ser muy difícil después de más de medio siglo (!) de estar abierta. ya has enumerado algunas de las mejores y más recientes referencias en el subj que serían muy difíciles de superar (artículo reciente de Alons, libro de Juknas sobre combinatoria). El artículo de Alon es muy notable por vincular recientemente la conjetura a los límites inferiores en la multiplicación de matrices, un área que ha visto un avance innovador reciente en los resultados de Williams. [4]

puede encontrar algún tratamiento adicional, principalmente aplicaciones a la teoría del circuito extremo (límites inferiores del primer circuito descubiertos por Razborov y extendidos por otros), en el destacado libro de Jukna [1].

Rossman con una nueva dirección de aplicación (gráficos aleatorios de Erdos-Renyi sobre circuitos monótonos) y una referencia reciente notable / relacionada a lo largo de estas líneas aparentemente no tan conocida o citada hasta ahora es [2] Resultados extendidos y / o más fuertes en girasoles "cuasi". El artículo es el resultado de su tesis doctoral [3]. del resumen en papel

Presentamos una nueva variante de girasoles y demostramos un análogo del lema del girasol que puede ser de interés independiente.

[1] Complejidad, avances y fronteras de la función booleana.

[2] La complejidad monótona de k-Clique en gráficos aleatorios (2009) Rossman

[3] Complejidad de casos promedio de detección de camarillas por Rossman

[4] Comentario sobre el avance de Williams en el blog de la carta perdida RJ Liptons Godels Lost Letter de productos de matriz

[5] Materiales detallados sobre girasoles

vzn
fuente