TAU Combinatorics Seminar 2020/21

When: Sunday, December 6, 10am
Speaker: Anita Liebenau, University of New South Wales Sydney
Title: Two approximate versions of Jackson's conjecture

Abstract:

A diregular bipartite tournament is a balanced complete bipartite graph whose edges are oriented so that every vertex has the same in- and outdegree. In 1981, Jackson showed that a diregular bipartite tournament contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: for every $\varepsilon>0$ there exists $n_0$ such that every diregular bipartite tournament on $2n\ge n_0$ vertices contains a collection of $(1/2-\varepsilon)n$ cycles of length at least $(2-\varepsilon)n.$ Increasing the degree by a small proportion allows us to prove the existence of many Hamilton cycles: for every $c>1/2$ and $\varepsilon>0$ there exists $n_0$ such that every $cn$-regular bipartite digraph on $2n \ge n_0$ vertices contains $(1-\varepsilon)cn$ edge-disjoint Hamilton cycles.

Joint work with Yani Pehova.