Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Subgraph densities in signed graphons and the local Simonovits–Sidorenko conjecture"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Subgraph densities in signed graphons and the local Simonovits–Sidorenko conjecture. | Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture László Lovasz Institute of Mathematics Eotvos Lorand University Budapest Hungary Submitted Feb 17 2011 Accepted Jun 6 2011 Published Jun 14 2011 Mathematics Subject Classification 05C35 Abstract We prove inequalities between the densities of various bipartite subgraphs in signed graphs. One of the main inequalities is that the density of any bipartite graph with girth 2r cannot exceed the density of the 2r-cycle. This study is motivated by the Simonovits-Sidorenko conjecture which states that the density of a bipartite graph F with m edges in any graph G is at least the m-th power of the edge density of G. Another way of stating this is that the graph G with given edge density minimizing the number of copies of F is asymptotically a random graph. We prove that this is true locally i.e. for graphs G that are close to a random graph. Both kinds of results are treated in the framework of graphons 2-variable functions serving as limit objects for graph sequences which in this context was already used by Sidorenko. Research supported by ERC Grant No. 227701. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P127 1 Contents 1 Introduction 2 2 Preliminaries 4 2.1 Notation. 4 2.2 Kernel operators and their norms. 4 3 Density inequalities for signed graphons 6 3.1 Ordering signed graphons . 6 3.2 A generalized Cauchy-Schwarz inequality. 7 3.3 Inequalities between densities . 8 3.4 Special graphs and examples. 10 3.5 The main inequalities between graphs. 13 4 Local Sidorenko Conjecture 18 5 Variations 19 1 Introduction Let F be a bipartite graph with k nodes and l edges and let G be any graph with n nodes and m p n edges. Simonovits 3 10 conjectured that the number of copies of F in G is at least pl k o plnk where we consider k and l fixed and n X . Sidorenko 7 8 9 conjectured a stronger exact inequality. To state this formulation we count homomorphisms instead of copies of F. Let hom F G .