Konstan dalam dugaan Komlos

Diberikan vektor v 1 , … , v n ∈ R N dengan ‖ v i ‖ 2 2 ≤ 1 di setiap i ∈ { 1 , … , n } , dugaan Komlos menyatakan bahwa, ada c ∈ R (tidak bergantung pada n , N ) sedemikian rupa sehingga pada beberapa ϵ ∈ { - 1 , + 1 } n , $n$$v_1,\dots,v_n\in\Bbb R^N$$\|v_i\|_2^2\leq1$$i\in\{1,\dots,n\}$$c\in\Bbb R$$n,N$$\epsilon\in\{-1,+1\}^n$Apabatas bawahterbaik yangdikenal untukc?

Batas atas terbaik adalah .$c=O(\sqrt{\log n})$

Apakah ada satu set contoh untuk untuk setiap δ > 0 di mana dugaan Komlos gagal?$c=1+\delta$$\delta>0$

Cara sederhana untuk mendapatkan batas bawah adalah untuk mempertimbangkan pasang vektoru,v∈R. Pertama-tama, masuk akal untuk fokus pada pasangan unit vektor yang semua{-1,1}kombinasi -Linear yang selama mungkin (catatan bahwa ini hanya sebuah kasus khusus yang menarik, saya tidak mengatakan bahwa itu adalah opotimal dengan cara apa pun). Ini dicapai ketikau,vadalah ortogonal, dan dengan memeriksa rotasi yang mungkin kami temukan bahwau=$c\ge\sqrt{2}$$u,v\in\mathbb{R}$$\{-1,1\}$$u,v$menunjukkan bahwacharus setidaknya$u=\frac{1}{\sqrt{2}}(1,1), v=\frac{1}{\sqrt{2}}(1,-1)$$c$ .$\sqrt{2}$

Contoh ini dapat digeneralisasi untuk set vektor , di manakoefisienj-th(vi,k)jdarivi,kadalah1jikadigit bineri-thdalamjadalah0, dan-1sebaliknya.$V_k=\{2^{-\frac{k}{2}}v_{i,k}\ |\ 0\le i\le k\}\subseteq\mathbb{R}^{2^k}$$j$$(v_{i,k})_j$$v_{i,k}$$1$$i-th$$j$$0$$-1$

$\infty$$\{-1,1\}$$V_k$$(k+1)2^{-\frac{k}{2}}$$\frac{3}{2}$$k=2$

$V_2=\{\frac{1}{2}(1,1,1,1),\frac{1}{2}(1,1,-1,-1),\frac{1}{2}(1,-1,1,-1)\}$

Mungkin ada batas bawah yang lebih baik, tapi ini awal.

$v_i$$c \geq \frac{4}{\sqrt{6}} \approx 1.633$

$O(\sqrt{\log n})$