A sharp lower bound for the number of mappings of a linear graph into an arbitrary graph and an inequality of A. F. Sidorenko

Improved lower bounds (compared with the known bounds of A. F. Sidorenko) are obtained for the number of mappings of a tree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula> into a graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ</mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> under the assumption that the degrees of the vertices of the tree take two values. These bounds are sharp also in a more general setting, when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ</mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be a weighted graph. The bounds also appear to be true for all trees <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D"> <mml:semantics> <mml:mi>D</mml:mi> <mml:annotation encoding="application/x-tex">D</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with a specified number of edges.