Tue, 06 May 2025

14:00 - 15:00
L4

Optimally packing Hamilton cycles in random directed digraphs

Adva Mond
(King's College London)
Abstract

At most how many edge-disjoint Hamilton cycles does a given directed graph contain? It is easy to see that one cannot pack more than the minimum in-degree or the minimum out-degree of the digraph. We show that in the random directed graph $D(n,p)$ one can pack precisely this many edge-disjoint Hamilton cycles, with high probability, given that $p$ is at least the Hamiltonicity threshold, up to a polylog factor.

Based on a joint work with Asaf Ferber.

Tue, 29 Apr 2025

14:00 - 15:00
L4

Surprising orderings

Jaroslav Nešetřil
(Charles University)
Abstract

Graphs (and structures) which have a linear ordering of their vertices with given local properties have a rich spectrum of complexities. Some have full power of class NP (and thus no dichotomy) but for biconnected patterns we get dichotomy. This also displays the importance of Sparse Incomparability Lemma. This is a joint work with Gabor Kun (Budapest).

Wellbeing resources

Student studying in a libraryAs exam season approaches, we want to remind you of the wellbeing resources available for students.

Here are a few resources which may help:

Oxford Nightline

Oxford NightlineNightline is an independent listening, support, and information service run for students, by students.  We aim to provide every student in Oxford with the opportunity to talk to someone in confiden

Oxford AI Society

The Oxford AI Gala invites up to 350 AI professionals, founders, and researchers to gather on 31 May 2025 at the Oxford University Museum of Natural History. This event is a unique opportunity to connect with Oxford's world-class AI ecosystem, global industry leaders, and University of Oxford researchers and students, fostering collaboration an

NIHR funded summer internship opportunity, Imperial Clinical Trials Unit Statistician

The Imperial Clinical Trials Unit have an exciting opportunity to undertake an NIHR funded internship at Imperial Clinical Trials Unit, London. 

The statistics internship is suitable for those coming to the end of their second or third year, who have an interest in a career in healthcare research. 

The internship is paid (£20.82 per hour, inclusive of holiday pay), and will run for 8 weeks. Additional funding of up to £1000 is available for accommodation and travel expenses.

Subscribe to