Skip to main content
Added top-level tag
Link
gmvh
  • 3.1k
  • 6
  • 27
  • 45
deleted 2 characters in body
Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113

Related to this question, which I asked at MSE, I'd like to ask this one here:

Consider a (large) graph $G$ and its setmulti-set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the multi-set of pointed graphs (one for each vertex) containing the vertex and all of its neighbours, together with all the edges between them.

Define the set $\Gamma(T)$ of all (random) graphs graphs having the same tile set $T$.

How would you calculate some expected properties $P$ of these graphs in the sense of "almost all graphs in $\Gamma(T)$ have property $P$". If "almost all" was to mean "in the limit $|V(G)| \rightarrow \infty$" one would interpret a given tile set $T$ as defining ratios of tiles, i.e. counting relative instead of absolute numbers per single (isomorphism class of) tile.

There are two "properties" literally all graphs in $\Gamma(T)$ do have: the (same) degree distribution and the (same) distribution of clustering coefficients. By which means do I find and calculate other properties that almost all graphs in $\Gamma(T)$ have?

Related to this question, which I asked at MSE, I'd like to ask this one here:

Consider a (large) graph $G$ and its set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the multi-set of pointed graphs (one for each vertex) containing the vertex and all of its neighbours, together with all the edges between them.

Define the set $\Gamma(T)$ of all (random) graphs having the same tile set $T$.

How would you calculate some expected properties $P$ of these graphs in the sense of "almost all graphs in $\Gamma(T)$ have property $P$". If "almost all" was to mean "in the limit $|V(G)| \rightarrow \infty$" one would interpret a given tile set $T$ as defining ratios of tiles, i.e. counting relative instead of absolute numbers per single (isomorphism class of) tile.

There are two "properties" literally all graphs in $\Gamma(T)$ do have: the (same) degree distribution and the (same) distribution of clustering coefficients. By which means do I find and calculate other properties that almost all graphs in $\Gamma(T)$ have?

Related to this question, which I asked at MSE, I'd like to ask this one here:

Consider a (large) graph $G$ and its multi-set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the multi-set of pointed graphs (one for each vertex) containing the vertex and all of its neighbours, together with all the edges between them.

Define the set $\Gamma(T)$ of all graphs having the same tile set $T$.

How would you calculate some expected properties $P$ of these graphs in the sense of "almost all graphs in $\Gamma(T)$ have property $P$". If "almost all" was to mean "in the limit $|V(G)| \rightarrow \infty$" one would interpret a given tile set $T$ as defining ratios of tiles, i.e. counting relative instead of absolute numbers per single (isomorphism class of) tile.

There are two "properties" literally all graphs in $\Gamma(T)$ do have: the (same) degree distribution and the (same) distribution of clustering coefficients. By which means do I find and calculate other properties that almost all graphs in $\Gamma(T)$ have?

Source Link
Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113

Random graphs defined by a set of tiles

Related to this question, which I asked at MSE, I'd like to ask this one here:

Consider a (large) graph $G$ and its set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the multi-set of pointed graphs (one for each vertex) containing the vertex and all of its neighbours, together with all the edges between them.

Define the set $\Gamma(T)$ of all (random) graphs having the same tile set $T$.

How would you calculate some expected properties $P$ of these graphs in the sense of "almost all graphs in $\Gamma(T)$ have property $P$". If "almost all" was to mean "in the limit $|V(G)| \rightarrow \infty$" one would interpret a given tile set $T$ as defining ratios of tiles, i.e. counting relative instead of absolute numbers per single (isomorphism class of) tile.

There are two "properties" literally all graphs in $\Gamma(T)$ do have: the (same) degree distribution and the (same) distribution of clustering coefficients. By which means do I find and calculate other properties that almost all graphs in $\Gamma(T)$ have?