On Emergence of Dominating Cliques in Random Graphs
| dc.creator | Nehez, Martin | |
| dc.creator | Olejar, Daniel | |
| dc.creator | Demetrian, Michal | |
| dc.date | 2008-05-14 | |
| dc.date.accessioned | 2026-07-07T09:38:51Z | |
| dc.date.available | 2026-07-07T09:38:51Z | |
| dc.description | Emergence of dominating cliques in Erdös-Rényi random graph model ${\bbbg(n,p)}$ is investigated in this paper. It is shown this phenomenon possesses a phase transition. Namely, we have argued that, given a constant probability $p$, an $n$-node random graph $G$ from ${\bbbg(n,p)}$ and for $r= c \log_{1/p} n$ with $1 \leq c \leq 2$, it holds: (1) if $p > 1/2$ then an $r$-node clique is dominating in $G$ almost surely and, (2) if $p \leq (3 - \sqrt{5})/2$ then an $r$-node clique is not dominating in $G$ almost surely. The remaining range of probability $p$ is discussed with more attention. A detailed study shows that this problem is answered by examination of sub-logarithmic growth of $r$ upon $n$. | |
| dc.description | to appear in Proc. 2nd Int. Conf. on Math. and Applications in Information Technology, Lahore Univ. of Management, Lahore, Pakistan, 2008 | |
| dc.identifier | https://arxiv.org/abs/0805.2105 | |
| dc.identifier | http://arxiv.org/abs/0805.2105 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160961 | |
| dc.subject | Combinatorics | |
| dc.subject | Information Theory | |
| dc.title | On Emergence of Dominating Cliques in Random Graphs | |
| dc.type | text |