Simple extensions of combinatorial structures - Mathematics > CombinatoricsReportar como inadecuado

Simple extensions of combinatorial structures - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: An interval in a combinatorial structure S is a set I of points which relateto every point from S I in the same way. A structure is simple if it has noproper intervals. Every combinatorial structure can be expressed as aninflation of a simple structure by structures of smaller sizes - this iscalled the substitution or modular decomposition. In this paper we proveseveral results of the following type: An arbitrary structure S of size nbelonging to a class C can be embedded into a simple structure from C by addingat most fn elements. We prove such results when C is the class of alltournaments, graphs, permutations, posets, digraphs, oriented graphs andgeneral relational structures containing a relation of arity greater than 2.The function fn in these cases is 2, \lceil log 2n+1 ceil, \lceiln+1-2 ceil, \lceil n+1-2 ceil, \lceil log 4n+1 ceil, \lceil\log 3n+1 ceil and 1, respectively. In each case these bounds are bestpossible.

Autor: Robert Brignall, Nik Ruskuc, Vince Vatter


Documentos relacionados