平面網格點中無直角的最大點集構造

趙紅濤，裴四寶

（華北電力大學數理學院，北京102206）

0 引言

1977年Erd?s和Silverman提出這樣一個問題：確定最大整數f（n），使得從平面上任意n個點的集合中可以找到f（n）個點，且這些點中任意三個點不會構成一個直角三角形.他們得到對于一個 k×k的網格點中有 f（k2）≤2k－2，Erd?s證明了，并且他和Silverman猜想有.1980年H.L.Abbott在文獻[1]中證明了Erd?s和Silverman的猜想且有，他也指出 Erd?s和 Silverman的強猜想 f（k2）＝2k－2是錯誤的，同時給出了一個反例的定理，即當k≥5時，有f（k2＋k－4）≤2k－3.1995年Gamble B，Pulleyblank W，Reed B等人在文獻[2]中探究了從二維平面上的一個給定集合中尋找無直角的最大子集的復雜性，他們證明了這類問題的計算是NP-難的.2009年Gy.Elekes在文獻[3]中證明得到.2011年Viktor Harangi，Tamas Keleti等人在文獻[4]中研究了多大的Hausdorff維數保證一個給定角.隨后，關于點集中不出現直角的研究由歐氏空間轉為有限域上的討論，首先是2015年Michael Bennett在文獻[5]中研究了有限域上向量空間中的一些Erd?s-Falconer類問題，他證明了在有限域中不含直角的點集的最大基數，在有限域中過原點的任意兩個點不構成直角的點集的最大基數.2016年Ge和Shangguan在文獻[6]中利用多項式方法對有限域中不含直角的點集的最大基數給出了新的上界，并且得到此最大基數，其中n為有限域的維數，q為素數.

通過Erd?s和Silverman對于k×k的網格點中任意三點不構成直角的最大點集的基數為f（k2）≤2k－2的討論，本文主要研究了m×n網格點中不出現直角的最大點集的基數，通過利用坐標投影法和代數法分別給出了證明，并得到了此最大點集的構造；最后給出了一些關于平面網格點中有待解決的新問題.

1 平面網格點中不出現直角的最大點集

Erd?s和Silverman給出：對于平面上n×n的網格點中，不出現直角的最大點集的基數為2n－2.因而，對于在平面上m×n的網格點中，是否會有類似的結果，比如不構成直角三角形的最大點集的基數為m＋n－2.以下本文將用坐標投影法和代數方法分別證明這個結果是正確的.并且令平面上m×n的網格點中不出現直角的最大點集的基數為 f（m，n）.

定理1在平面上的m×n網格點中，f（m，n）＝m＋n－2.

證明：（1）坐標投影法

對于平面上的任意一個m×n網格點，在滿足任意三個點不構成直角的條件下，一定能夠找到該網格點上大矩形的四個頂點中必有兩個點是不能取的，否則它們會出現直角.所以選取這兩個空點中任意一個點作為原點，同時以該點所對應大矩形的邊為坐標軸作一個平面直角坐標系O－xy，如圖1所示.

圖1 平面上10×20的網格點

為了尋找網格點中無直角的最大點集，應該盡量多的選擇使任意三個點不構成直角的點，對于這類構造得到的點集，可以分三種情形：1）點在x軸或y軸上；2）兩個及兩個以上點的橫坐標或縱坐標相同；3）其他情形的點.對于這三種類型的點，在使用投影法將這些點投影到坐標軸上的過程中，優先安排第一類點，然后考慮第二類點的投影，最后進行第三類點的投影.

1）點在x軸或y軸上

對于這種類型的點，仍然保持點的位置不變.

2）兩個及兩個以上點的橫坐標或縱坐標相同（不包含坐標軸上的點）

對于這種類型的點，可以將這些點投影到坐標軸上，而不會影響原點集的總個數，這是因為兩個及兩個以上的點處于同一直線上時，它們有相同的橫坐標或者縱坐標，那么就不能再出現與它們縱坐標或者橫坐標相同的點.（如圖2，兩個黑點確定后，白色虛點則不能出現）

圖2 平面網格點中縱坐標相同的點的投影

3）其他情形的點

對于這種情況的點，要么是非坐標軸上的單個點，要么點與點之間是處于對角的情形，這類點可以將其投影在前兩類點投影后的坐標軸仍為空點處的位置，并且它不會影響點集總數的變化，這里要求任意一個點不與其他任一點處于同一條直線，否則屬于第二種情形考慮.點集投影示例如圖3（其中，黑點表示未投影或投影后點的位置，白色虛點表示投影前點的位置）.

圖3 平面網格點中單個點與對角點的投影

由于滿足條件的點都可以通過以上三種情形進行投影，在規定的順序下最后可以將所有點投影到x軸和y軸上，并使每個點都不重復投影，投影后所得到的點數最多的情形如圖4.

圖4 平面網格點中投影后所得到的點數最多的情形

顯然，這樣所構造的點都不能構成直角三角形，并且圖4中的點集情形就是平面上m×n網格點中不出現直角的最大點集，又由坐標軸上的點總數為m＋n－1，而原點為空點，因此有 f（m，n）＝m＋n－2.

（2）代數法

由圖1可知，建立坐標系O－xy后，m×n網格點就是橫坐標介于0和n－1之間，縱坐標介于0和m－1之間的整點構成的網格點.那么假設，即 P 表示平面上m×n網格點中不出現直角的最大點集；

Px＝，Px表示該網格點中滿足條件且每行點集的點數大于1的所有點集；

Py＝，Py表示該網格點中滿足條件且每列點集的點數大于1的所有點集；

顯然有 Px∩Py＝?，

當 m＝2或n＝2時，m×n網格點中的最大點集的基數為f（m，n）＝n或f（m，n）＝m.

當m≠2且n≠2時，m×n網格點中的每行或每列的單點個數必小于等于m－1或n－1，否則f（m，n）不是網格點中的最大點集的基數，與假設矛盾.

因此有，2f（m，n）－m－n＋2≤f（m，n），則有 f（m，n）≤m＋n－2.

綜上所述，f（m，n）＝m＋n－2.

2 結論與展望

本文主要是對二維平面網格點中不出現直角的最大點集進行討論，得到了平面上m×n網格點中不出現直角的最大點集的基數為m＋n－2，并分別給出坐標投影法與代數法的兩種證明；另外，如果將網格點中任意三個點不構成直角的問題轉化為網格點中過原點而不構成直角的問題，那么對于n×n網格點與m×n網格點中過原點而無直角的最大點集的基數分別是多少呢？這也是我們下一步將要研究的內容.

[1]ABBOTT H L.On a conjecture ofErd?s and Silverman in combinatorial geometry[J].Journal of Combinatorial Theory，1980，29（3）：380-381.

[2]GAMBLE B，PULLEYBLANK W，REED B，et al.Right angle free subsets in the plane[J].Graphs＆Combinatorics，1995，11（2）：121-129.

[3]ELEKES G.A note on a problem of Erd?s on right angles[J].Discrete Mathematics，2009，309（16）：5253-5254.

[4]HARANGI V，KELETI T，KISS G，et al.Howlarge dimension guarantees a given angle?[J].Monatshefte Für Mathematik，2012，171（2）：169-187.

[5]BENNETTM.Extremal results regardingright angles in vector spaces over finite fields[EB/OL].[2017-03-23].https://arxiv.org/pdf/1511.08942.pdf.

[6]GE G，SHANGGUAN C.Rank counting and maximum subsets ofcontaining no right angles[EB/OL].[2017-03-23].https://arxiv.org/abs/1612.08255.