% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.39}{23(3)}{2016} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\xmin}{\textnormal{$x$-min}} \newcommand{\RR}{{\mathbb R}} \newcommand{\NN}{{\mathbb N}} \newcommand{\Zd}{{\mathbb Z}^d} \newcommand{\Ed}{{\mathbb E}^d} \newcommand{\PP}{{\mathbb P}} \newcommand{\EE}{{\mathbb E}} \newcommand{\el}[2]{#1\!\!\mod\! #2} \newcommand{\np}[1]{{#1}_{\!\scriptscriptstyle +}\!} \def\cn{\mbox{\rm cr}} \def\twr{\mbox{\rm twr}} \def\conv{\mbox{\rm conv}} \def\ex{{\rm{ex}}} \def\e{\epsilon} \parindent=0pt \parskip=6pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \begin{document} \title{\bf Counting trees in graphs} \date{\dateline{Apr 19, 2016}{Aug 11, 2016}{Aug 19, 2016} \\ \small Mathematics Subject Classifications: 05C} \medskip \author{ Dhruv Mubayi\thanks{Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL, 60607 USA. Research partially supported by NSF grant DMS-1300138. Email: {\tt mubayi@uic.edu}} \and Jacques Verstra\" ete\thanks{ Department of Mathematics, UCSD. E-mail: {\tt jacques@ucsd.edu}} } \maketitle \vspace{-0.2in} \begin{abstract} Erd\H{o}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 \geq 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 = (4t)^5/d^2$. 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. \end{abstract} \section{Introduction} If $H$ and $G$ are graphs, let $\mathsf{N}_H(G)$ denote the number of labelled copies of $H$ in $G$. More precisely, $\mathsf{N}_H(G)$ is the number of injections $\phi: V(H) \rightarrow V(G)$ such that $\phi(u)\phi(v)\in E(G)$ for every edge $uv$ of $H$. Let $N_G(v)$ denote the neighborhood of vertex $v$ in a graph $G$ and let $d_G(v) = |N_G(v)|$. Let $(a)_b = a(a - 1)(a - 2) \dots (a - b + 1)$ when $a \geq b \geq 1$ and $a$ is real and $b$ is an integer, and let $(a)_0 = 1$. Let $T$ be a $t$-edge tree and $G=(V,E)$ be a graph with minimum degree at least $t$. In this paper, we obtain lower bounds on $\mathsf{N}_T(G)$. This is a basic question in combinatorics, for example, the simple lower bound $\sum_{v \in V}(d(v))_t$ in the case when $T$ is a star is the main inequality needed for a variety of fundamental problems in extremal graph theory. Counting paths and walks in graphs has numerous applications, such as finding bounds on the spectral radius of the graph and the energy of a graph (see T\"{a}ubig and Weihmann~\cite{TW} and the references therein), as well as in standard graph theoretic reductions of combinatorial problems such as counting words over alphabets with forbidden patterns. \medskip Blakley and Roy~\cite{BR} used elementary linear algebraic methods to show that if $A$ is any symmetric pointwise non-negative matrix and $v$ is any pointwise non-negative unit vector, then for any $t \in \mathbb N$, $\bigl \geq \bigl^t$. If $t$ is even, this is a simple consequence of the fact that $A$ is diagonalizable and Jensen's Inequality applied to a convex combination of the $t$-th powers of the eigenvalues of $A$. When $A$ is the adjacency matrix of an $n$-vertex graph of average degree $d$, this shows that the number of walks of length $t$ is at least $nd^t$. There are now a number of proofs of this result, for instance another approach to counting walks was used by Sidorenko, using an analytic method and the tensor power trick~\cite{sidorenko}, as well as generalizations to various other inequalities involving walks (see~\cite{TW} and the references therein). \medskip Alon, Hoory and Linial~\cite{AHL} showed that the number of non-backtracking walks in an $n$-vertex graph $G$ of average degree $d$ and minimum degree at least two is at least $nd(d - 1)^{t - 1}$, which is again tight for $d$-regular graphs. A key fact in their proof is that if one considers a random walk of length $t$ on the graph, starting with a uniformly randomly chosen edge, then the distribution of every edge of the walk is also uniform. The method of Alon, Hoory and Linial~\cite{AHL} was generalized in Dellamonica et. al.~\cite{Detal} to show that the number of homomorphisms of a $t$-edge tree $T$ in $G$ is at least $nd \prod_{v \in V} d(v)^{(t - 1)d(v)/nd}$. By Jensen's Inequality, this is at least $nd^t$ when $G$ has no isolated vertices. \medskip In Problem 4 of~\cite{Detal}, the question of finding similar lower bounds for $\mathsf{N}_T(G)$ when $T$ is a tree is raised. In the case $T$ is a path with three edges, it was shown in~\cite{Detal} that $\mathsf{N}_T(G) \geq nd\prod_{v \in V} (d - 2)^{2d(v)/dn}$ when $G$ has minimum degree at least three. If $P$ is a $t$-edge path, and $G$ is a $d$-regular graph, then clearly $\mathsf{N}_P(G) \geq n(d)_t$ with equality for $d \geq t$ if and only if every component of $G$ is a clique. Erd\H{o}s and Simonovits~\cite{ES} showed that if $G$ is any graph of average degree $d$, then $\mathsf{N}_P(G) \geq n(d - o(d))_t$ as $d \rightarrow \infty$. In this paper, we answer Problem 4 of~\cite{Detal}, extend the result in~\cite{ES} to arbitrary trees and strengthen their lower bound to $n(d - O(1/d))_t$ as $d \rightarrow \infty$: \begin{theorem}\label{main} If $T$ is any $t$-edge tree and $G$ is an $n$-vertex graph of average degree $d \geq t$, and $\varepsilon_d = (4t)^5/d^2$, then \[ \mathsf{N}_T(G) \geq (1 - \varepsilon_d)n(d)_t.\] \end{theorem} This result is best possible up to the factor $1 - \varepsilon_d$ in view of the graph comprising $n/(d + 1)$ cliques of order $d + 1 \geq t + 1$ when $d+1$ is a positive integer dividing $n$, since these graphs have exactly $n(d)_t$ copies of $T$. Note that since $\varepsilon = O(1/d^2)$, Theorem \ref{main} implies $\mathsf{N}_T(G) \geq n(d - O(1/d))_t$ as $d \rightarrow \infty$. \medskip Since we do not have an example of a graph $G$ with $n$ vertices and average degree $d$ for which $\mathsf{N}_T(G) < n(d)_t$, we propose the following conjecture: \begin{conjecture} For every $t>1$, there exists $d_0 = d_0(t)$ such that for any tree $T$ with $t$ edges and any $n$-vertex graph $G$ with average degree $d \geq d_0$, $\mathsf{N}_T(G) \geq n(d)_t$. \end{conjecture} Once more the example of disjoint complete graphs of order $d + 1$ shows that this conjecture if true is best possible. Perhaps it is even true that if $d$ is an integer, then this is the only example where equality holds. \medskip This paper is organized as follows. In the next section, we determine a lower bound on $\mathsf{N}_T(G)$ for a $t$-edge tree $T$, as a function of the degree sequence of $G$. This answers Problem 4 of~\cite{Detal}. The proof of this result extends the method of~\cite{AHL} by carefully controlling the distribution of the edges in a random embedding of a tree in a graph of average degree $d$. The function of degrees is ``almost'' convex, and in Section 3 we give a suitable approximate form of Jensen's Inequality, which is used in Section 4 to derive Theorem \ref{main}. \section{Degree sequences and counting trees} As a stepping stone to Theorem \ref{main}, we are going to prove the following theorem, which gives a lower bound for $\mathsf{N}_T(G)$ in terms of the degree sequence of $G$, and addresses Problem 4 in~\cite{Detal}: \begin{theorem}\label{loc} Let $T$ be a $t$-edge tree, and let $G = (V,E)$ be an $n$-vertex graph with average degree $d$ and minimum degree $k > t > 1$. Then \begin{equation}\label{lb} \mathsf{N}_T(G) \geq nd \prod_{v \in V}\prod_{i = 3}^{t+1} (d(v) - i + 2)^{\frac{d(v) - i + 2}{(d - i + 2)n}\theta_i(v)} \end{equation} where for $3 \leq i \leq t + 1$, \begin{equation}\label{lb.5} \frac{1}{n}\sum_{v \in V} (d(v) - i + 2)\theta_i(v) = d - i + 2 \end{equation} and for $3 \leq i \leq t + 1$, \begin{equation}\label{lb1} \Bigl(\frac{k-t}{k}\Bigr)^t \leq \theta_i(v) \leq \Bigl(\frac{k}{k - t}\Bigr)^t \end{equation} %If $G$ has girth at least $\mbox{diam}(T)$ and $d \geq 2t$, then %\begin{equation}\label{lb2} %\mathsf{N}_T(G) \geq nd \prod_{v \in V} \prod_{i = 1}^{t-1} (d(v) - 1)_{i}^{\frac{d(v)}{nd}}. %\end{equation} \end{theorem} \medskip \begin{proof} Let $\Omega$ be the set of all labelled copies of $T$ in the graph $G$. Fix a breadth-first search ordering $\vec{x} = (x_1,x_2,\dots,x_{t + 1})$ of the vertices of $T$, starting with a leaf $x_1$ of $T$. For $2 \le i \le t + 1$, let $a(i)$ be the unique $h < i$ such that $x_h$ is the parent of $x_i$ in the ordering $\vec{x}$. Note that $a(2)=1$ and $a(3)=2$. Let $v_1 v_2$ be a randomly and uniformly chosen (oriented) edge of $G$ and define $\phi(x_1) = v_1$ and $\phi(x_2) = v_2$. Having defined $\phi(x_j) = v_j$ for all $j < i$, let $x_{i}$ be mapped to a uniformly chosen vertex of \[ \np{N}(v_{a(i)}) := N(v_{a(i)}) \backslash \{v_1,v_2,\dots,v_{i-1}\}.\] One can always define $\phi$ in this manner since $d(v_{a(i)}) \geq k \geq t + 1 \geq i$ and therefore \begin{eqnarray*} |\np{N}(v_{a(i)})| &\geq& |N(v_{a(i)})| - |\{v_1,v_2,\dots,v_{i-1}\} \backslash \{v_{a(i)}\}| \\ &\geq& d(v_{a(i)}) - i + 2 > 0. \end{eqnarray*} Here we noted that $v_{a(i)} \in \{v_1,v_2,\dots,v_{i-1}\}$. Then $\phi$ gives a probability measure $\mathsf P$ on the sample space $\Omega$. Let $\vec{v}$ denote a vector $(v_1,v_2,\dots,v_{t+1})$ of vertices of $G$. We write $\phi(\vec{x}) = \vec{v}$ to denote the event that $\phi(x_i) = v_i$ for all $i \in [t + 1]$. Then \begin{equation}\label{exact} \mathsf P(\phi(\vec{x}) = \vec{v}) = \frac{1}{nd} \prod_{i = 3}^{t + 1} \frac{1}{|\np{N}(v_{a(i)})|}. \end{equation} By the inequality of arithmetic and geometric means: \begin{eqnarray*} \mathsf{N}_T(G) &=& \sum_{\vec{v} \in \Omega} \mathsf P(\phi(\vec{x}) = \vec{v}) \cdot \frac{1}{\mathsf{P}(\phi(\vec{x}) = \vec{v})} \\ &\geq& \prod_{\vec{v} \in \Omega} \mathsf P(\phi(\vec{x}) = \vec{v})^{-\mathsf P(\phi(\vec{x}) = \vec{v})} \\ &=& \prod_{\vec{v} \in \Omega} (nd)^{\mathsf P(\phi(\vec{x}) = \vec{v})} \cdot \prod_{\vec{v} \in \Omega} \prod_{i = 3}^{t+1} |\np{N}(v_{a(i)})|^{\mathsf P(\phi(\vec{x}) = \vec{v})} \\ &=& nd \prod_{\vec{v} \in \Omega} \prod_{i = 3}^{t+1} |\np{N}(v_{a(i)})|^{\mathsf P(\phi(\vec{x}) = \vec{v})}. \end{eqnarray*} Let $\Omega_{iv} = \{\vec{v} \in \Omega : v_{a(i)} = v\}$. Since $|\np{N}(v_{a(i)})| \geq d(v_{a(i)}) - i + 2$ for $3 \leq i \leq t + 1$, \begin{eqnarray}\label{lastbound} \mathsf{N}_T(G) &\geq& nd \cdot \prod_{\vec{v} \in \Omega} \prod_{i = 3}^{t + 1} |\np{N}(v_{a(i)})|^{\mathsf{P}(\phi(\vec{x}) = \vec{v})} \nonumber \\ &=& nd \cdot \prod_{i = 3}^{t+1} \prod_{v \in V} \prod_{\vec{v} \in \Omega_{iv}} |\np{N}(v_{a(i)})|^{\mathsf{P}(\phi(\vec{x}) = \vec{v})} \nonumber \\ &\geq& nd \cdot \prod_{i = 3}^{t+1} \prod_{v \in V} \prod_{\vec{v} \in \Omega_{iv}} (d_G(v) - i + 2)^{\mathsf{P}(\phi(\vec{x}) = \vec{v})} \nonumber \\ &=& nd \cdot \prod_{i = 3}^{t+1} \prod_{v \in V} (d_G(v) - i + 2)^{\sum_{\vec{v} \in \Omega_{iv}} \mathsf{P}(\phi(\vec{x}) = \vec{v})} \nonumber \\ &=& nd \cdot \prod_{i = 3}^{t+1} \prod_{v \in V} (d_G(v) - i + 2)^{\mathsf{P}(\phi(x_{a(i)}) = v)}. \end{eqnarray} In the next two claims, we fix $v \in V$. For $i \in [t + 1]$, define \[ g_i(v) = \mathsf P(\phi(x_i) = v).\] We observe that $g_1(v) = g_2(v) = d_G(v)/dn$. For $3 \leq i \leq t + 1$, we determine upper and lower bounds on $g_i(v)$ relative to $d_G(v)/dn$. We write $d(v)$ instead of $d_G(v)$ in what follows. \medskip To bound the quantities $g_i(v)$, let $T_i$ be the subtree of $T$ consisting of the vertices $x_1,x_2,\dots,x_i$ in order. Now consider a breadth-first search ordering $y_1,y_2,\dots,y_i$ of $T_i$ such that $y_1 = x_i$ and $y_i = x_1$. For $2 \le j \le i$, let $b(j)$ be the unique $h < j$ such that $y_h$ is the parent of $y_j$ in the ordering $y_1,y_2,\dots,y_i$ and let \begin{eqnarray*} \np{N}(u_{b(j)}) &=& N_G(u_{b(j)}) \backslash \{u_1,u_2,\dots,u_{j-1}\}. \end{eqnarray*} As an example, if $T_i$ is a path, then $b(j) = j - 1$ and $\np{N}(u_j) = N_G(u_j) \backslash \{u_1,u_2,\dots,u_{j-1}\}$. \bigskip \bigskip {\bf Claim 1.} Let $3 \leq i \leq t + 1$ and let $v = u_{b(2)} = u_1$. Then \begin{equation}\label{gidentity} \frac{1}{nd}\!\sum_{\scriptscriptstyle{u_2 \in \np{N}(u_{b(2)})}}\!\!\!\! \cdots \!\! \sum_{\scriptscriptstyle{u_i \in \np{N}(u_{b(i)})}} \prod_{j = 3}^{i} \frac{1}{d(u_{b(j)})} \leq g_i(v) \leq \frac{1}{nd}\!\sum_{\scriptscriptstyle{u_2 \in \np{N}(u_{b(2)})}} \!\!\!\! \cdots \!\! \sum_{\scriptscriptstyle{u_i \in \np{N}(u_{b(i)})}} \prod_{j = 3}^{i} \frac{1}{d(u_{b(j)}) - t} \end{equation} {\bf Proof of Claim 1.} The number of choices of an embedding of $T_i$ with $x_i$ mapping to $v$ is \begin{equation}\label{gformula} \sum_{u_2 \in \np{N}(u_{b(2)})} \sum_{u_3 \in \np{N}(u_{b(3)})} \cdots \sum_{u_i \in \np{N}(u_{b(i)})}1. \end{equation} Here we are counting the images of $T_i$ according to the breadth-first search ordering $y_1,y_2,\dots,y_i$ of $T_i$ with $y_1 = x_i$ and $y_i = x_1$, so that the image of $y_j$ is $u_j$ for $j \in [i]$. At the stage where $y_j$ is to be embedded, we have to select a vertex $u_j \in N_G(u_{b(j)})$ such that $u_j$ is not equal to any of $v = u_1,u_2,\dots,u_{j - 1}$, which have already been embedded. By definition of $\np{N}(u_{b(j)})$, this is equivalent to $u_j \in \np{N}(u_{b(j)})$. \medskip Suppose we fix such an embedding with vertices $u_1,u_2,\dots,u_i$. Let $v_1,v_2,\dots,v_i$ be the re-ordering of $u_1,u_2,\dots,u_i$ such that $x_j$ is mapped to $v_j$ for $j \in [i]$. This fixed embedding has probability \begin{equation}\label{pformula} \mathsf P(\phi(\vec{x}) = \vec{v}) = \frac{1}{nd} \prod_{j = 3}^{i} \frac{1}{|\np{N}(v_{a(j)})|}. \end{equation} Since $d(v_{a(j)}) - t \leq |\np{N}(v_{a(j)})| \leq d(v_{a(j)})$, \begin{equation}\label{pformula2} \frac{1}{nd} \prod_{j = 3}^{i} \frac{1}{d(v_{a(j)})} \leq \mathsf P(\phi(\vec{x}) = \vec{v}) \leq \frac{1}{nd} \prod_{j = 3}^{i} \frac{1}{d(v_{a(j)}) - t }. \end{equation} We now prove $\{v_{a(j)} : 3 \leq j \leq i\}$ and $\{u_{b(j)} : 3 \leq j \leq i\}$ are equal as multisets. For example, if $T_i$ is a path, then these multisets are sets, and $\{v_{a(j)} : 3 \leq j \leq i\} = \{v_2,v_3,\dots,v_{i-1}\} = \{u_2,u_3,\dots,u_{i-1}\}$ since $u_j = v_{i-j+1}$ for $j \in [i]$. For $2 \le \ell \le i-1$, the number of times $u_{\ell}$ appears in the multiset $\{u_{b(j)} : 3 \leq j \leq i\}$ is the number of $j$ with $3 \le j \le i$ such that $b(j)=\ell$. In other words, it is the number of times $u_{\ell}$ is a parent of some vertex $u_j$ in the ordering $u_1, \ldots, u_i$. This is precisely $d_T(y_{\ell}) - 1$. Similarly, the number of times $u_{\ell} \in \{v_2,v_3,\dots,v_{i-1}\}$ appears in the multiset $\{v_{a(j)} : 3 \leq j \leq i\}$ is the number of times $u_{\ell}$ is a parent of some vertex $v_j$ in the ordering $v_1, \ldots, v_i$, and this is again $d_T(y_{\ell}) - 1$. We conclude $\{v_{a(j)} : 3 \leq j \leq i\}$ and $\{u_{b(j)} : 3 \leq j \leq i\}$ are equal as multisets. Therefore by (\ref{pformula2}), \[ \frac{1}{nd} \prod_{j = 3}^{i} \frac{1}{d(u_{b(j)})} \leq \mathsf P(\phi(\vec{x}) = \vec{v}) \leq \frac{1}{nd} \prod_{j = 3}^{i} \frac{1}{d(u_{b(j)}) - t}.\] Replacing the summand $1$ in (\ref{gformula}) with $\mathsf P(\phi(\vec{x}) = \vec{v})$, we obtain Claim 1. \hfill $\Box$ \bigskip \bigskip For each $v \in V$ and $3 \leq i \leq t + 1$, define $\theta_i(v)$ by \begin{equation}\label{deftheta} g_{a(i)}(v) = \frac{d(v) - i + 2}{(d - i + 2)n} \theta_i(v). \end{equation} Note that since $\sum_{v \in V} g_{\ell}(v) = \sum_{v \in V} \mathsf{P}(\phi(x_{\ell}) = v) = 1$ for all ${\ell} \leq t + 1$, we have \[ \frac{1}{n} \sum_{v \in V} (d(v) - i + 2)\theta_i(v) = d - i + 2\] and this verifies (\ref{lb.5}). The goal of the next claim is to verify (\ref{lb1}). \bigskip \bigskip {\bf Claim 2.} {\em For $3 \leq i \leq t + 1$,} \[ \Bigl(\frac{k-t}{k}\Bigr)^t \leq \theta_i(v) \leq \Bigl(\frac{k}{k - t}\Bigr)^t.\] {\bf Proof of Claim 2.} We only prove the upper bound, since the lower bound is similar. For convenience, for $3 \leq \ell \leq i$, and $v = u_1 = u_{b(2)}$, define \[ f(\ell) = \frac{1}{nd}\sum_{u_{2} \in \np{N}(u_{b(2)})} \sum_{u_{3} \in \np{N}(u_{b(3)})} \cdots \sum_{u_{\ell} \in \np{N}(u_{b(\ell)})} \prod_{j = 3}^{\ell} \frac{1}{d(u_{b(j)}) - t}.\] Then $g_i(v) \leq f(i)$ by Claim 1. Since $|\np{N}(u_{b(i)})| \leq d(u_{b(i)})$ and $d(u_{b(i)}) \geq k$, \[ \sum_{u_{i} \in \np{N}(u_{b(i)})} \frac{1}{d(u_{b(i)}) - t} = \frac{|\np{N}(u_{b(i)})|}{d(u_{b(i)}) - t}\le \frac{d(u_{b(i)})}{d(u_{b(i)}) - t} \leq \frac{k}{k - t}.\] This shows $f(i) \leq \frac{k}{k - t}f(i - 1)$. Continuing in this way we obtain \begin{eqnarray*} g_i(v) \leq f(i) &\leq& \Bigl(\frac{k}{k - t}\Bigr)^{i - 2} f(2) \\ &=& \frac{1}{nd} \Bigl(\frac{k}{k - t}\Bigr)^{i - 2} \sum_{u_2 \in N(v)} 1 \\ &=& \frac{d(v)}{nd} \Bigl(\frac{k}{k - t}\Bigr)^{i - 2} \\ &\leq& \frac{d(v)}{nd} \Bigl(\frac{k}{k - t}\Bigr)^{t - 2}. \end{eqnarray*} For any $j$ such that $3 \leq j \leq i \le t + 1$, $d(v)/(d(v) - j + 2) \leq k/(k - j + 2) \leq k/(k - t)$ since $d(v) \geq k \geq t + 1 \geq j$. Therefore \[ \frac{d(v)}{nd} \leq \frac{d(v) - j + 2}{(d- j + 2)n} \cdot \frac{d(v)}{d(v) - j + 2} \leq \frac{d(v) - j + 2}{(d - j + 2)n} \cdot \frac{k}{k-t}.\] Inserting this in the preceding upper bound for $g_i(v)$, we find for any $j$ with $3 \leq j \le i \leq t + 1$, \[ g_i(v) \leq \frac{d(v) - j + 2}{(d - j + 2)n} \cdot \frac{k}{k - t} \cdot \Bigl(\frac{k}{k - t}\Bigr)^{t-2} \leq \frac{d(v) - j + 2}{(d - j + 2)n} \cdot \Bigl(\frac{k}{k - t}\Bigr)^t.\] This also holds for $i=2$ as \[ g_2(v) =\frac{d(v)}{dn} \leq \frac{d(v) - j + 2}{(d - j + 2)n} \cdot \frac{d(v)}{d(v)-j+2} \leq \frac{d(v) - j + 2}{(d - j + 2)n} \Bigl(\frac{k}{k - t}\Bigr).\] Replacing $i$ with $a(i)\ge 2$ and selecting $j = i$, \[ g_{a(i)}(v) \leq \frac{d(v) - i + 2}{(d - i + 2)n} \Bigl(\frac{k}{k - t}\Bigr)^t.\] By the definition (\ref{deftheta}), this gives $\theta_i(v) \leq (k/(k - t))^t$. The lower bound is similar: we use the lower bound on $g_i(v)$ from Claim 1, together with the observation $|\np{N}(u_{b(i)})| \geq d(u_{b(i)}) - t$ and $d(u_{b(i)}) \geq k$ to obtain \[g_i(v) \geq \frac{d(v)}{nd} \Bigl(\frac{k - t}{k}\Bigr)^{t - 2}.\] Then we use \[ \frac{d(v)}{dn} \geq \frac{d(v) - j + 2}{(d - j + 2)n} \cdot \frac{d-j+2}{d} \geq \frac{d(v) - j + 2}{(d - j + 2)n} \cdot \frac{k-t}{k}\] for $3 \leq j \leq t + 1$, and as above this gives the required lower bound on $\theta_i(v)$. \hfill $\Box$ \bigskip Now we finish the proof of Theorem \ref{loc}: (\ref{lastbound}) becomes \[ \mathsf{N}_T(G) \geq nd \prod_{v \in V} \prod_{i = 3}^{t+1} (d(v)- i + 2)^{g_{a(i)}(v)} = nd \prod_{v \in V} \prod_{i = 3}^{t + 1} (d(v)- i + 2)^{\frac{d(v) - i + 2}{(d - i + 2)n}\theta_i(v)}\] where $\theta_i(v)$ satisfies (\ref{lb.5}) and (\ref{lb1}), by Claims 1 and 2. This proves (\ref{lb}). \end{proof} %\medskip % %For (\ref{lb2}), in the context of Claim 1 we now have %$|\np{N}(v_j)| = |Nv_j)|$ for $j \leq i + 1$. Therefore (\ref{gidentity}) becomes: %\[ g_i(v) = \frac{1}{nd} \sum_{v_{i} \in N^(v)} \cdots \sum_{v_{1} \in Nv_2)} \prod_{j = 2}^{i} \frac{1}{|\np{N}(v_j)|} = \frac{1}{nd} %\sum_{v_{i} \in N(v)} 1 = \frac{d(v_{i+1})}{nd} = \frac{d(v)}{nd}.\] %Therefore $\mathsf{N}_T(G) \geq nd \prod_{v \in V} (d(v) - 1)_{d_i}^{d(v)/nd}$ and the proof of (\ref{lb2}) is complete. \section{An Approximate Jensen's Inequality} An approximate form of Jensen's Inequality is used to prove Theorem \ref{main} from Theorem \ref{loc}: \begin{lemma}\label{jensen} Let $\delta,x_i,y_i \in [0,\infty)$ for all $i \in [n]$, and suppose $\frac{1}{n}\sum_{i=1}^n x_i = \frac{1}{n}\sum_{i=1}^n y_i = \gamma$ and $|x_i/y_i - 1| \leq \delta$ for all $i \in [n]$. Then \[ \prod_{i=1}^n x_i^{\frac{y_i}{\gamma n}} \geq (1 - \delta)e^{\delta} \gamma.\] \end{lemma} \begin{proof} The lemma is clear if $\delta \geq 1$ so we assume $\delta \in [0,1)$. This implies $x_i,y_i \in (0,\infty)$. Let $f(y) = y\log y$ and $\frac{x_i}{y_i} = c_i$. Since $f$ is convex on $(0,\infty)$, Jensen's Inequality gives: \[ \frac{1}{n} \sum_{i=1}^n f(y_i) \geq f\Bigl(\frac{1}{n}\sum_{i=1}^n y_i\Bigr) = \gamma \log \gamma. \] Furthermore, $y_i\log x_i = f(y_i) + y_i \log c_i$. Therefore \begin{eqnarray*} \log \prod_{i = 1}^n x_i^{\frac{y_i}{\gamma n}} &=& \frac{1}{\gamma n} \sum_{i = 1}^n y_i\log x_i \\ &=& \frac{1}{\gamma} \cdot \frac{1}{n}\sum_{i = 1}^n (f(y_i) + y_i \log c_i) \\ &=& \frac{1}{\gamma} \Bigl(\frac{1}{n}\sum_{i = 1}^n f(y_i)\Bigr) + \frac{1}{\gamma n} \sum_{i = 1}^n y_i \log c_i \\ &\geq& \log \gamma + \frac{1}{\gamma n} \sum_{i = 1}^n y_i \log c_i \\ &=& \log \gamma + \frac{1}{\gamma n} \sum_{i = 1}^n y_i (c_i - 1) + \frac{1}{\gamma n} \sum_{i = 1}^n y_i (\log c_i - c_i + 1). \end{eqnarray*} Since $\sum c_i y_i = \sum x_i = \gamma n$, $\sum y_i(c_i - 1) = 0$. The function $h(x) = \log x - x$ on the interval $[1-\delta,1+\delta]$ has one critical point, a maximum at $x=1$, and therefore its minimum in this interval occurs at one of its endpoints. We claim that $h(1-\delta)2$, this proves that $h(1-\delta) \frac{1}{2}n$, then as $\delta \rightarrow 0$, \[ \prod_{i=1}^n x_i^{\frac{y_i}{\gamma n}} = (1 - \delta^2)^{\frac{1}{2}}\gamma = 1 - \frac{1}{2}\delta^2 + O(\delta^3).\] This shows the bound in Lemma \ref{jensen} is asymptotically tight as $\delta \rightarrow 0$. Note that if $\delta = 0$, then $\prod_{i = 1}^n x_i^{y_i/\gamma n} \geq \gamma$ directly from Jensen's Inequality. \section{Proof of Theorem \ref{main}} We prove Theorem \ref{main} by induction on $n$. Let $G$ be an $n$-vertex graph with average degree $d \geq t$. Theorem \ref{main} states $\mathsf{N}_T(G) \geq (1 - \varepsilon_d) n(d)_t$. If $t \leq d < 16t^2$, then $1 - \varepsilon_d \leq 0$ and so Theorem \ref{main} is true in this case. This also proves the theorem when $n<16t^2$. Suppose $d \geq 16t^2$. If $k$ is the minimum degree of $G$, we consider the two cases $k < d/8$ and $k \geq d/8$ separately. \medskip {\bf Case 1.} {\em $k < d/8$.} In this case, remove from $G$ a vertex of degree $k$ to get a graph $H$ with $n - 1$ vertices and average degree at least \[ \frac{2}{n - 1}\Bigl(\frac{dn}{2} - \frac{d}{8}\Bigr) > d + \frac{d}{n - 1} - \frac{d}{4(n - 1)} > d + \frac{3d}{4n} := d'.\] By definition of $d'$, \begin{eqnarray*} (n - 1)d'(d' - 1) &=& (n - 1)(d + \tfrac{3d}{4n})(d - 1 + \tfrac{3d}{4n}) \\ &=& nd(d - 1) + \tfrac{1}{4}d + \tfrac{1}{2}d^2 - \tfrac{9 d^2}{16n^2} + \tfrac{3 d}{4n} - \tfrac{15 d^2}{16n} \\ &>& nd(d - 1) + \tfrac{1}{2}d^2 - \tfrac{1}{n}d^2 \\ &>& nd(d - 1). \end{eqnarray*} From the second to the third line, we used $3d/4n > 9d^2/16n^2$ since $d < n$, and $15d^2/16n < d^2/n$. Recall $\varepsilon_d = (4t)^5/d^2$. Note also $d' > d \geq t$, so by induction, and since $1 - \varepsilon_{d'} \geq 1 - \varepsilon_d$ for $d' \geq d$, \begin{eqnarray*} \mathsf{N}_T(H) &\geq& (1 - \varepsilon_{d'}) \cdot (n - 1)(d')_t \\ &\geq& (1 - \varepsilon_{d}) \cdot (n - 1)d'(d' - 1) \cdot (d - 2)_{t - 2} \\ &>& (1 - \varepsilon_{d}) \cdot nd(d - 1) \cdot (d - 2)_{t - 2} \\ &=& (1 - \varepsilon_d) \cdot n(d)_t. \end{eqnarray*} The proof is complete in this case. \medskip {\bf Case 2.} {\em $k \geq d/8$.} We apply Lemma \ref{jensen} and Theorem \ref{loc}. By Theorem \ref{loc}, shifting the range of summation from $3 \leq i \leq t + 1$ to $j \in [t-1]$, \begin{equation}\label{locbound} \mathsf{N}_T(G) \geq nd \prod_{v \in V} \prod_{j = 1}^{t-1} (d(v) - j)^{\frac{d(v)-j}{(d-j)n}\theta_{j+2}(v)}. \end{equation} By (\ref{lb1}), for all $j \in [t-1]$, \[ \Bigl(\frac{k - t}{k}\Bigr)^t \leq \frac{1}{\theta_{j+2}(v)} \leq \Bigl(\frac{k}{k - t}\Bigr)^t.\] Since $(1 - x)^t \geq 1 - x t$ for $0 \leq x \leq 1$ and $(1 + x)^t \leq 1 + 2xt$ for $0 \leq x \leq 1/t$, \[ 1 - \frac{t^2}{k} \leq \frac{1}{\theta_{j+2}(v)} \leq 1 + \frac{2t^2}{k - t}.\] Since $2t^2/(k - t) \leq 4t^2/k$ is easily true for $k \geq d/8 \geq 2t^2$, letting $\delta = 4t^2/k$ we obtain \[ \Bigl|\frac{1}{\theta_{j + 2}(v)} - 1\Bigr| \leq \delta\] for all $j \in [t - 1]$. Now we use Lemma \ref{jensen}. Fixing $j \in [t-1]$, let $x_{v,j} = d(v) - j$ and let $y_{v,j} = (d(v) - j)\theta_{j+2}(v)$ for $v \in V$. Then \[ \Bigl|\frac{x_{v,j}}{y_{v,j}} - 1\Bigr| = \Bigl|\frac{1}{\theta_{j+2}(v)} - 1\Bigr| \leq \delta.\] Furthermore, from (\ref{lb.5}) in Theorem \ref{loc}, \[ \frac{1}{n} \sum_{v \in V} y_{v,j} = \frac{1}{n}\sum_{v \in V} (d(v) - j)\theta_{j+2}(v) = d - j = \frac{1}{n}\sum_{v \in V} (d(v) - j) = \frac{1}{n}\sum_{v \in V} x_{v,j}.\] Also $x_{v,j} \geq d(v) - j \geq k - t \geq 0$ and $y_{v,j} = \theta_{j+2}(v)x_{v,j} \geq 0$. Therefore all the conditions of Lemma \ref{jensen} are satisfied, and so for each $j \in [t - 1]$, Lemma \ref{jensen} with $\gamma = d - j$ gives \[ \prod_{v \in V} x_{v,j}^{\frac{y_{v,j}}{(d - j)n}} \geq (1 - \delta)e^{\delta}(d - j).\] Applying this for each $j \in [t - 1]$ to (\ref{locbound}) gives \[ \mathsf{N}_T(G) \geq nd \prod_{j = 1}^{t - 1} (1 - \delta) e^{\delta}(d - j) = n(d)_t \cdot (1 - \delta)^{t-1} e^{(t-1)\delta}.\] Finally, using $(1 - \delta)e^{\delta} \geq 1 - \delta^2$ and $(1 - \delta^2)^{t - 1} \geq 1 - t\delta^2$, \begin{eqnarray*} (1 - \delta)^{t-1} e^{(t-1)\delta} &\geq& (1 - \delta^2)^{(t-1)} \\ &\geq& 1 - t\delta^2 \\ &=& 1 - \frac{16t^5}{k^2} \\ &\geq& 1 - \varepsilon_d. \end{eqnarray*} From the third line to the fourth, we used $k \geq d/8$. This completes the proof. \hfill $\Box$ \section{Concluding remarks} $\bullet$ Theorem \ref{main} can be improved if structural information on $G$ is given. For instance, if $G$ is an $n$-vertex triangle-free graph of average degree $d$, and $T$ is the $t$-edge path, then one can adapt the proof of Theorem \ref{main} to obtain \[ \mathsf{N}_T(G) \geq (1 - O(\tfrac{t^5}{d^2})) nd \prod_{i = 1}^{t - 1} (d - \lceil \tfrac{i}{2}\rceil).\] A disjoint union of complete bipartite graphs $K_{d,d}$ shows this is tight up to the factor $1 - O(\tfrac{t^5}{d^2})$. It is plausible as in Conjecture 1 that this construction has the fewest copies of $T$ amongst all triangle-free graphs of average degree $d$, when $d$ is large enough. \medskip $\bullet$ Fix a tree $T$ with $t$ edges and degrees $1,d_1,d_2,\dots,d_t$ in a breadth-first labelling starting with a leaf. A {\em local isomorphism} of $T$ in a graph $G$ is a neighbourhood preserving embedding of $T$ in $G$ i.e. a map $\phi : V(T) \rightarrow V(G)$ such that if $\phi(x) = v$ for some $x \in V(T)$, then $\phi(y) \neq \phi(z)$ whenever $y, z \in N_T(x)$ are distinct. Using the method of Theorem \ref{loc}, one can show that the number of local isomorphisms of $T$ in $G$ is at least \[ nd \prod_{v \in V} \prod_{i = 1}^{t-1} (d(v) - 1)_{d_i-1}^{\frac{d(v)}{dn}}.\] If $G$ has minimum degree say at least $2t$, and average degree $d$, it is possible to show that the above expression is at least \[ nd\prod_{i = 1}^{t-1}(d - 1)_{d_i-1}.\] If $T$ is a path, then we recover the main result of~\cite{AHL} stating that the number of non-backtracking walks of $t$ edges in $G$ is at least $nd(d - 1)^{t - 1}$. Furthermore, the bound is tight since equality is achieved for any $d$-regular $n$-vertex graph. Finally, if $G$ has girth at least $\mbox{diam}(T)$, then every local isomorphism of $T$ in $G$ is an isomorphism, so we obtain the lower bound \[ \mathsf{N}_T(G) \geq nd \prod_{i = 1}^{t - 1} (d - 1)_{d_i-1}.\] Again, this is tight for any $d$-regular graph of sufficiently large girth. \bigskip \subsection*{Acknowledgments} We thank Eoin Long for pointing out an error in an earlier version of this paper, and the anonymous referees for helpful comments. \begin{thebibliography}{99} \bibitem{AHL} N. Alon, S. Hoory, and N. Linial, The Moore Bound for Irregular Graphs, Graphs Combin. 18 (2002), no. 1, 53--57. \bibitem{BR} G. Blakley and P. Roy, H\" older type inequality for symmetrical matrices with non-negative entries, Proc. Amer. Math. Soc. (1965) 16, 1244--1245. \bibitem{Detal} D. Dellamonica Jr., P. Haxell, T. {\L}uczak, D. Mubayi, B. Nagle, Y. Person, V. R\"odl, M. Schacht, Tree-minimal graphs are almost regular, J. Comb. 3 (2012), no. 1, 49--62. \bibitem{ES} P. Erd\H os and M. Simonovits, Compactness results in extremal graph theory, Combinatorica 2 (1982) no. 3, 275--288. \bibitem{sidorenko} A. F. Sidorenko, Inequalities for functionals generated by bipartite graphs, Diskretnaya Matematika 3 (1991), 50-65 (in Russian), Discrete Math. Appl. 2 (1992), 489-504 (in English). \bibitem{TW} H. T\"{a}ubig. J. Weihmann, Matrix power inequalities and the number of walks in graphs, Discrete Appl. Math. 176, 122--129. \end{thebibliography} \end{document} \begin{lemma}\label{Lambda} There exists a constant $\alpha \approx 1.398$ and a function $f(t) = \alpha t + o(k)$, defined for $t \leq 8$ by the following table: \begin{center} \begin{tabular}{|l|l|l|l|l|l|l|l|l|} \hline $t$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ \\ \hline $f(t)$ & $2$ & $4$ & $5$ & $7$ & $8$ & $10$ & $11$ & $12$\\ \hline \end{tabular} \end{center} such that for any graph $G$ with average degree $d$ and minimum degree at least $f(t)$, \begin{equation}\label{lambdabound} \prod_{v \in V} \prod_{i = 2}^{t - 1} (d(v) - i + 1)^{\frac{d(v)}{2e(G)}} \geq (d-1)_{t - 1}. \end{equation} \end{lemma} \begin{proof} We establish (\ref{lambdabound}) using Jensen's Inequality applied to the function $g(x) = x\log (x - 1)_t$ on $[t+1, \infty)$. First we compute the second derivative of $g$ to determine where $g$ is convex: \begin{eqnarray*} \frac{d^2 g}{d x^2} &=& \frac{d^2}{d x^2} \left(x \sum_{i=1}^{t} \log (x - i)\right) \\ &=& \frac{d}{dx} \left(\sum_{i=1}^{t} \left(\log (x - i) + \frac{x}{x-i}\right)\right) \\ &=& \sum_{i=1}^{t} \frac{x - 2i}{(x - i)^2}\\ &=& \frac{1}{t}\sum_{i=1}^{t} \frac{\xi - \frac{2i}{t}}{(\xi - \frac{i}{t})^2} \end{eqnarray*} where we put $x = \xi t$ for $\xi > 1$. Now the last sum is a Riemann sum for the function $h_\xi (t) = \frac{\xi - 2t}{(\xi - t)^2} $ on $[0,1]$, so \begin{eqnarray*} \lim_{t \rightarrow \infty} \frac{1}{t}\sum_{i=0}^{t-1} \frac{\xi - \frac{2i}{t}}{(\xi - \frac{i}{t})^2} &=& \int_{0}^{1} \frac{\xi - 2s}{(\xi - s)^2} ds \\ &=& 2\ln\Bigl(\frac{\xi}{\xi-1}\Bigr) - \frac{1}{\xi-1}. \end{eqnarray*} The last expression is positive when $\xi > \alpha$, where $\alpha \approx 1.398$ is a solution of $$2\ln\Bigl(\frac{\xi}{\xi-1}\Bigr) - \frac{1}{\xi-1}=0.$$ So there exists a function $f(t) = \alpha t + o(t)$ such that if $x \geq f(t)$, then $g ''(x) > 0$. Now Jensen's Inequality applied to $g$ on $[f(t), \infty)$ gives \[ \frac{1}{|V|}\sum_{v \in V} g(d(v)) \geq g(d).\] For small values of $t$, a simple inspection reveals the values in the table. \end{proof}