More on quasi-random graphs,subgraph counts and graph limits |
| |
Institution: | 1. Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden;2. A. Rényi Institute of Mathematics, Budapest, Hungary |
| |
Abstract: | We study some properties of graphs (or, rather, graph sequences) defined by demanding that the number of subgraphs of a given type, with vertices in subsets of given sizes, approximatively equals the number expected in a random graph. It has been shown by several authors that several such conditions are quasi-random, but that there are exceptions. In order to understand this better, we investigate some new properties of this type. We show that these properties too are quasi-random, at least in some cases; however, there are also cases that are left as open problems, and we discuss why the proofs fail in these cases.The proofs are based on the theory of graph limits; and on the method and results developed by Janson (2011), this translates the combinatorial problem to an analytic problem, which then is translated to an algebraic problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|