Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Matrix-free proof of a regularity characterization"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: Matrix-free proof of a regularity characterization. | Matrix-free proof of a regularity characterization A. Czygrinow Department of Mathematics and Statistics Arizona State University Tempe Arizona 85287 USA andrzej@math.la.asu.edu B. Nagle Department of Mathematics and Statistics University of Nevada Reno Nevada 89557 USA nagle@unr.edu Submitted May 28 2003 Accepted Oct 7 2003 Published Oct 13 2003 MR Subject Classifications 05C35 05C80 Abstract The central concept in Szemeredi s powerful regularity lemma is the so-called e-regular pair. A useful statement of Alon et al. essentially equates the notion of an e-regular pair with degree uniformity of vertices and pairs of vertices. The known proof of this characterization uses a clever matrix argument. This paper gives a simple proof of the characterization without appealing to the matrix argument of Alon et al. We show the e-regular characterization follows from an application of Szemeredi s regularity lemma itself. 1 Introduction The well-known Szemeredi Regularity Lemma 7 cf. 4 or 5 may be the single most powerful tool in extremal graph theory. Roughly speaking this lemma asserts that every large enough graph may be decomposed into constantly many random-like induced bipartite subgraphs i.e. e-regular pairs . A property of the e-regular pairs obtained from Szemeredi s lemma is studied in this note. Suppose G U u V E is a bipartite graph. For nonempty subsets U c U and V c V let G U V u v E E u E U v E V be the subgraph of G induced on U and V . Set d U V IG U V U -1 V -1 to be the density of U and V . For e 0 we say G U u V E is e-regular if for all U c U U s U and V c V V eV we have1 d U V d U V e. 1For simplicity of calculations in this paper s a b t is short for a b t s a b t. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R39 1 1.1 Equivalent conditions for e-regularity We consider the following two conditions for a bipartite graph G U u V E with fixed density d where whenever needed we assume U and V are sufficiently large . For 0 e 5 1 consider G1 G1 e G is .