Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, March 14, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Asaf Ferber (Tel Aviv University)

Counting and packing Hamilton cycles in dense graphs and oriented graphs

In this talk we would like to present a general method for counting and packing Hamilton cycles in dense graphs and oriented graphs, based on permanent estimates. We then show how to utilize this approach to prove several extremal results. As a warm up we prove that every Dirac graph G contains at least (reg(G)/e)ⁿ many distinct Hamilton cycles, where reg(G) is the maximal degree of a spanning regular subgraph of G. We then show that every nearly cn-regular oriented graph on n vertices with c>3/8 contains (cn/e)ⁿ (1+o(1))ⁿ 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 show that every graph G on n vertices with minimum degree at least (1/2+ɛ)n contains at least (1-ɛ)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 Kühn, Lapinskas and Osthus.
Joint work with Michael Krivelevich (my supervisor) and Benny Sudakov.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login