Số độc lập của $C_4$-đồ thị miễn phí

Question

Ai cũng biết rằng một $C_4$-đồ thị đặt hàng miễn phí $n$ có mức độ trung bình $O(\sqrt{n})$, và theo sau rằng số độc lập là$\Omega(\sqrt{n})$.

Không thể cải thiện ràng buộc này $\Theta(n^{\frac34})$: Đồ thị cực của mặt phẳng xạ ảnh có thứ tự $q$ có đơn đặt hàng $q^2+q+1$,trình độ $q+1$ và giá trị riêng tối thiểu $-\sqrt q$, do đó, theo sự ràng buộc của Hoffman, số lượng độc lập tối đa là $O(q^\frac32)=O(n^\frac34)$.

Câu hỏi: Có thể đạt được giới hạn tốt hơn như$\alpha(G)=\Omega(|G|^a)$ với $a>\frac12$?

Bất kỳ câu trả lời nào đưa ra bằng chứng hoặc bác bỏ về việc liệu có thể đạt được $a=\frac58$ sẽ được chấp nhận.

Answer 1

Nếu chúng ta biểu thị $m=\alpha(G)+1$, thì biểu đồ của chúng tôi không chứa $C_4$ và phần bổ sung của nó không chứa $K_m$, do đó $n<R(C_4,K_m)$ (và viceversa, nếu $n<R(C_4,K_m)$, tồn tại một biểu đồ trên $n$ đỉnh không có $C_4$ như vậy mà $\alpha(G)\leqslant m-1$). Vì vậy, câu hỏi này là về$C_4$ và $K_m$Số Ramsey. J. Spencer (Các giới hạn dưới tiệm cận cho các hàm Ramsey. Toán học rời rạc. 20 (1977), 69-76) đã chứng minh rằng$R(C_4,K_m)\geqslant m^{3/2-o(1)}$, cung cấp một ví dụ về biểu đồ với $n$ đỉnh không có $C_4$ và với $\alpha(G)\leqslant n^{2/3+o(1)}$. Giới hạn dưới tốt nhất hiện tại, theo như tôi biết,$R(C_4,K_m)\leqslant m^{2-o(1)}$ (xem Y. Caro, Y. Li, CC Rousseau và Y. Zhang. Các giới hạn tiệm cận cho một số đồ thị lưỡng phân - đồ thị hoàn chỉnh các số Ramsey. Toán học rời rạc. 220 (2000), 51-56) dẫn đến kết quả là $\alpha(G)\geqslant n^{1/2+o(1)}$, có một số cải tiến về nhật ký liên quan đến $n^{1/2}$ràng buộc từ OP). Từ$5/8$ nằm giữa $2/3$ và $1/2$, câu hỏi của bạn dường như đang bỏ ngỏ.