Apakah shift-chain dua warna?

Untuk $A\subset [n]$ dilambangkan dengan $a_i$ yang $i^{th}$ elemen terkecil$A$ .

Untuk dua set elemen $k$ , $A,B\subset [n]$ , kita mengatakan bahwa $A\le B$ jika $a_i\le b_i$ untuk setiap $i$ .

Sebuah $k$ -uniform hipergraf ${\mathcal H}\subset [n]$ disebut pergeseran-rantai jika untuk setiap hyperedges, $A, B \in {\mathcal H}$ , kita memiliki $A\le B$ atau $B\le A$ . (Jadi rantai shift memiliki paling banyak $k(n-k)+1$ hyperedges.)

Kami mengatakan bahwa hypergraph ${\mathcal H}$ adalah dua warna (atau memiliki Properti B) jika kita bisa mewarnai simpulnya dengan dua warna sehingga tidak ada hyperedge yang monokromatik.

Benarkah shift-chain dua warna jika $k$ cukup besar?

KomentarSaya pertama kali memposting masalah ini di mathoverflow , tetapi tidak ada yang mengomentarinya.

Masalahnya diselidiki pada Lokakarya Emlektabla ke-1 untuk beberapa hasil parsial, lihat buklet .

Pertanyaannya dimotivasi oleh dekomposisi beberapa penutup pesawat dengan menerjemahkan bentuk cembung, ada banyak pertanyaan terbuka di bidang ini. (Untuk lebih lanjut, lihat tesis PhD .)

Untuk $k=2$ ada contoh tandingan sepele: (12), (13), (23).

Contoh tandingan yang sangat ajaib diberikan untuk $k=3$ oleh Radoslav Fulek dengan program komputer:

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

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

Jika kita membiarkan hypergraph menjadi penyatuan dua rantai shift (dengan urutan yang sama), maka ada contoh tandingan untuk setiap $k$ .

Memperbarui. Baru-baru ini saya berhasil menunjukkan bahwa versi yang lebih terbatas dari rantai shift dua warna dalam cetakan ini .

Hadiah permanen! Saya senang memberikan hadiah 500 untuk solusi kapan saja!

Ini bukan jawaban. Berikut ini adalah bukti sederhana bahwa konstruksi untuk k = 3 memang merupakan contoh tandingan. Saya pikir penanya mengetahui bukti ini, tetapi saya akan tetap mempostingnya karena buktinya bagus dan ini mungkin berguna ketika orang mempertimbangkan kasus k yang lebih besar .

Sangat mudah untuk memverifikasi bahwa itu adalah rantai shift. Mari kita tunjukkan bahwa ia tidak memiliki Properti B.

Bahkan, subhypergraph {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} sudah gagal memenuhi Properti B. Untuk melihat ini, anggaplah bahwa hypergraph ini memiliki 2-warna dan biarkan c _i menjadi warna dari simpul i . Lihatlah tiga hyperedges (145), (245), (345). Jika c ₄ = c ₅ , maka semua 1, 2 dan 3 harus menjadi warna yang berlawanan dengan c ₄ , tetapi ini akan memberikan hyperedge monokromatik (123). Oleh karena itu, harus menjadi kasus yang c ₄ ≠ c ₅ . Demikian pula,

• c ₃ ≠ c ₄ dengan membandingkan tiga hyperedges (345), (346), (347) dan memperhatikan hyperedge (567).
• c ₆ ≠ c ₇ dengan membandingkan tiga hyperedges (367), (467), (567) dan memperhatikan hyperedge (345).
• c ₅ ≠ c ₆ dengan membandingkan tiga hyperedges (567), (568), (569) dan memperhatikan hyperedge (789).

Oleh karena itu, kita memiliki c ₃ ≠ c ₄ ≠ c ₅ ≠ c ₆ ≠ c ₇ . Tapi ini menyiratkan c ₃ = c ₅ = c ₇ , membuat hyperedge (357) monokromatik. Ini bertentangan dengan asumsi pewarnaan 2.

Mungkin saya kehilangan sesuatu tetapi saya pikir ada batas bawah yang baik dengan metode probabilistik:

Jika Anda mewarnai setiap sudut indepedently dengan probabilitas untuk setiap warna maka Anda memiliki tepi monokromatik dengan probabilitas 2 ⋅ ( $1/2$. Denganlemas lokal LovaszAnda mendapatkan bahwa rantai shift memiliki propertiBjika k(n-k)+1≤2 k $2 \cdot (\dfrac{1}{2})^k = 2^{-k+1}$$B$

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