平面網(wǎng)格點中無直角的最大點集構(gòu)造

趙紅濤，裴四寶

（華北電力大學數(shù)理學院，北京102206）

0 引言

1977年Erd?s和Silverman提出這樣一個問題：確定最大整數(shù)f（n），使得從平面上任意n個點的集合中可以找到f（n）個點，且這些點中任意三個點不會構(gòu)成一個直角三角形.他們得到對于一個 k×k的網(wǎng)格點中有 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維數(shù)保證一個給定角.隨后，關(guān)于點集中不出現(xiàn)直角的研究由歐氏空間轉(zhuǎn)為有限域上的討論，首先是2015年Michael Bennett在文獻[5]中研究了有限域上向量空間中的一些Erd?s-Falconer類問題，他證明了在有限域中不含直角的點集的最大基數(shù)，在有限域中過原點的任意兩個點不構(gòu)成直角的點集的最大基數(shù).2016年Ge和Shangguan在文獻[6]中利用多項式方法對有限域中不含直角的點集的最大基數(shù)給出了新的上界，并且得到此最大基數(shù)，其中n為有限域的維數(shù)，q為素數(shù).

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

1 平面網(wǎng)格點中不出現(xiàn)直角的最大點集

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

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

證明：（1）坐標投影法

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

圖1 平面上10×20的網(wǎng)格點

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

1）點在x軸或y軸上

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

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

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

圖2 平面網(wǎng)格點中縱坐標相同的點的投影

3）其他情形的點

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

圖3 平面網(wǎng)格點中單個點與對角點的投影

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

圖4 平面網(wǎng)格點中投影后所得到的點數(shù)最多的情形

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

（2）代數(shù)法

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

Px＝，Px表示該網(wǎng)格點中滿足條件且每行點集的點數(shù)大于1的所有點集；

Py＝，Py表示該網(wǎng)格點中滿足條件且每列點集的點數(shù)大于1的所有點集；

顯然有 Px∩Py＝?，

當 m＝2或n＝2時，m×n網(wǎng)格點中的最大點集的基數(shù)為f（m，n）＝n或f（m，n）＝m.

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

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

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

2 結(jié)論與展望

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

[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.