PRoxy Diary_ [研究] Additive Combinatorics最近新しいこと勉強してないなと思ったので、CSの一部で大流行しているAdditive Combinatoricsを始めてみることにしました。まだ内容は部分的にしか理解していませんが、Additive CombinatoricsではSum Product Theoremが中心的な話題のようです。体Aに対してA+A={a+b:a∈A,b∈A}, A*A={a*b:a∈A,b∈A}と定義すると、Sum Product Theoremというのは、あるεが存在して、任意の体Aに対して、|A+A|>|A|^(1+ε)または|A*A|>|A|^(1+ε)が成り立つという定理です。有限体バージョンも有ります。で、組み合わせ幾何とか数論とかグラフ理論とか確率的検査証明とかに応用できるらしい。応用できすぎ。グラフ理論では主にSzemeredi's Re
