Skip to main content
edited title
Link
Jernej
  • 3.5k
  • 1
  • 27
  • 41

Almost all graphs have a subgraph from a large class of graphs with constant degreeorder

Source Link
Jernej
  • 3.5k
  • 1
  • 27
  • 41

Almost all graphs have a subgraph from a large class of graphs with constant degree

I will pose the question in relation to trees but the more general question that can be deduced from the title of this post is also very interesting.

I suspect the question might have a very trivial answer using some of the relatively modern tools of which I am unaware.

Denote by $T_k$ the set of all trees on $k$ vertices (up to isomorphism). Let $c$ be a positive integer and let $T$ be a subset of $T_c$ such that $$ |T| > \frac{|T_c|}{2} $$

For $n \geq c$ let $p_n$ be the probability that a tree, chosen uniformly at random from $T_n$ contains as a subgraph at least one tree from $T.$

Is the following statement true or false?

$p_n \rightarrow 1$ as $n \rightarrow > \infty \; \; (1)$ ?

It seems to me that the following does not hold if we consider labeled trees, but I am not sure how to smartly compute the ratio $\frac{T_n'}{T_n}$ where $T_n'$ is the subset of all trees from $T_n$ such that every graph in $T_n'$ has some subgraph from $T.$

Is the above statement true? Is there any way to relax the inequality? If not, is there a way to (non trivially) restrict the inequality so that $(1)$ holds?