Download PDF - Lattices of relative colour-families and antivarietiesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Lattices of relative colour-families and antivarieties

Authors 1

Affiliations

  1. Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia

Abstract

We consider general properties of lattices of relative colour-families and antivarieties. Several results generalise the corresponding assertions about colour-families of undirected loopless graphs, see [1]. Conditions are indicated under which relative colour-families form a lattice. We prove that such a lattice is distributive. In the class of lattices of antivarieties of relation structures of finite signature, we distinguish the most complicated (universal) objects. Meet decompositions in lattices of colour-families are considered. A criterion is found for existence of irredundant meet decompositions. A connection is found between meet decompositions and bases for anti-identities.

Keywords

ENG
colour-family, antivariety, lattice of antivarieties, meet decomposition, basis for anti-identities

Bibliography

  1. V.A. Gorbunov and A.V. Kravchenko, Universal Horn classes and colour-families of graphs, Algebra Universalis 46 (1-2) (2001), 43-67.
  2. V.A. Gorbunov and A. V. Kravchenko, Universal Horn classes and antivarieties of algebraic systems, Algebra Logic 39 (1) (2000), 1-11.
  3. L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hung. 18 (3-4) (1967), 321-328.
  4. D. Duffus and N. Sauer, Lattices arising in categorial investigations of Hedetniemi's conjecture, Discrete Math. 152 (1996), 125-139.
  5. J. Nešetřil and C. Tardif, Duality theorems for finite structures (charaterising gaps and good characterisations), J. Combin. Theory, B 80 (1) (2000), 80-97.
  6. R. Balbes and Ph. Dwinger, Distributive lattices, Univ. Missouri Press, Columbia, MI, 1974.
  7. G. Grätzer, General Lattice Theory, Birkhäusser, Basel 1998.
  8. A. Pultr and V. Trnková, Combinatorial, algebraic and topological representations of groups, semigroups and categories, Academia, Prague 1980.
  9. Z. Hedrlín, On universal partly ordered sets and classes, J. Algebra 11 (4) (1969), 503-509.
  10. J. Nešetřil, Aspects of structural combinatorics (Graph homomorphisms and their use), Taiwanese J. Math. 3 (4) (1999), 381-423.
  11. J. Nešetřil and A. Pultr, On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (3) (1978), 287-300.
  12. A.V. Kravchenko, On lattice complexity of quasivarieties of graphs and endographs, Algebra and Logic 36 (3) (1997), 164-168.
  13. V.A. Gorbunov and A.V. Kravchenko, Universal Horn logic, colour-families and formal languages, General Algebra and Applications in Discrete Mathematics (Proc. Conf. General Algebra Discrete Math.), Shaker Verlag, Aachen, 1997, pp. 77-91.
  14. D.P. Smith, Meet-irreducible elements in implicative lattices, Proc. Amer. Math. Soc. 34 (1) (1972), 57-62.
  15. S.S. Goncharov, Countable Boolean Algebras and Decidability, Plenum, New York-London-Moscow 1997.
  16. H. Rasiowa and R. Sikorski, The mathematics of metamathematics, Panstwowe Wydawnictwo Naukowe, Waszawa 1963.
  17. C. Tardif and X. Zhu, The level of nonmultiplicativity of graphs, Discrete Math. 244 (2002), 461-471.
Discussiones Mathematicae - General Algebra and Applications
2007/27/1
Export to PBN, Opens in new tab
Pages:
123-139
Main language of publication
English
Received
2006-04-25
Accepted
2006-06-21
Published
2007

DOI: 10.7151/dmgaa.1123

Exact and natural sciences