Simple extensions of combinatorial structures - Mathematics > CombinatoricsReport as inadecuate

Simple extensions of combinatorial structures - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

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.

Author: Robert Brignall, Nik Ruskuc, Vince Vatter



Related documents