Combinatorics Seminar
When: Sunday, November 20, 10am
Where: Schreiber 309
Speaker: Raphael Yuster, University of Haifa
Title: Packing small cycles in regular tournaments
Abstract:
A tournament is an orientation of the complete graph. A tournament
is regular if the in-degree is equal to the out-degree at each
vertex.
There are exponentially many non-isomorphic regular tournaments
with n vertices, but they do all share some properties other than
just being regular. For example, they all have the same number
of triangles (directed cycles of length 3).
In this talk we survey some conjectures and sketch proofs of some
results on the number of {\em disjoint} triangles and other small
cycles in regular tournaments.
Here are a few sample conjectures and results in this area:
1. Conjecture: Every regular tournament has \lfloor n/3 \rfloor
pairwise vertex-disjoint triangles. In particular, if n = 3 mod 6,
then an n-vertex regular tournament has a triangle factor.
Recently, Keevash and Sudakov came close to proving this
conjecture. Their packing only misses at most three vertices.
2. Conjecture: Every regular tournament has at least (1-o(1))n^2/8
pairwise edge-disjoint triangles.
We will show that there are regular tournaments that have less
than n^2/8 pairwise edge-disjoint triangles, and, on the other
hand,
we will prove that there are always at least (1-o(1))n^2/11.5
pairwise edge-disjoint triangles.
3. Conjecture: Every regular tournament has at least
(1-o(1)){n \choose 2}/4k pairwise edge-disjoint cycles of length 4k.
In other words, essentially 100% of the edges can be packed into
cycles of length 4k.
Presently, the best known lower bound is
still very far from 100% even for the case k=1.