2021/06/06 by Bogdan Alecu, Alecu, Bogdan, Vadim Lozin +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2106.03267
openalex publication_date 2021/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Lettericity is a graph parameter introduced by Petkovšek in 2002 in order to study well-quasi-orderability under the induced subgraph relation. In the world of permutations, geometric griddability was independently introduced in 2013 by Albert, Atkinson, Bouvel, Ruškuc and Vatter, partly as an enumerative tool. Despite their independent origins, those two notions share a connection: they highlight very similar structural features in their respective objects. The fact that those structural features arose separately on two different occasions makes them very interesting to study in their own right. In the present paper, we explore the notion of lettericity through the lens of "minimal obstructions", i.e., minimal classes of graphs of unbounded lettericity, and identify an infinite collection of such classes. We also discover an intriguing structural hierarchy that arises in the study of lettericity and that of griddability.