Long monotone trails in random edge-labellings of random graphs

DOI10.1017/S096354831900018XMaRDI QIDQ5222568zbMATH OpenOpenAlexWikidataFDO

Authors Omer Angel, Asaf Ferber, Vincent Tassion, Benny Sudakov

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Given a graph $G$ and a bijection $f:E(G)ightarrow1,2,ldots,e(G)$, we say that a trail/path in $G$ is $f$-emph{increasing} if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chv'atal and Koml'os raised the question of providing the worst-case estimates of the length of the longest increasing trail/path over all edge orderings of $K_n$. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is $n-1$, and the case of a path is still widely open. Recently Lavrov and Loh proposed to study the average case of this problem in which the edge ordering is chosen uniformly at random. They conjectured (and it was proved by Martinsson) that such an ordering with high probability (whp) contains an increasing Hamilton path. In this paper we consider random graph $G=G(n,p)$ and its edge ordering chosen uniformly at random. In this setting we determine whp the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average case of the result of Graham and Kleitman, showing that the random edge ordering of $K_n$ has whp an increasing trail of length $(1-o(1))en$ and this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random ErdH{o}-Renyi graphs with $p=o(1)$.

Recommendations

• Increasing Hamiltonian paths in random edge orderings
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Nearly-linear monotone paths in edge-ordered graphs
• Monotone paths in dense edge-ordered graphs
• On the minimal length of the longest trail in a fixed edge-density graph

Cites work

• A Combinatorial Lemma and Its Application to Probability Theory
• Increasing Hamiltonian paths in random edge orderings
• Increasing paths in edge ordered graphs
• Increasing paths in edge-ordered graphs: the hypercube and random graph
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Large monotone paths in graphs with bounded degree
• Minimal positions in a branching random walk
• Monotone paths in dense edge-ordered graphs
• Monotone paths in edge-ordered sparse graphs
• Most edge-orderings of \(K_{n}\) have maximal altitude
• Nearly-linear monotone paths in edge-ordered graphs
• On the Variance of the Height of Random Binary Search Trees
• Random graphs.
• Some Combinatorial Theorems on Monotonicity

Cited in

(7)

• Increasing paths in edge-ordered graphs: the hypercube and random graph
• Nearly-linear monotone paths in edge-ordered graphs
• Most edge-orderings of \(K_{n}\) have maximal altitude
• On the minimal length of the longest trail in a fixed edge-density graph
• Sharp Thresholds in Random Simple Temporal Graphs
• Increasing Hamiltonian paths in random edge orderings
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs

This page was built for publication: Long monotone trails in random edge-labellings of random graphs

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