Journal of Combinatorics

Volume 3 (2012)

Number 1

Tree-minimal graphs are almost regular

Pages: 49 – 62

DOI: https://dx.doi.org/10.4310/JOC.2012.v3.n1.a2

Authors

D. Dellamonica (Department of Mathematics and Computer Science, Emory University, Atlanta, Ga., U.SA.)

P. Haxell (Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada)

T. Luczak (Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland)

D. Mubayi (Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, Il., U.S.A.)

B. Nagle (Department of Mathematics and Statistics, University of South Florida, Tampa, Fl., U.S.A.)

Y. Person (Institut für Mathematik, Freie Universität Berlin, Germany)

V. Rödl (Department of Mathematics and Computer Science, Emory University, Atlanta, Ga., U.SA.)

Mathias Schacht (Fachbereich Mathematik, Universität Hamburg, Germany)

Abstract

For all fixed trees $T$ and any graph $G$we derive a counting formula for the number $\hat N_T(G)$ ofhomomorphisms from $T$ to $G$ in terms of the degree sequence of~$G$.

As a consequence we obtain that %for any fixed tree $T$ with $t\geq3$%verticesany $n$-vertex graph $G$ with edge density$p=p(n)\gg n^{-1/(t-2)}$, which contains at most $(1 +o(1))p^{t-1} n^t$ copiesof some fixed tree $T$ with $t\geq3$ verticesmust be almost regular, i.e.,$\sum_{v \in V(G)} |\deg(v) - pn| = o(pn^2)$.

Full Text (PDF format)

Published 11 September 2012