¿Son las cadenas de cambio de dos colores?

Para $A\subset [n]$ denotan por $a_i$ el $i^{th}$ elemento más pequeño de $A$ .

Para dos conjuntos de elementos $k$ , $A,B\subset [n]$ , decimos que $A\le B$ si $a_i\le b_i$ para cada $i$ .

A $k$ hypergraph Uniform que se llama una cadena cambio si por cualquier hyperedges, , tenemos A ≤ B o B ≤ A . (Por lo tanto, una cadena de cambio tiene como máximo k ( n - k ) + 1 hiperedges).${\mathcal H}\subset [n]$$A, B \in {\mathcal H}$$A\le B$$B\le A$$k(n-k)+1$

Decimos que una hipergrafía es de dos colores (o que tiene la Propiedad B) si podemos colorear sus vértices con dos colores de modo que ninguna hiperedificación sea monocromática.${\mathcal H}$

¿Es cierto que las cadenas de cambio son de dos colores si es lo suficientemente grande?$k$

Observaciones Primero publiqué este problema en mathoverflow , pero nadie lo comentó.

El problema se investigó en el 1er Taller Emlektabla para obtener algunos resultados parciales, consulte el folleto .

La pregunta está motivada por la descomposición de múltiples cubiertas del plano mediante traducciones de formas convexas, hay muchas preguntas abiertas en esta área. (Para más información, vea mi tesis doctoral ).

Para $k=2$ hay un contraejemplo trivial: (12), (13), (23).

Radoslav Fulek proporcionó un contraejemplo muy mágico para $k=3$ con un programa de computadora:

(123), (124), (125), (135), (145), (245), (345), (346), (347), (357),

(367), (467), (567), (568), (569), (579), (589), (689), (789).

Si permitimos que la hipergrafía sea la unión de dos cadenas de cambio (con el mismo orden), entonces hay un contraejemplo para cualquier $k$ .

Actualizar. Recientemente me las arreglé para mostrar que en esta preimpresión hay dos versiones más restringidas de cadenas de cambio .

Recompensa permanente! ¡Estoy feliz de otorgar una recompensa de 500 por una solución en cualquier momento!

Esta no es una respuesta. Lo que sigue es una prueba simple de que la construcción para k = 3 es de hecho un contraejemplo. Creo que el autor de la pregunta conoce esta prueba, pero la publicaré de todos modos porque la prueba es buena y esto podría ser útil cuando las personas consideran el caso de k más grande .

Es fácil verificar que se trata de una cadena de cambio. Demostremos que no tiene la Propiedad B.

De hecho, el subhypergraph {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} ya no satisface la propiedad B. para ver esto, supongamos que esta hypergraph tiene un 2-colorante y dejar que c _i ser el color del vértice i . Mire tres hiperedificaciones (145), (245), (345). Si c ₄ = c ₅ , entonces todos 1, 2 y 3 deben ser del color opuesto a c ₄ , pero esto daría una hiperedificación monocromática (123). Por lo tanto, debe ser el caso de que c ₄ ≠ c ₅ . Similar,

• c ₃ ≠ c ₄ comparando las tres hiperedificaciones (345), (346), (347) y notando una hiperedificación (567).
• c ₆ ≠ c ₇ comparando las tres hiperedificaciones (367), (467), (567) y notando una hiperedificación (345).
• c ₅ ≠ c ₆ comparando las tres hiperedificaciones (567), (568), (569) y notando una hiperedificación (789).

Por lo tanto, tenemos c ₃ ≠ c ₄ ≠ c ₅ ≠ c ₆ ≠ c ₇ . Pero esto implica c ₃ = c ₅ = c ₇ , lo que hace que el hiperedge (357) sea monocromático. Esto contradice la suposición de 2 colores.

Quizás me estoy perdiendo algo, pero creo que hay un buen límite inferior con el método probabilístico:

Si el color de cada vértice indepedently con una probabilidad de para cada color, entonces su tener un borde monocromática con una probabilidad de 2 ⋅ ( $1/2$$2 \cdot (\dfrac{1}{2})^k = 2^{-k+1}$$B$

$O(\sqrt{k/\ln(k)} \cdot 2^k)$$k$$B$