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
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)}.
