Name
Abstract | ||
|---|---|---|
Let f be an edge ordering of K-n: a bijection E(K-n) -> {1, 2,..., (n/2)}. For an edge e is an element of E(K-n), we call f (e) the label of e. An increasing path in K-n is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S(f) be the number of edges in the longest increasing path. Chvatal and Komlos raised the question of estimating m(n): the minimum value of S(f) over all orderings f of K-n. The best known bounds on m(n) are root n -1 <= m(n) = <= (1/2 + o(1)) n, due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades. In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S(f) often takes its maximum possible value of n - 1 (visiting all of the vertices with an increasing Hamiltonian path). We prove that this occurs with probability at least about 1/e. We also prove that with probability 1-o(1), there is an increasing path of length at least 0.85n, suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely. (C) 2015Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/rsa.20592 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
random graphs,edge labeling,monotone subsequences,Hamiltonian paths,algorithms | Discrete mathematics,Combinatorics,Path (graph theory),Bijection,Random graph,Vertex (geometry),Hamiltonian (quantum mechanics),Hamiltonian path,Almost surely,Mathematics | Journal |
Volume | Issue | ISSN |
48.0 | 3.0 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikhail Lavrov | 1 | 2 | 1.82 |
| Po-Shen Loh | 2 | 133 | 18.68 |