摘要 :
We study the random planar graph process introduced by Gerke et al. [Random Structures Algorithms, 32 (2008), pp. 236--261]: Begin with an empty graph on n vertices, consider the edges of the complete graph Kn one by one in a rand...
展开
We study the random planar graph process introduced by Gerke et al. [Random Structures Algorithms, 32 (2008), pp. 236--261]: Begin with an empty graph on n vertices, consider the edges of the complete graph Kn one by one in a random ordering, and at each step add an edge to a current graph only if the graph remains planar. They studied the number of edges added up to step t for ``large"" t = \omega(n). In this paper we extend their results by determining the asymptotic number of edges added up to step t in the early evolution of the process when t = O(n). We also show that this result holds for a much more general class of graphs, including outerplanar graphs, planar graphs, and graphs on surfaces.
收起
摘要 :
In this paper we consider the degree of a typical vertex in two models of random intersection graphs introduced in [E. Godehardt, J. Jaworski, Two models of random intersection graphs for classification, in: M. Schwaiger, O. Opitz...
展开
In this paper we consider the degree of a typical vertex in two models of random intersection graphs introduced in [E. Godehardt, J. Jaworski, Two models of random intersection graphs for classification, in: M. Schwaiger, O. Opitz (Eds.), Exploratory Data Analysis in Empirical Research, Proceedings of the 25th Annual Conference of the Gesellschaft für Klassifikation e.V., University of Munich, March 14–16, 2001, Springer, Berlin, Heidelberg, New York, 2002, pp. 67–81], the active and passive models. The active models are those for which vertices are assigned a random subset of a list of objects and two vertices are made adjacent when their subsets intersect. We prove sufficient conditions for vertex degree to be asymptotically Poisson as well as closely related necessary conditions. We also consider the passive model of intersection graphs, in which objects are vertices and two objects are made adjacent if there is at least one vertex in the corresponding active model “containing” both objects. We prove a necessary condition for vertex degree to be asymptotically Poisson for passive intersection graphs.
收起
摘要 :
We consider random graphs on the set of vertices placed on the discrete d-dimensional torus. The edges between pairs of vertices are independent, and their probabilities depend on the distance between the vertices. Hence, the prob...
展开
We consider random graphs on the set of vertices placed on the discrete d-dimensional torus. The edges between pairs of vertices are independent, and their probabilities depend on the distance between the vertices. Hence, the probabilities of connections are naturally scaled with the total number of vertices via distance. We propose a model with a universal form of scaling, which yields a natural classification of the models. In particular, it allows us to identify the class models which fit naturally the theory of inhomogeneous random graphs. These models exhibit phase transition in change of the size of the largest connected component strikingly similar to the one in the classical random graph model. However, despite such similarities with G(n,p) the geometric random graphs are proved here to exhibit also a new type of phase transitions when it concerns the local characteristics, such as the number of triangles or the clustering coefficient.
收起
摘要 :
We propose a unifying framework for studying extremal problems related to graph minors. This framework relates the existence of a large minor in a given graph to its expansion properties. We then apply the developed framework to s...
展开
We propose a unifying framework for studying extremal problems related to graph minors. This framework relates the existence of a large minor in a given graph to its expansion properties. We then apply the developed framework to several extremal problems and prove in particular that: (a) Every K-s,K-s'-free graph G with average degree r (2 0; (b) Every C-2k-free graph G with average degree r (k >= 2 is a constant) contains a minor with average degree cr(k+1/2), for some constant c = c(k) > 0. We also derive explicit lower bounds on the minor density in random, pseudo-random and expanding graphs.
收起
摘要 :
We study conditions under which the treewidth of three different classes of random graphs is linear in the number of vertices. For the Erd?s- Rényi random graph G(n,m), our result improves a previous lower bound obtained by Kloks...
展开
We study conditions under which the treewidth of three different classes of random graphs is linear in the number of vertices. For the Erd?s- Rényi random graph G(n,m), our result improves a previous lower bound obtained by Kloks (1994) [22]. For random intersection graphs, our result strengthens a previous observation on the treewidth by Karoski et al. (1999) [19]. For scale-free random graphs based on the Barabsi-Albert preferential-attachment model, it is shown that if more than 11 vertices are attached to a new vertex, then the treewidth of the obtained network is linear in the size of the network with high probability.
收起
摘要 :
We initiate a general study of the feasibility of implementing (huge) random objects, and demonstrate its applicability to a number of areas in which random objects occur naturally. We highlight two types of measures of the qualit...
展开
We initiate a general study of the feasibility of implementing (huge) random objects, and demonstrate its applicability to a number of areas in which random objects occur naturally. We highlight two types of measures of the quality of the implementation (with respect to the desired specification): The first type corresponds to various standard notions of indistinguishability (applied to function ensembles), whereas the second type is a novel notion that we call truthfulness. Intuitively, a truthful implementation of a random object of Type T must (always) be an object of Type T, and not merely be indistinguishable from a random object of Type T. Our formalism allows for the consideration of random objects that satisfy some fixed property (or have some fixed structure) as well as the consideration of objects supporting complex queries. For example, we consider the truthful implementation of random Hamiltonian graphs as well as supporting complex queries regarding such graphs (e.g., providing the next vertex along a fixed Hamiltonian path in such a graph).
收起
摘要 :
There tend to be no related researches regarding the relationships between graph theory and languages ever since the concept of graph-semigroup was first proposed in 1991. In 2011, after finding out the inner co-relations among di...
展开
There tend to be no related researches regarding the relationships between graph theory and languages ever since the concept of graph-semigroup was first proposed in 1991. In 2011, after finding out the inner co-relations among digraphs, undirected graphs and languages, we proposed certain concepts including undirected graph language and digraph language; moreover, in 2014, we proposed a broaden concept–(V,R)-language and proved: (1) both undirected graph language and digraph language are (V,R)-languages; (2) both undirected graph language and digraph language are regular languages; (3) natural languages are regular languages. In this paper, we propose a new concept–Random Graph Language and build the relationships between random graph and language, which provides researchers with the possibility to do research about languages by using random graph theory.
收起
摘要 :
It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5-regular graph asymptotically almost surely has chromatic number at most 4. Here, we show th...
展开
It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5-regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5-regular graph is asymptotically almost surely equal to 3, provided a certain four-variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3-colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors.
收起
摘要 :
Write C(G) for the cycle space of a graph G, C-kappa(G) for the subspace of C(G) spanned by the copies of the kappa-cycle C-kappa in G, T-kappa for the class of graphs satisfying C-kappa(G)=C(G), and Q(kappa) for the class of grap...
展开
Write C(G) for the cycle space of a graph G, C-kappa(G) for the subspace of C(G) spanned by the copies of the kappa-cycle C-kappa in G, T-kappa for the class of graphs satisfying C-kappa(G)=C(G), and Q(kappa) for the class of graphs each of whose edges lies in a C-kappa. We prove that for every odd kappa >= 3 and G=G(n,p),
收起
摘要 :
Abstract Hyperbolic random graphs (HRGs) and geometric inhomogeneous random graphs (GIRGs) are two similar generative network models that were designed to resemble complex real-world networks. In particular, they have a power-law ...
展开
Abstract Hyperbolic random graphs (HRGs) and geometric inhomogeneous random graphs (GIRGs) are two similar generative network models that were designed to resemble complex real-world networks. In particular, they have a power-law degree distribution with controllable exponent $\beta$ and high clustering that can be controlled via the temperature $T$ .We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to $T = 0$ . We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, that is, they involve no approximation.Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify the desired expected average degree as input.Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straightforward inclusion does not hold in practice. However, the difference is negligible for most use cases.
收起