Long monotone trails in random edge-labellings of random graphs

DOI10.1017/S096354831900018XzbMATH Open1465.05156arXiv1808.07351OpenAlexW2979430184WikidataQ127127569 ScholiaQ127127569MaRDI QIDQ5222568FDOQ5222568

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)

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)$.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Increasing paths in edge-ordered graphs: the hypercube and random graph
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Nearly-linear monotone paths in edge-ordered graphs
• Increasing Hamiltonian paths in random edge orderings
• 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

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)