tailieunhanh - Báo cáo toán học: "A Permutation Regularity Lemma"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Permutation Regularity Lemma. | A Permutation Regularity Lemma Joshua N. Cooper Institute for Theoretical Computer Science ETH-Zurich Zurich Switzerland cooper@ Submitted May 17 2004 Accepted Mar 4 2006 Published Mar 14 2006 Mathematics Subject Classification 05D40 Abstract We introduce a permutation analogue of the celebrated Szemeredi Regularity Lemma and derive a number of consequences. This tool allows us to provide a structural description of permutations which avoid a specified pattern a result that permutations which scatter small intervals contain all possible patterns of a given size a proof that every permutation avoiding a specified pattern has a nearly monotone linear-sized subset and a thin deletion result. We also show how one can count sub-patterns of a permutation with an integral and relate our results to permutation quasirandomness in a manner analogous to the graph-theoretic setting. 1 Introduction The Szemeredi Regularity Lemma a tool developed in the early 1970 s in service of the combinatorial milestone now known as the Szemeredi Theorem has turned out to be one of the most useful tools in graph theory ever discovered. In essence it says that any graph can be approximated by a small collection of random-like graphs. This powerful structural characterization allows one to answer questions about graphs by taking such a Szemeredi partition and then addressing the question by using known facts about random graphs. A number of variants of the Regularity Lemma or Uniformity Lemma as it is sometimes called have emerged since the publication of the original. Versions of it giving structural decompositions of hypergraphs have been used in many contexts and a few results have addressed the difficult case of sparse graph regularity. The reader is encouraged to read the excellent surveys of Komlos and Simonovits 9 and Kohayakawa and Rodl 8 to learn about how and where the Lemma is used how it is proved and what its limitations are. Supported by NSF grant DMS-0303272. THE .