Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-09T05:58:09.906Z Has data issue: false hasContentIssue false
  • English
  • Français

SIMPLE EXTENSIONS OF COMBINATORIAL STRUCTURES

Part of: Graph theory Model theory Ordered sets Combinatorics

Published online by Cambridge University Press:  21 December 2010

Robert Brignall ,
Nik Ruškuc  and
Vincent Vatter
Robert Brignall
Affiliation:
Department of Mathematics and Statistics, The Open University, Milton Keynes, MK7 6AA, England (email: [email protected])
Nik Ruškuc
Affiliation:
School of Mathematics and Statistics, University of St Andrews, St Andrews, KY16 9SS, Scotland (email: [email protected])
Vincent Vatter
Affiliation:
Department of Mathematics, University of Florida, Gainesville, Florida 32611, U.S.A. (email: [email protected])
Get access

Abstract

An interval in a combinatorial structure R is a set I of points that are related to every point in R∖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 𝒞 can be embedded into a simple structure from 𝒞 by adding at most f(n) elements. We prove such results when 𝒞 is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than two. The functions f(n) in these cases are 2, ⌈log 2(n+1)⌉, ⌈(n+1)/2⌉, ⌈(n+1)/2⌉, ⌈log 4(n+1)⌉, ⌈log 3(n+1)⌉ and 1, respectively. In each case these bounds are the best possible.

MSC classification

Secondary: 05C20: Directed graphs (digraphs), tournaments 06A06: Partial order, general 05C25: Graphs and abstract algebra (groups, rings, fields, etc.) 05A05: Permutations, words, matrices 03C13: Finite structures
Type
Research Article
Information
Mathematika , Volume 57 , Issue 2 , July 2011 , pp. 193 - 214
Copyright
Copyright © University College London 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bergeron, A., Chauve, C., de Montgolfier, F. and Raffinot, M., Computing common intervals of K permutations, with applications to modular decomposition of graphs. In Algorithms—ESA 2005 (Lecture Notes in Computer Science 3669), Springer (Berlin, 2005), 779–790.Google Scholar
[2]Brandstädt, A., Le, V. B. and Spinrad, J. P., Graph Classes: A Survey (SIAM Monographs on Discrete Mathematics and Applications 3), Society for Industrial and Applied Mathematics (SIAM) (Philadelphia, PA, 1999).Google Scholar
[3]Brignall, R., A survey of simple permutations. In Permutation Patterns (London Mathematical Society Lecture Note Series 376) (eds Linton, S., Ruškuc, N. and Vatter, V.), Cambridge University Press (Cambridge, 2010), 41–65.Google Scholar
[4]Cournier, A. and Habib, M., A new linear algorithm for modular decomposition. In Trees in Algebra and Programming—CAAP ’94 (Edinburgh, 1994) (Lecture Notes in Computer Science 787), Springer (Berlin, 1994), 68–84.Google Scholar
[5]Crvenković, S., Dolinka, I. and Marković, P., A survey of algebra of tournaments. Novi Sad J. Math. 29 (1999), 95–130.Google Scholar
[6]Dahlhaus, E., Gustedt, J. and McConnell, R. M., Efficient and practical modular decomposition. In Proceedings of the Eighth Annual ACM–SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), ACM (New York, 1997), 26–35.Google Scholar
[7]Ehrenfeucht, A., Harju, T. and Rozenberg, G., The Theory of 2-Structures, World Scientific Publishing Co. Inc. (River Edge, NJ, 1999).Google Scholar
[8]Erdős, P., Fried, E., Hajnal, A. and Milner, E. C., Some remarks on simple tournaments. Algebra Universalis 2 (1972), 238–245.Google Scholar
[9]Erdős, P., Hajnal, A. and Milner, E. C., Simple one-point extensions of tournaments. Mathematika 19 (1972), 57–62.Google Scholar
[10]Földes, S., On intervals in relational structures. Z. Math. Logik Grundlag. Math. 26(2) (1980), 97–101.Google Scholar
[11]Fraïssé, R., On a decomposition of relations which generalizes the sum of ordering relations. Bull. Amer. Math. Soc. 59 (1953), 389.Google Scholar
[12]Gallai, T., Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66.Google Scholar
[13]Gallai, T., A Translation of T. Gallai’s Paper: Transitiv Orientierbare Graphen (Wiley-Interscience Series in Discrete Mathematics and Optimization), Wiley (Chichester, 2001), 25–66.Google Scholar
[14]Ille, P., Indecomposable graphs. Discrete Math. 173(1–3) (1997), 71–78.Google Scholar
[15]McConnell, R. M. and de Montgolfier, F., Linear-time modular decomposition of directed graphs. Discrete Appl. Math. 145(2) (2005), 198–209.Google Scholar
[16]McConnell, R. M. and Spinrad, J. P., Modular decomposition and transitive orientation. Discrete Math. 201(1–3) (1999), 189–241.Google Scholar
[17]Möhring, R. H., On the distribution of locally undecomposable relations and independence systems. In Colloquium on Mathematical Methods of Operations Research (Aachen, 1980) (Methods of Operations Research 42), Athenäum/Hain/Hanstein (Königstein/Ts, 1981), 33–48.Google Scholar
[18]Möhring, R. H., An algebraic decomposition theory for discrete structures. In Universal Algebra and its Links with Logic, Algebra, Combinatorics and Computer Science (Darmstadt, 1983) (Research and Exposition in Mathematics 4), Heldermann (Berlin, 1984), 191–203.Google Scholar
[19]Möhring, R. H., Algorithmic aspects of comparability graphs and interval graphs. In Graphs and Order (Banff, Alta., 1984) (NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences 147), Reidel (Dordrecht, 1985), 41–101.Google Scholar
[20]Möhring, R. H. and Radermacher, F. J., Substitution decomposition for discrete structures and connections with combinatorial optimization. In Algebraic and Combinatorial Methods in Operations Research (North-Holland Mathematics Studies 95), North-Holland (Amsterdam, 1984), 257–355.Google Scholar
[21]Moon, J. W., Embedding tournaments in simple tournaments. Discrete Math. 2 4 (1972), 389–395.Google Scholar
[22]Sabidussi, G., Graph derivatives. Math. Z. 76 (1961), 385–401.Google Scholar
[23]Sumner, D. P., Indecomposable graphs. PhD Thesis, University of Massachusetts, 1971.Google Scholar