Tangled paths: a random graph model from Mallows permutations

DOI10.37236/11602MaRDI QIDQ6977157zbMATH OpenFDO

Authors Jessica Enright, Kitty Meeks, William Pettersson, John Sylvester

Publication date 30 May 2025

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.37236/11602

zbMATH Keywords

Mallows permutationtangled path

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites work

• A note on the width of sparse random graphs
• A Separator Theorem for Planar Graphs
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Cliques in the union of \(C_4\)-free graphs
• Cliques in the union of graphs
• Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
• Decompositions into isomorphic rainbow spanning trees
• Decompositions into spanning rainbow structures
• Degree sequence of random permutation graphs
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Every monotone graph property has a sharp threshold
• Expander graphs and their applications
• Expanders via Random Spanning Trees
• How many graphs are unions of k‐cliques?
• How many random edges make a dense graph hamiltonian?
• scientific article; zbMATH DE number 3728625 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• Independent sets in the union of two Hamiltonian cycles
• Introduction to Random Graphs
• Lengths of monotone subsequences in a Mallows permutation
• Mallows permutations and finite dependence
• Mallows permutations as stable matchings
• Noisy sorting without resampling
• NON-NULL RANKING MODELS. I
• On the Cutwidth and the Topological Bandwidth of a Tree
• On the cycle structure of Mallows permutations
• On the perfect orderability of unions of two graphs
• On the Problem of Decomposing a Graph into n Connected Factors
• On tree width, bramble size, and expansion
• Parameterized algorithms
• Permutations avoiding a pattern of length three under Mallows distributions
• Probability and Computing
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Rank-width of random graphs
• Sparsity. Graphs, structures, and algorithms
• Tail bounds for sums of geometric and exponential variables
• Tangled paths: a random graph model from Mallows permutations (extended abstract)
• The length of the longest increasing subsequence of a random Mallows permutation
• The probability of avoiding consecutive patterns in the Mallows distribution
• The Treewidth and Pathwidth of Graph Unions
• Thermodynamic limit for the Mallows model on S_n
• Treewidth. Computations and approximations

Cited in

(1)

• Logical limit laws for Mallows random permutations

This page was built for publication: Tangled paths: a random graph model from Mallows permutations

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