tailieunhanh - Báo cáo toán học: "A simple algorithm for constructing Szemer´di’s Regularity Partition e"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A simple algorithm for constructing Szemer´di’s Regularity Partition e. | A simple algorithm for constructing Szemeredi s Regularity Partition Alan Frieze Department of Mathematical Sciences Carnegie Mellon University. alan@ Ravi Kannan Department of Computer Science Yale University. kannan@ Submitted November 25 1998 Accepted March 15 1999. Abstract We give a simple constructive version of Szemeredi s Regularity Lemma based on the computation of singular values of matrices. Mathematical Reviews Subject Numbers 05C85 68R10. 1 Introduction Szemeredi s Regularity Lemma 9 is one of the most powerful tools of extremal graph theory . One can only agree with that opening sentence of the Supported in part by NSF grant CCR-9530974. 1Supported in part by NSF grant CCR-9528973. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 6 1999 R17 2 paper by Komlos and Simonovits 6 . It has many many applications and we refer the reader to this excellent survey. The Regularity lemma is often used to prove the existence of certain objects and if in addition one wants to construct them then one needs a constructive version of the lemma. This was provided by Alon Duke Lefmann Rodl and Yuster 1 . Subsequently Frieze and Kannan 3 4 gave a different version and extended it to deal with hypergraphs see also Czygrinow and Rodl 2 . In this note we give another construction based on the construction of singular values of matrices. The proofs in 1 3 4 are somewhat technical. The result of this paper follows quite easily from a simple lemma relating non-regularity and largeness of singular values. Szemeredi s Lemma Let G V E be a graph with n vertices and let A be its adjacency matrix. For a disjoint pair of subsets A B c V let e A B denote the number of edges between A and B. The density d A B is defined by d A B e A B d A B A B A disjoint pair A B c V is said to be e regular if for every X c A with XI e A and Y c B with YI e B we have d X Y d A B I e. Theorem 1 Szemeredi s Regularity Lemma For every e 0 and integer m 0 there are integers P