Search

We study Hamiltonicity in random subgraphs of the hypercube $\mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $\mathcal{Q}^n$ according to a uniformly chosen random ordering. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$, it contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\in\mathbb{N}$. Secondly, we obtain a perturbation result: if $H\subseteq\mathcal{Q}^n$ satisfies $\delta(H)\geq\alpha n$ with $\alpha>0$ fixed and we consider a random binomial subgraph $\mathcal{Q}^n_p$ of $\mathcal{Q}^n$ with $p\in(0,1]$ fixed, then with high probability $H\cup\mathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $k\in\mathbb{N}$. In particular, both results resolve a long standing conjecture, posed e.g. by Bollob\'as, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. Our techniques also show that, with high probability, for all fixed $p\in(0,1]$ the graph $\mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the R\"odl nibble, and absorption., Comment: Final version, to appear in Memoirs of the AMS

We show that there is a constant c>0 so that for any fixed r which is at least 3 a.a.s. an r-regular graph on n vertices contains a complete graph on c n^{1/2} vertices as a minor. This confirms a conjecture of Markstrom. Since any minor of an r-regular graph on n vertices has at most rn/2 edges, our bound is clearly best possible up to the value of the constant c. As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph G(n,p) during the phase transition (i.e. when pn is close to 1)., 18 pages

eLife 12, e81916 (2023). doi:10.7554/eLife.81916, Background:Short-term forecasts of infectious disease burden can contribute to situational awareness and aid capacity planning. Based on best practice in other fields and recent insights in infectious disease epidemiology, one can maximise the predictive performance of such forecasts if multiple models are combined into an ensemble. Here, we report on the performance of ensembles in predicting COVID-19 cases and deaths across Europe between 08 March 2021 and 07 March 2022.Methods:We used open-source tools to develop a public European COVID-19 Forecast Hub. We invited groups globally to contribute weekly forecasts for COVID-19 cases and deaths reported by a standardised source for 32 countries over the next 1–4 weeks. Teams submitted forecasts from March 2021 using standardised quantiles of the predictive distribution. Each week we created an ensemble forecast, where each predictive quantile was calculated as the equally-weighted average (initially the mean and then from 26th July the median) of all individual models’ predictive quantiles. We measured the performance of each model using the relative Weighted Interval Score (WIS), comparing models’ forecast accuracy relative to all other models. We retrospectively explored alternative methods for ensemble forecasts, including weighted averages based on models’ past predictive performance.Results:Over 52 weeks, we collected forecasts from 48 unique models. We evaluated 29 models’ forecast scores in comparison to the ensemble model. We found a weekly ensemble had a consistently strong performance across countries over time. Across all horizons and locations, the ensemble performed better on relative WIS than 83% of participating models’ forecasts of incident cases (with a total N=886 predictions from 23 unique models), and 91% of participating models’ forecasts of deaths (N=763 predictions from 20 models). Across a 1–4 week time horizon, ensemble performance declined with longer forecast periods when forecasting cases, but remained stable over 4 weeks for incident death forecasts. In every forecast across 32 countries, the ensemble outperformed most contributing models when forecasting either cases or deaths, frequently outperforming all of its individual component models. Among several choices of ensemble methods we found that the most influential and best choice was to use a median average of models instead of using the mean, regardless of methods of weighting component forecast models.Conclusions:Our results support the use of combining forecasts from individual models into an ensemble in order to improve predictive performance across epidemiological targets and populations during infectious disease epidemics. Our findings further suggest that median ensemble methods yield better predictive performance more than ones based on means. Our findings also highlight that forecast consumers should place more weight on incident death forecasts than incident case forecasts at forecast horizons greater than 2 weeks., Published by eLife Sciences Publications, Cambridge