pith. machine review for the scientific record. sign in

arxiv: 1108.2502 · v3 · submitted 2011-08-11 · 🧮 math.CO

Recognition: unknown

Dirac's theorem for random graphs

Authors on Pith no claims yet
classification 🧮 math.CO
keywords randomdegreediraceverygraphgraphshamiltonianleast
0
0 comments X
read the original abstract

A classical theorem of Dirac from 1952 asserts that every graph on $n$ vertices with minimum degree at least $\lceil n/2 \rceil$ is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if $p \gg \log n /n$, then a.a.s. every subgraph of $G(n,p)$ with minimum degree at least $(1/2+o(1))np$ is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability $p$ and the value of the constant 1/2 are asymptotically best possible.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.