Tree-minimal graphs are almost regular (Q353399): Difference between revisions

\(N_F(G)\) denotes the number of labelled copies of a subgraph \(F\) in a graph \(G\); \(d_v\) denotes the degree of vertex \(v\). Addressing a problem of [\textit{J. Skokan} and \textit{L. Thoma}, Graphs Comb. 20, No. 2, 255--262 (2004; Zbl 1054.05091)], the authors prove Theorem 1. For all \(\varepsilon\in(0,1]\) and all integers \(t\geq3\), there exists \(\delta>0\) so that, whenever \(p \gg n^{-\frac1{t-2}}\), the following statement holds: Let \(T\) be a tree with \(t\) vertices, and let \(G=(V,E)\) be a graph with \(n\) vertices and \(|E|=p{n\choose2}\) edges. If \(N_T(G)\leq(1+\delta)p^{t-1}n^t\), then \(\sum_{v\in V}\left|d_v-d\right|<\varepsilon pn^2\). For a tree \(T\), \(\hat N_T(G)\) denotes the number of edge-preserving maps \(h : V(T) \to V(G)\). Theorem 1 is a consequence of the following theorem, ``which extends a result of [\textit{N. Alon, S. Hoory} and \textit{N. Linial}, Graphs Comb. 18, No. 1, 53--57 (2002; Zbl 0990.05075)] from paths to arbitrary trees'': Theorem 3. Let \(T\) be a tree with \(t\geq3\) vertices, and let \(G = (V,E)\) be a graph with \(n\) vertices and average degree \(d\). Then \(\hat N_T(G) \geq nd\prod_{v\in V} d_v^{\frac{(t-2)d_v}{nd}}\). It is also shown that the proof of Theorem 3 can be altered to prove Theorem 5. Let \(P_3\) denote the path with 3 edges, and let \(G\) be a graph with \(n\) vertices, average degree \(d\), and minimum degree at least 3. Then \(N_{P_3}(G)\geq nd\prod_{v\in V}\left(d_v-2\right)^{\frac{2d_v}{nd}}\). The authors thank Jacques Verstraëte for pointing out the relation of their work to [\textit{P. Erdős} and \textit{M. Simonovits}, Combinatorica 2, 275--288 (1982; Zbl 0508.05043)].