對一致超圖頂點集等分情形的Frankl－R?dl正則性引理

張作作，李國全

對一致超圖頂點集等分情形的Frankl－R?dl正則性引理

張作作，李國全

（天津師范大學數(shù)學科學學院，天津300387）

1992年Frankl和R?dl將關(guān)于圖的Szemerédi正則性引理推廣到一致超圖，其結(jié)論適用于對超圖頂點集進行一般分割的情形．當對超圖頂點集的分割是等分時，本研究得到了Frankl－R?dl結(jié)論的具體加強形式．

一致超圖；ε－正則性；指標增長性估計

1976年，Szemerédi證明了圖的正則性引理［1］．之后這個定理得到了廣泛的應(yīng)用．特別地，Ruzsa等［2］用它重新證明了關(guān)于長度為3的算術(shù)數(shù)列的密度定理：max｛｜A｜：A［n］，A中不含長度為3的算術(shù)數(shù)列｝＝o（n），此處，［n］｛1，2，…，n｝．

眾所周知，關(guān)于任意長度的算術(shù)數(shù)列的密度定理是成立的［3］．將Ruzsa與Szemeréd的方法推廣到任意長度的算術(shù)數(shù)列的情形，成為研究超圖的正則性理論的動機，超圖正則性理論最終由Nagle、R?dl、Schacht、Skokan［4－7］以及Gowers［8］建立．

R?dl學派的超圖正則性理論奠基于1992年Frankl和R?dl的文章［9］．在這篇文章中，他們提出了Szemerédi正則性引理到一致超圖的一種推廣形式．他們是在對超圖頂點集進行一般分割的前提下進行討論的，當對超圖的頂點集進行等分時，本研究得到了Frankl－R?dl結(jié)論的具體加強形式．

1 基本概念及主要結(jié)論

設(shè)r∈N＋，r≥2，若E［V］r｛AV：｜A｜＝r｝，則稱H為V上的r－一致超圖，簡稱r－圖．特別地，當r＝2時，則為眾所周知的圖．

設(shè)H＝（V，E）為一個r－圖，ν≥r，｛V1，V2，…，Vν｝為V的一個分割，即V1，V2，…，Vν為V的兩兩不交的非空子集，且V1∪V2∪…∪Vν＝V．

設(shè)1≤i1＜i2＜…＜ir－1≤ν，I｛i1，i2，…，ir－1｝，記VI｛Vi1，Vi2，…，Vir－1｝．定義（r－1）－圖K（I）

定義2（H－系統(tǒng)） 設(shè)｝，｛GαI：1≤α≤m｝為K（I）的一個分割，這里GαI均為VI上的邊兩兩不交的（r－1）－部（r－1）－圖，且＝E（K（I）），則稱為一個H－系統(tǒng)．

設(shè)1≤j1＜…＜jr≤ν，J｛j1，…，jr｝，1≤i≤r，JiJ＼｛ji｝，GαiJiK（Ji）．記α（α1，…，αr）．

定義r－圖R（GαJ）如下：

定義H關(guān)于GαJ的密度為：

定義3（ε－正則性） 設(shè)ε＞0．設(shè)GαJ和FβJ為兩個組，記FβJ≤GαJ，如果i∈［r］，F(xiàn)βiJiGαiJi，其中αi表示α的第i個分量．當背景明確時，也記（J，β）≤（J，α）．

i）ε－正則組：稱組GαJ為ε－正則的，如果對任意組FαJ≤GαJ，當r （FαJ）≥εr （GαJ）時，均有d （FαJ）－d （GαJ）≤ε，否則，稱GαJ為ε－非正則的．

ii）ε－正則系統(tǒng)：稱H－系統(tǒng)為ε－正則的，如果

Frankl－R?dl有如下結(jié)論：

定理1［9］ε∈（0，1），t∈N＋，t0（ε，t），n0（ε，t）∈N＋具有下列性質(zhì)：

設(shè)ν，r∈N＋，ν≥r≥2，｛V1，V2，…，Vν｝為V的一個分割，nV，H為V上的一個r－圖．當n≥ n0（ε，t）時，存在一個ε－正則的H－系統(tǒng)

為了加強Frankl－R?dl的結(jié)論，下面考慮等分情況，即V1＝V2＝…＝Vν．在這種情況下，考慮標有例外圖的H－系統(tǒng)其中G0I被標記為例外（r－1）－圖，其邊集可為空集．此時H－系統(tǒng)稱為ε－正則的，如果

本研究主要結(jié)論如下：

設(shè)ν，r∈N＋，ν≥r≥2，｛V1，V2，…，Vν｝為V的一個分割，且V1＝V2＝…＝Vν＝n，H為V上的一個r－圖．當n≥tr－11時，存在一個ε－正則的H－系統(tǒng)滿足下列條件：

2 定理2的證明

對標記例外圖的H－部分系統(tǒng)定義指標：

其中：Γ0（S），Γ1（S）定義如下：

由上面的定義易得ind（S）≤1．

引理1（Cauchy－Schwarz不等式） 設(shè)A為一個有限集，a∈A，μa、da≥0，記．如果

證明

從而

證明 證明分為以下三步：

1．構(gòu)造S的細分H－系統(tǒng)S″，使其具有指標增長性．

對S的每個ε－非正則組GαJ，取定一個組FβJ≤GαJ，適合r （FαJ）≥εr （GαJ），d （FαJ）－d （GαJ）＞ε．設(shè)I∈設(shè)q（I）表示包含GαI，α∈［m］的ε－非正則組的個數(shù)，則有

1）當q（I）＝0時，記LαIGαI，α∈［m］．此時，記p（I）m．

從而m≤p（）I≤m2q（I）≤m2（ν－r＋1）mr＝ξ（m）．此外，設(shè)L0IG0I．從而可得S的細分H－系統(tǒng)S″

2．指標增長性估計．

對一個組GαJ，有從而由Cauchy－Schwarz不等式有此外，若GαJ為ε－非正則的，因為

所以

又因為Γ0（S″）為Γ0（S）的一個細分，故由引理2有σ（Γ0（S″））≥σ（Γ0（S）），因此

3．由S″構(gòu)造滿足條件的等分H－系統(tǒng)S′．

1）當‖LαI‖≥d時，將LαI等分為個大小為d的圖，將剩下的一個大小小于d的圖放入AI；

2）當‖LαI‖＜d時，將LαI放入AI．

對每個LαI都做如上操作，再將LI0并入EI0，得到｛EαI：1≤α≤kI｝∪AI．

下面驗證S′滿足引理的條件．

設(shè)mc＝［ξ（m）］2d＋e，0≤e＜［ξ（m）］2≤d．因為kId≤mc，所以

又因為kId＋p（I）≥mc，所以

iii）因為Γ0S（）′∪Γ1S（）′為Γ0S（）″∪Γ1S（）″的一個細分，由引理2及2中結(jié)論有：

此時，若S1為ε－正則的，則定理得證；否則，由引理3可得H－系統(tǒng)S2＝滿足引理3的條件．

由于n足夠大，可重復(fù)上面的迭代．因為對任意H－系統(tǒng)S，均有ind（S）≤1，所以迭代最多經(jīng)過s步終止．設(shè)得到系統(tǒng)

令t0（t，ε）max ｛nr1－1，hs（m1）｝．

［1］ SZEMEREDI E．Regular Partitions of Graphs［M］．Proc Colloq Int CNRS，1976．

［2］ RUZSA I，SZEMEREDI E．Triple systems with no six points carrying three triangles［C］／／Keszthely：Proc Fifth Hungarian Colloq，1976，2：939－945．

［3］ SZEMEREDI E．On sets of integers containing no kelements in arithmetic progression［J］．Acta Arithmetica，1975，27：199－245．

［4］ R?DL V，SKOKAN J．Regularity lemma for k－uniform hypergraphs［J］．Random Structures and Algorithms，2004，25：1－42．

［5］ NAGLE B，R?DL V，SCHACHT M．The counting lemma for regular k－uniform hypergraphs［J］．Random Structures and Algorithms，2006，28：113－179．

［6］ R?DL V，SCHACHT M．Regular partition of hypergraphs：Regularity lemmas［J］．Combin Probab Comput，2007，16（6）：833－885．

［7］ R?DL V，SCHACHT M．Regular partitions of hypergraphs：Counting lemmas［J］．Combin Probab Comput，2007，16（6）：887－901．

［8］ GOWERS W T．Hypergraph regularity and the multidimensional Szemerédi theorem［J］．Ann Math，2007，166（3）：897－946．

［9］ FRANKL P，R?DL V．The uniformity lemma for hypergraphs［J］．Graphs Combinat，1992，8（4）：309－312．

（責任編校 馬新光）

Frankl－R?dl’s regularity lemma for uniform hypergraphs on equitable partition of vertex set

ZHANG Zuo－zuo，LI Guo－quan
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

In 1992，F(xiàn)rankl and R?dl extended Szemerédi regularity lemma for graphs to uniform hypergraphs，the results of which are for general partition of the vertex set．A concrete strengthening form of Frankl－R?dl’s results for equitable situation is obtained．

uniform hypergraph；ε－regularity；estimate on index increment

book=2012,ebook=7

O157．5

A

2011－07－01

張作作（1984－），女，碩士研究生．

李國全（1969－），男，教授，博士，主要從事調(diào)和分析方面的研究．為以Vi1，Vi2，…，Vir－1為頂點類的完全（r－1）－部（r－1）－圖，且邊集非空，即

1671－1114（2012）02－0026－06