# Combinatorics Seminar

When: Sunday, February 28, 10am

Where: Schreiber 309

Speaker: Raphy Yuster, University of Haifa

Title:
On the maximum number of spanning copies of an orientation in a
tournament

## Abstract:

For an orientation H with n vertices, let T(H) denote the maximum
number of
labeled copies of H in an n-vertex tournament.
It is easily seen that T(H) >= n!/2^{e(H)} as the latter is the
expected
number of such copies in a random tournament.
For n odd, let R(H) denote the maximum number of labeled copies of
H in an
n-vertex regular tournament.
Adler, Alon, and Ross proved that, in fact, for H=C_n the directed
Hamilton
cycle, T(C_n) >= (e-o(1))n!/2^{n} and it was observed by Alon that
already
R(C_n) >= (e-o(1))n!/2^{n}. Similar results hold for the directed
Hamilton
path P_n.
In other words, for the Hamilton path and cycle, the lower bound
derived
from the expectation argument can be improved by a constant factor.

In this talk we significantly extend these results and prove that
they hold
for a larger family of orientations H which includes all bounded
degree
Eulerian orientations
and all bounded degree balanced orientations, as well as many
others. One
corollary of our method is that for any k-regular orientation H
with n
vertices,
T(H) >= (e^k-o(1))n!/2^{e(H)} and in fact, for n odd, R(H) \ge
(e^k-o(1))n!/2^{e(H)}.

redesigned by barak soreq