0
$\begingroup$

If I look at the distribution of the number of small subgraphs in the random graph isomorphic to a connected graph $H$, this is asymptotically Poisson.

What proportion of these small subgraphs intersect another, fixed subgraph?

Also, what if I want them to intersect in a specific way, not just arbitrarily? Do the subgraphs occur on vertices that are selected uniformly at random, so the `striking' probability is just the probability I select those vertex, chosen uniformly at random?

$\endgroup$
1
$\begingroup$

Given $G,H$ two finite connected graphs, let $H_1,...,H_k$ be all the connected graphs obtained as a union of $G$ and $H$ (the connectedness of the $H_i$ implies that $H$ and $G$ intersect). Then making the sum for $i$ of the occurences of $H_i$ as a subgraph, for $i$ between $1$ and $k$, gives the answer to the first question. For the second question simply count the number of occurences of the $H_i$ that you like. Sorry I did not understand the last question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.