text: 數學上，塞邁雷迪正則性引理斷言，給定任意一個足夠大的圖，都可以將其頂點集劃分成若干個差不多一樣大的子集，使得幾乎每兩個不同的子集之間的邊，都具有隨機二部圖的性質。塞邁雷迪於 1975 年引入了該引理較弱的版本，其只適用於二部圖，用作證明塞邁雷迪定理，後來再於 1978 年證明瞭完整的版本。及其合作者和高爾斯將正則性方法推廣到超圖上。定義和引理敍述.塞邁雷迪正則性引理的嚴格敍述須用到下列定義。設 "V" 為其頂點集。密度.設 ("X", "Y") 的密度為formula_1其中 "Y" 中的邊的集合。"ε"-正則.對於 "B" ⊆ "Y", 都有formula_2"ε"-正則劃分.設 "ε"-正則劃分，若：利用上述定義，可以寫出引理的嚴格敍述。正則性引理.對任意的 "k" 份。引理的證明所給出的 "ε"−1/16 次疊代冪次。由此可見，最佳的上界必定位於 中的第 4 層，因此不屬初等遞迴函式。推廣.、和塞邁雷迪·安德烈其後證明瞭blow-up 引理 ，其斷言塞邁雷迪正則性引理中的正則對，在特定意義下與完全二部圖具有同樣的性質。若考慮將大而疏的圖，嵌入到一個稠密的圖中，則適用 blow-up 引理來深入研究該嵌入的性質。陶哲軒以機率方法證明瞭一條不等式，其推廣了塞邁雷迪正則性引理。注意，不可能在塞邁雷迪正則性引理中，證明「所有」對都正則。原因是，一些圖確實需要劃分中有若干對頂點集非正則，儘管按照正則性引理，這樣的對只佔很小一部分。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 塞邁雷迪正則性引理
metadata: https://zh.wikipedia.org/wiki?curid=6382813