1
$\begingroup$

Is this statement true? If yes, I would like to be pointed to references containing its proof.

$\endgroup$
4
  • 4
    $\begingroup$ Don't almost all graphs have any particular finite graph as an induced subgraph in whatever model you have for random graphs? $\endgroup$ Sep 2 '16 at 10:03
  • $\begingroup$ @DouglasZare Of course not. Let the random gram $G_n$ be the Dirac distribution on the $n$-clique for example. But even without going to such trivial random graphs, no property of $G(n,1/2)$ can be generalized to "whatever (reasonable) model of random graphs". $\endgroup$
    – logicute
    Sep 3 '16 at 10:42
  • $\begingroup$ @logicute: Are you seriously saying that you use that model of random graph for something? There are multiple common models for random graphs where every finite graph occurs as an induced subgraph with high probability. You have to choose the growth rates of the parameters carefully to make the high probability statement correct and nontrivial. $\endgroup$ Sep 3 '16 at 12:06
  • $\begingroup$ @DouglasZare It was kind of a joke, but in general "any particular finite graph as an induced subgraph in whatever model" is really false in reasonable settings. Take as induced subgraph $K_4$ and as random graph model the preferential attachment for example that falsifies the statement. $\endgroup$
    – logicute
    Sep 3 '16 at 16:36

Browse other questions tagged or ask your own question.