University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Spanning cycles in random directed graphs.

Spanning cycles in random directed graphs.

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Johannes Carmesin.

A beautiful coupling argument of McDiarmid shows that, given any orientated n-vertex cycle C, a copy of C almost surely appears in D(n,p) if p=(log n+log log n+omega(1))/n. This is not always optimal—as Frieze had shown, for a directed Hamilton cycle p=(log n+omega(1))/n is sufficient.

This talk will address the following questions, by combining McDiarmid’s coupling with constructive techniques:

- Is p=(log n+omega(1))/n sufficient for the appearance of any oriented n-vertex cycle?

- When is it likely that a copy of all such cycles can be found simultaneously?

This talk is part of the Combinatorics and Probability Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.