Định lý Szemerédi–Trotter

Định lý Szemerédi–Trotter là một định lý trong hình học tổ hợp phát biểu rằng với mọi bộ n điểm và m đường thẳng trên mặt phẳng, số cặp đường thẳng-điểm sao cho điểm nằm trên đường thẳng là

$O(n^{2/3}m^{2/3}+n+m)$.

Chặn trên này là chặt, nghĩa là tồn tại bộ n điểm và m đường thẳng có số giao điểm đạt đến giá trị đó (chỉ sai khác tỉ lệ hằng số).

Một hệ quả của định lý là như sau. Với mọi bộ n điểm và một số k > 2, số đường thẳng đi qua ít nhất k điểm là

$O(n^{2}/k^{3}+n/k).$

Chứng minh đầu tiên của Szemerédi và Trotter khá phức tạp, sử dụng phương pháp phân chia ô. Sau đó, Székely tìm ra một chứng minh đơn giản sử dụng bất đẳng thức số giao điểm của đồ thị.

Định lý Szemerédi–Trotter có nhiều hệ quả, chẳng hạn như định lý Beck trong hình học.

Chứng minh

Ta có thể loại đi các đường thẳng chỉ chứa một hoặc hai điểm do chúng chỉ tạo ra không quá 2m cặp đường thẳng-điểm sao cho điểm đó nằm trên đường thẳng. Do đó, từ nay ta giả sử mọi đường thẳng đều chứa ít nhất ba điểm.

Nếu một đường thẳng chứa k điểm, thì nó bao gồm k−1 đoạn thẳng rời nhau nối hai trong số n điểm đã cho. Vì vậy nó chứa ít nhất k/2 đoạn thẳng như vậy, do ta giả sử k≥ 3. Cộng các giá trị này từ tất cả m đường thẳng, ta thu được số đoạn thẳng bằng ít nhất một nửa số cặp đường thẳng-điểm. Nếu đặt e là số đoạn thẳng thì để có được định lý, ta chỉ cần chứng minh $e=O(n^{2/3}m^{2/3}+n+m)$.

Xét đồ thị tạo bởi n điểm là các đỉnh, và e đoạn thẳng là các cạnh. Do các đoạn thẳng nằm trên m đường thẳng, và hai đường thẳng giao nhau tại tối đa là một điểm, số giao điểm của đồ thị này là không quá $m^{2}$. Áp dụng bất đẳng thức cho số giao điểm, ta có hoặc e ≤ 7.5n, hoặc m² ≥ e³ / 33.75n². Trong cả hai trường hợp e ≤ 3.24n^2 / 3m^2 / 3 + 7.5n và ta thu được kết quả $e=O(n^{2/3}m^{2/3}+n+m)$.

Chứng minh hệ quả

Mỗi cặp điểm xác định đúng một đường thẳng nên có tối đa n(n − 1)/2 đường thẳng chứa ít nhất k điểm, vì k ≥ 2. Chặn trên này cho ta kết quả cần chứng minh nếu k nhỏ (chẳng hạn k ≤ C với một hằng số cố định C). Do đó chỉ cần xem xét trường hợp k lớn, chẳng hạn k ≥ C.

Giả sử có m đường thẳng chứa ít nhất k điểm. Các đường thẳng này tạo ra mk cặp đường thẳng-điểm mà điểm nằm trên đường thẳng, nên theo định lý Szemerédi–Trotter, ta có

$mk=O(n^{2/3}m^{2/3}+n+m)$

Vì vậy xảy ra một trong ba khả năng sau: $mk=O(n^{2/3}m^{2/3})$, $mk=O(n)$, hoặc $mk=O(m)$. Trường hợp thứ ba bị loại do ta giả sử k lớn, nên chỉ có thể xảy ra hai trường hợp đầu. Nhưng trong cả hai trường hợp đầu, với một số tính toán đơn giản ta đều thu được $m=O(n^{2}/k^{3}+n/k)$.

Tổng quát hóa lên ℝ^d

Một tổng quát hóa của định lý này cho ℝ^d được tìm ra bởi Agarwal và Aronov. Cho một tập hợp $S$ gồm $n$ điểm, và một tập hợp $H$ gồm $m$ siêu phẳng, sao cho mỗi siêu phẳng đều sinh bởi $S$, số giao điểm giữa $S$ và $H$ là không quá

$O(m^{2/3}n^{d/3}+n^{d-1}).$

Một cách tương đương, số siêu phẳng trong $H$ chứa $k$ điểm là không quá

$O(n^{d}/k^{3}+n^{d-1}/k).$

Một ví dụ của Edelsbrunner cho thấy chặn trên này là tối ưu (không tính đến hằng số tuyệt đối).

Solymosi và Tao chứng minh được chặn trên gần chặt cho số giao điểm của một tập hợp điểm với một tập hợp các đa tạp đại số. Chứng minh của họ sử dụng định lý bánh mì dăm bông đa thức.