As correntes de mudança são bicolores?

Para $A\subset [n]$ designam por $a_i$ o $i^{th}$ menor elemento de $A$ .

Para dois conjuntos de elementos $k$ , $A,B\subset [n]$ , dizemos que $A\le B$ se $a_i\le b_i$ para cada $i$ .

Um $k$ -uniform hipergrafo ${\mathcal H}\subset [n]$ é chamado uma cadeia turno , se por qualquer hiperarestas, $A, B \in {\mathcal H}$ , temos ou . (Portanto, uma cadeia de turnos tem no máximo hiperedges.)$A\le B$$B\le A$$k(n-k)+1$

Dizemos que um hipergrafo é bicolor (ou que possui a Propriedade B) se pudermos colorir seus vértices com duas cores, de modo que nenhuma hiper-borda seja monocromática.${\mathcal H}$

É verdade que as cadeias de mudança são bicolores se for grande o suficiente?$k$

Observações A primeira vez que publiquei esse problema no mathoverflow , mas ninguém comentou.

O problema foi investigado no 1º Workshop Emlektabla para obter alguns resultados parciais, consulte o livreto .

A questão é motivada pela decomposição de múltiplas coberturas do avião por traduções de formas convexas; existem muitas questões em aberto nessa área. (Para mais, veja minha tese de doutorado .)

Para existe um contra-exemplo trivial: (12), (13), (23).$k=2$

Um contra-exemplo muito mágico foi dado para $k=3$ por Radoslav Fulek com um programa de computador:

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

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

Se permitirmos que o hipergrafo seja a união de duas cadeias de mudança (com a mesma ordem), existe um contraexemplo para qualquer $k$ .

Atualizar. Recentemente, consegui mostrar que uma versão mais restrita das cadeias de turnos é bicolor nesta pré-impressão .

Recompensa permanente! Estou feliz em conceder uma recompensa de 500 por uma solução a qualquer momento!

Esta não é uma resposta. O que se segue é uma prova simples de que a construção para k = 3 é realmente um contra-exemplo. Eu acho que o solicitante conhece essa prova, mas eu a publicarei de qualquer maneira, porque a prova é boa e isso pode ser útil quando as pessoas consideram o caso de k maior .

É fácil verificar se é uma cadeia de turnos. Vamos mostrar que ele não possui a propriedade B.

De fato, o sub-hipergrafo {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} já não consegue satisfazer a propriedade B. para ver isto, suponho que este hipergrafo tem um 2-coloração e deixar c _i ser a cor do vértice i . Veja três hipervedades (145), (245), (345). Se c ₄ = c ₅ , todos os 1, 2 e 3 devem ter a cor oposta a c ₄ , mas isso daria uma hiper-borda monocromática (123). Portanto, deve ser o caso que c ₄ ≠ c ₅ . Similarmente,

• c ₃ ≠ c ₄ comparando as três hipervedades (345), (346), (347) e observando uma hiper-margem (567).
• c ₆ ≠ c ₇ comparando as três hipervedidas (367), (467), (567) e observando uma hiper-borda (345).
• c ₅ ≠ c ₆ comparando as três hiperedotas (567), (568), (569) e observando uma hiper-borda (789).

Portanto, temos c ₃ ≠ c ₄ ≠ c ₅ ≠ c ₆ ≠ c ₇ . Mas isso implica c ₃ = c ₅ = c ₇ , tornando a hipérbere (357) monocromática. Isso contradiz a suposição da coloração 2.

Talvez esteja faltando alguma coisa, mas acho que há um bom limite inferior com o método probabilístico:

$1/2$$2 \cdot (\dfrac{1}{2})^k = 2^{-k+1}$$B$

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