How many random edges make a dense graph hamiltonian?

DOI10.1002/RSA.10070MaRDI QIDQ4798179zbMATH OpenOpenAlexWikidataFDO

Authors Tom Bohman, Ryan R. Martin, Alan Frieze

Publication date 19 March 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.07243

zbMATH Keywords

Hamilton cycle random digraph random graph rotation method

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding

T h e t a (n)

random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs.

Review text

The basic situation of this paper is to take a graph \(H\) chosen arbitrarily from a certain class of graphs, and to add some random set \(R\) of additional edges to the graph (but not new vertices). Interest is then in the typical properties of the resulting graph \(G\). For example, the question asked in this paper is how many edges need to be added to make the resulting graph Hamiltonian \textbf{whp}, where a property \(\wp\) of random graphs is said to hold \textbf{whp} if \[ \lim_{n\rightarrow\infty}P(G\text{~has~}\wp\}=1 \] where \(n\) is the number of vertices. It is important to emphasise that \(H\) is arbitrary, and so that when we insist the property should hold \textbf{whp} this means irrespective of the (possibly adversarial) choice of \(H\) from this class. This is clearly a very general framework: for example, the classical model of random graphs \(G(n,m)\) (where all graphs with \(n\) labelled vertices and \(m\) edges are equally likely) is a (rather degenerate) special case, where we insist that \(H\) come from the class of graphs with no edges. This paper considers the question of when a Hamilton cycle arises, for certain classes of graphs \(H\). Let \(0<d<1\) be a fixed constant, and consider \(H\) to be taken from the set \({\mathcal G}(n,d)\) of graphs with vertex set \(\{1,2,\ldots,n\}\) whose minimum degree \(\delta\) is at least \(dn\). If \(d\geq 1/2\) by Dirac's theorem \(H\) is already Hamiltonian, so we assume \(d<1/2\). Let \(R\) be a subset, of size \(m\) of the possible edges which are not already in \(E(H)\), all such subsets being equally likely to be chosen. For convenience, set \(\theta=-\ln(d)>0.69\dots\;\). The first theorem proved in this paper is that if \(m\geq (30\theta+13)n\) then \(G\), the graph with edges \(E(H)\cup R\), is Hamiltonian \textbf{whp}. However, for \(d\leq 1/10\) there exist graphs in \({\mathcal G}(n,d)\) for which, if \(m<\theta n/3\) then \textbf{whp} \(G\) is not Hamiltonian. Though this is not a clean-cut threshold result, it does make it clear that the order of magnitude of the number of edges which have to be added is \(n\). This is in a sense rather disappointing, since a graph \(H\in {\mathcal G}(n,d)\) is already likely to be Hamiltonian (with considerable room to spare). Some obvious exceptions are bipartite graphs with unequally sized vertex classes and the right density; these \(H\) of course have independence number \(\alpha(H)>n/2\). This suggests large independence number might be the problem, and this motivates the next theorem. It states that, if \(H\in {\mathcal G}(n,d)\) has \(\alpha(H)<d(n)^{2}n/2\) (note that in this theorem \(d\) need not be constant) and \(R\) is a set of \(m\) non-edges of \(H\) selected uniformly and at random (as above), then provided \(md^{3}/\theta\rightarrow \infty\) as \(n\rightarrow\infty\), \(G\) is Hamiltonian \textbf{whp}. The third result is a similar problem for digraphs. Let \(A(D)\) be the set of arcs of the digraph \(D\), \(\delta^{+}\) be the minimum outdegree and \(\delta^{-}\) the minimum indegree, \(\delta=\min\{\delta^{+},\delta^{-}\}\). Let \(0<d<1/2\) be a fixed positive constant (again the case \(d\geq 1/2\) is trivial). Let \({\mathcal D}(n,d)\) be the set of digraphs with vertex set \(\{1,2,\ldots, n\}\) with \(\delta\geq dn\). Again let \(\theta=-\ln(d)\). Suppose \(H\in {\mathcal D}(n,d)\) and \(R\), with \(|R|=m\) is chosen uniformly and at random from the \(n^{2}-|A(H)|\) non-arcs of \(H\). Then if \(m\geq n(d^{-1}(15+6\theta)+5d^{-2})\), \(D\) is Hamiltonian \textbf{whp}, but if \(d\leq 1/10\) there are graphs in \({\mathcal D}(n,d)\) such that, if \(m\leq \theta n/3\) then \textbf{whp} \(D\) is not Hamiltonian. As so often in arguments proving a graph is Hamiltonian, the rotation method of L. Pósa plays a key role in the (positive part of) Theorem 1, as does a technical lemma showing that if \(\lceil 30\theta n\rceil\) random edges are added to \(H\) the resulting graph is connected with reasonable expanding properties. The negative part of the result is obtained by considering \(H\) to be a complete bipartite graph with classes of size \(dn\) and \((1-d)n\) and using the second moment method to show that \(I\), the number of edges of the larger class not incident with an edge of \(R\) is close to its mean \(f(d)n\) where \(f(d)\neq 0\). For Theorem 2, a technical lemma is proved showing that \(V(G)\) can be partitioned in a small number of vertex disjoint cycles, then using a refinement procedure which \textbf{whp} reduces the number of such cycles (eventually to 1). In Theorem 3, the proof is to show that \textbf{whp} \(H_{1}\), comprising \(H\) and some of the edges in \(R\), has a (directed) cycle cover; again a certain procedure, dependent on reasonable expansion-type properties, allows this cycle cover to be turned into a Hamilton cycle \textbf{whp}. The negative part is similar to the negative part of Theorem~1.

Recommendations

Cited in

(75)

This page was built for publication: How many random edges make a dense graph hamiltonian?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4798179)