Letter graphs and geometric grid classes of permutations

DOI10.1137/21M1449646MaRDI QIDQ5048304zbMATH OpenOpenAlexFDO

Authors Bogdan Alecu, Robert Ferguson, Mamadou Moustapha Kanté, Victor Zamaraev, Vadim Lozin, Vincent Vatter

Publication date 15 November 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutation patternswell-quasi-orderinversion graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Abstract: We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their respective classes of objects. We prove that these notions are equivalent in the sense that a permutation class is geometrically griddable if and only if the corresponding class of inversion graphs has bounded lettericity.

Recommendations

• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Geometric grid classes of permutations
• Growth rates of geometric grid classes of permutations
• Letter graphs and well-quasi-order by induced subgraphs

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3618209 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Classes of graphs without star forests and related graphs
• Combinatorics on traces
• Forbidden subsequences
• From words to graphs, and back
• Geometric grid classes of permutations
• Graph Classes: A Survey
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Inflations of geometric grid classes of permutations
• Labelled induced subgraphs and well-quasi-ordering
• Labelled well-quasi-order for permutation classes
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Letter graphs and modular decomposition
• Letter graphs and well-quasi-order by induced subgraphs
• On partial well-order for monotone grid classes of permutations
• On points drawn from a circle
• On the effective and automatic enumeration of polynomial permutation classes
• Ordering by Divisibility in Abstract Algebras
• Permutation classes
• Profile classes and partial well-order for permutations
• Restricted permutations and the wreath product
• Small permutation classes
• The Micro-world of Cographs
• Threshold graphs and related topics
• Zeros of the Möbius function of permutations

Cited in

(12)

• Geometric grid classes of permutations
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Hereditary classes of ordered sets of width at most two
• Generalized lettericity of graphs
• Deciding atomicity of subword-closed languages
• Decidability in geometric grid classes of permutations
• Labelled well-quasi-order for permutation classes
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
• Letter graphs and modular decomposition
• Bounds on the lettericity of graphs
• Ramsey numbers and graph parameters

This page was built for publication: Letter graphs and geometric grid classes of permutations

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