Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Getting directed Hamilton cycle twice faster   Consider the random graph process where we start with an empty graph on n
vertices, and at time t, are given an edge e_t chosen uniformly at random among
the edges which have not appeared so far. A classical result in random graph
theory asserts that w.h.p. the graph becomes Hamiltonian at time (1/2+o(1))n
log n. On the contrary, if all the edges were directed randomly, then the graph
has a directed Hamilton cycle w.h.p. only at time (1+o(1))n log n. In this
paper we further study the directed case, and ask whether it is essential to
have twice as many edges compared to the undirected case. More precisely, we
ask if at time t, instead of a random direction one is allowed to choose the
orientation of e_t, then whether it is possible or not to make the resulting
directed graph Hamiltonian at time earlier than n log n. The main result of our
paper answers this question in the strongest possible way, by asserting that
one can orient the edges on-line so that w.h.p., the resulting graph has a
directed Hamilton cycle exactly at the time at which the underlying graph is
Hamiltonian.

36
The categories of this paper are: cmp-lg
13
The categories of this paper are: quant-ph
6
The categories of this paper are: astro-ph
34
The categories of this paper are: chem-ph
1
The categories of this paper are: cs
18
The categories of this paper are: econ
25
The categories of this paper are: patt-sol
32
The categories of this paper are: atom-ph
26
The categories of this paper are: bayes-an
20
The categories of this paper are: acc-phys
7
The categories of this paper are: hep-th
11
The categories of this paper are: hep-lat
15
The categories of this paper are: nucl-ex
31
The categories of this paper are: ao-sci
27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th