Simple extensions of combinatorial structures

DOI10.1112/S0025579310001518MaRDI QIDQ3087001zbMATH OpenFDO

Authors Robert Brignall, N. Ruškuc, Vincent Vatter

Publication date 1 August 2011

Published in Mathematika (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Partial orders, general (06A06) Model theory of finite structures (03C13) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: An interval in a combinatorial structure S is a set I of points which relate to every point from S I in the same way. A structure is simple if it has no proper intervals. Every combinatorial structure can be expressed as an inflation of a simple structure by structures of smaller sizes -- this is called the substitution (or modular) decomposition. In this paper we prove several results of the following type: An arbitrary structure S of size n belonging to a class C can be embedded into a simple structure from C by adding at most f(n) elements. We prove such results when C is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than 2. The function f(n) in these cases is 2, lceil log_2(n+1) ceil, lceil (n+1)/2 ceil, lceil (n+1)/2 ceil, lceil log_4(n+1) ceil, lceil log_3(n+1) ceil and 1, respectively. In each case these bounds are best possible.

Recommendations

• Decomposing simple permutations, with enumerative consequences
• scientific article; zbMATH DE number 4214076
• Some remarks on simple tournaments
• Some intersection theorems for structures
• Some intersection theorems for structures

Cites work

• Embedding tournaments in simple tournaments
• Graph Classes: A Survey
• Graph derivatives
• Indecomposable graphs
• Linear-time modular decomposition of directed graphs
• Modular decomposition and transitive orientation
• On Intervals in Relational Structures
• Simple one‐point extensions of tournaments
• Some remarks on simple tournaments
• Transitiv orientierbare Graphen

Cited in

(4)

• scientific article; zbMATH DE number 6287632 (Why is no real title available?)
• Making a tournament indecomposable by one subtournament-reversal operation
• Editing to prime graphs
• Simple confluently persistent catenable lists

This page was built for publication: Simple extensions of combinatorial structures

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