Counting trees in graphs

Jacques Verstraete¹ ; Dhruv Mubayi²

¹University of California, San Diego
²University of Illinois, Chicago

The electronic journal of combinatorics, Tome 23 (2016) no. 3

Résumé

Erdős and Simonovits proved that the number of paths of length $t$ in an $n$-vertex graph of average degree $d$ is at least $(1 - \delta) nd(d - 1) \cdots (d - t + 1)$, where $\delta = (\log d)^{-1/2 + o(1)}$ as $d \rightarrow \infty$. In this paper, we strengthen and generalize this result as follows. Let $T$ be a tree with $t$ edges. We prove that for any $n$-vertex graph $G$ of average degree $d$ and minimum degree greater than $t$, the number of labelled copies of $T$ in $G$ is at least \[(1 - \varepsilon) n d(d - 1) \cdots (d - t + 1)\] where $\varepsilon = O(d^{-2})$ as $d \rightarrow \infty$. This bound is tight except for the term $1 - \varepsilon$, as shown by a disjoint union of cliques. Our proof is obtained by first showing a lower bound that is a convex function of the degree sequence of $G$, and this answers a question of Dellamonica et. al.

Détail

DOI : 10.37236/6084

Classification : 05C30, 05C05, 05C38, 05C60, 05C12, 05C07, 05C35
Mots-clés : embedding trees, paths, random embedding, Jensen's inequality