Twin-width IV: ordered graphs and matrices

DOI10.1145/3519935.3520037MaRDI QIDQ6083546zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, P. Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Toruńczyk

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

algorithmscomputational complexityenumerative combinatoricsmatricesmodel theoryordered graphsRamsey theorytwin-width

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains at least $n!$ matrices of size $nimesn$, or at most $c^n$ for some constant $c$. This generalizes the celebrated Stanley-Wilf conjecture/Marcus-Tardos theorem from permutation classes to any matrix class over a finite alphabet, answers our small conjecture [SODA '21] in the case of ordered graphs, and with more work, settles a question first asked by Balogh, Bollob'as, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width.

Recommendations

• Bounds for the twin-width of graphs
• Grid intersection graphs and order dimension
• scientific article; zbMATH DE number 4139805
• Twin-width and transductions of proper k-mixed-thin graphs
• On ordered graphs and graph orderings
• scientific article; zbMATH DE number 3902705
• Branch-width and well-quasi-ordering in matroids and graphs.
• scientific article; zbMATH DE number 3993776
• Extremal graphs of order dimension 4
• scientific article; zbMATH DE number 1958549

Cited in

(25)

• Bounds on the Twin-Width of Product Graphs
• Twin-width. II: Small classes
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Twin-width and transductions of proper \(k\)-mixed-thin graphs
• Planar graph with twin-width seven
• Twin-width of random graphs
• On classes of bounded tree rank, their interpretations, and efficient sparsification
• Isomorphism for tournaments of small twin width
• Computing twin-width parameterized by the feedback edge number
• Computing twin-width parameterized by the feedback edge number and vertex integrity
• Twin-width of planar graphs is at most 8, and some related bounds
• Graph theory. Abstracts from the workshop held January 5--10, 2025
• Stretch-width
• Decomposition horizons and a characterization of stable hereditary classes of graphs
• Sparse graphs of twin-width 2 have bounded tree-width
• Model checking disjoint-paths logic on topological-minor-free graph classes
• Elementary first-order model checking for sparse graphs
• The widths of strict outerconfluent graphs
• Decomposition horizons: from graph sparsity to model-theoretic dividing lines (extended abstract)
• Shallow vertex minors, stability, and dependence
• Compound logics for modification problems
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings
• Twin-width of graphs on surfaces
• Twin-width meets feedback edges and vertex integrity
• On computational aspects of cores of ordered graphs

This page was built for publication: Twin-width IV: ordered graphs and matrices

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