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

Question

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?

Answer 1

Let $T$ be any tree of size $c$, and let $p_n(T)$ be the probability that a uniformly chosen tree $T_n$ of size $n$ contains a copy of $T$. I claim that $p_n(T)\to1$ as $n\to\infty$ (which implies what you want).

A tree can be coded by its contour function (or Dick path); a random tree of size $n$ (say, of $n$ edges) corresponds to a random walk excursion conditioned to come back to $0$ after $2n$. Now, look at the contour function of $c$: we want to know whether this occurs somewhere along that of $T_n$ (this will imply that $T_n$ contains a copy of $T$). But given the first $m$ steps of $T_n$ (for $m \leq n/2-2c$), this occurs on the interval $[m,m+2c]$ with probability of order $e^{-\lambda c}$, so it will occur /somewhere/ with probability going to $1$ as long as $c$ is fixed.

Maybe there is some bookkeeping to be done, e.g. maybe this is only for binary trees or something; and certainly the lower bound on $p_n$ is very bad. But it seems to at least partially answer the question.

Answer 2

We can ask not only that something appears as a subtree, but that it appears as a "limb". A limb of a tree $T$ at a vertex $v$ is a maximal subtree of $T$ that includes $v$ and a neighbouring vertex. (Informally, separate $T$ at $v$ with each fragment getting its own copy of $v$; these fragments are the limbs.) Schwenk proved in 1971 that the number of (unlabeled) trees of order $n$ containing a given limb depends only on the size of the limb and not on its structure. From this he proved that almost all trees contain any given subtree as a limb. This is quite a bit stronger than what you request.

MR0384582. Schwenk, Allen J. Almost all trees are cospectral. New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), pp. 275–307. Academic Press, New York, 1973.

Answer 3

This sort of statement is often very strongly true - look at the pendant appearances theorem of McDiarmid, Steger and Welsh, which guarantees that for several natural graph classes (trees and planar are both included, IIRC the theorem is for monotone addable families), not only do you see one copy of any given small object from the class in a randomly chosen large member, you actually see linearly many copies as pendant subgraphs with exponentially good probability. But you have to be slightly careful generalising: I think that it is not true that graphs with genus g contain all small graphs with genus g: you are unlikely to find a large clique (even if that clique does have genus g) as what is left after removing the clique has to have genus much smaller than g, which is too restrictive to be likely.