I want to approximate the properties of a given, deterministic, undirected Graph $G$ without multiple edges. To be precise: I want to know the probability $P$ that $G$ with $n$ edges and $z$ vertices contains a clique $K_x$ of size $x$.

My intuition is, that probability of two vertices being connected by an edge in a random graph is equivalent to the density $den(G)$ of a given, deterministic Graph, hence i could use the following formula from the book "A Guide to Graph Colouring" by R. Lewis (2015), formulated for random graphs, $p$ being the probability that two vertices are connected by an edge:

$P(\exists K_x \subseteq G) = 1-(1-p^{\binom{x}{2}})^{\binom{n}{x}}$

and substitute $p$ with the $den(G) = \dfrac{n}{\frac{m(m-1)}{2}}$, $m$ being the number of edges of a complete Graph $K_z$

Is that intuition correct? If so, how can i argue that this is correct or even proof it?

Edited according to comments to make my question more clear.

  • $\begingroup$ If the graph is given, it's not clear what role probability plays. Are you trying to estimate properties of a deterministic graph using probabilistic arguments? Or is $G$ in fact a random graph? $\endgroup$ – joriki Apr 16 '16 at 22:29
  • $\begingroup$ Yes, i am trying to estimate the properties of a deterministic graph (my application being that the edge/vertex count is too large to actutally find a k-sized clique) $\endgroup$ – Migano Apr 16 '16 at 22:35
  • $\begingroup$ Short answer, yes, this kind of probabilistic arguments to work with big deterministic objects can be correct, but you have to be precise about the guarantees you want on your result. It's basically the idea behind 'property testing'. $\endgroup$ – Graffitics Apr 17 '16 at 9:01

Your Answer

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

Browse other questions tagged or ask your own question.