Algorithms, Combinatorics and Optimization Seminar

For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University.

Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...)

---

Michael Krivelevich
Tel Aviv University
Title: Counting and packing Hamilton cycles in dense graphs and oriented graphs

Abstract: We present a general method for counting and packing Hamilton cycles in dense graphs and oriented graphs, based on permanent estimates. We utilize this approach to prove several new extremal results, and also to derive new and conceptually simple(r) proofs of some known results in this area.

In particular, we show that every nearly cn-regular oriented graph on n vertices with c > 3/8 contains (cn/e)^n * (1+o(1))^n directed Hamilton cycles. This is an extension of a result of Cuckler, who settled an old conjecture of Thomassen about the number of Hamilton cycles in regular tournaments.

We also prove that every graph G on n vertices of minimum degree at least (1/2+\epsilon)n contains at least (1-\epsilon)reg_{even}(G)/2 edge-disjoint Hamilton cycles, where reg_{even}(G) is the maximum even degree of a spanning regular subgraph of G. This establishes an approximate version of a conjecture of Kuhn, Lapinskas and Osthus.

A joint work with Asaf Ferber (Tel Aviv U.) and Benny Sudakov (UCLA).

Date: Thursday, January 31, 2013
Time: 3:30 pm
Location: Wean 8220
Submitted by:  Loh