A class of formal languages

We deal with languages that are classes of fully invariant congruences on free semigroups of finite rank. The question is posed as to whether a given fully invariant congruence coincides with a syntactic congruence of the language in question. If all classes of a given fully invariant congruence are rational languages, the corresponding variety is then said to be rational. A number of properties of rational varieties is established—in particular, we point to the way in which they are related to finite varieties. Translated fromAlgebra i Logika, Vol. 37, No. 4, pp. 478–492, July–August, 1998.     

Universal Horn classes and antivarieties of algebraic systems

We define and study universal Horn classes dual to varieties in both the syntactic and the semantic sense. Such classes, which we call antivarieties, appear naturally, e.g., in graph theory and in formal language theory. The basic results are the characterization theorem for antivarieties, the theorem on cores in axiomatizable color-families, and the decidability theorem for universal theories of families of interpretations of formal languages. Supported by RFFR grants Nos. 99-01-000485 and 96-01-00097, and also by DFG grant No. 436113/2670. Translated fromAlgebra i Logika, Vol. 39, No. 1, pp. 3–22, January–February, 2000.     

Sur les automates qui reconnaissent une famille de langages

The main results about automatas and the languages they accept are easily extended to automatas which recognize a family of languages (L_i)_iεI of a free monoid, that is to automatas which recognize simultaneously all the languages L_i. This generalization enhances the notion of automata of type (p,r) introduced by S. Eilenberg [4]. In a similar way the notion of syntactic monoid of a family of languages extends the notion of syntactic monoid of a language. This extension is far from being trivial since we show that every finite monoid is the syntactic monoid of a recognizable partition of a free monoid, though this is false for the syntactic monoids of languages.      

Frucht theorem for inverse semigroups

In the paper, the problem of representing a finite inverse semigroup by partial transformations of a graph is treated. The notions of weighted graph and its weighted partial isomorphisms are introduced. The main result is that any finite inverse semigroup is isomorphic to the semigroup of weighted partial isomorphisms of a weighted graph. This assertion is a natural generalization of the Frucht theorem for groups. Translated fromMatematicheskie Zametki, Vol. 61, No. 2, pp. 246–251, February, 1997. This research was partially supported by the International Science Foundation under grant No. GSU 041049. Translated by A. I. Shtern     

A generalization of finiteness

We explore an analogy between the family ₁, of finite/cofinite languages and the family ₁ of languages whose syntactic monoids are J-trivial. It is shown that (a) J-trivial monoids, (b)L-trivial monoids, (c) R-trivial monoids, and (d) a recently studied family, that we callK, of aperiodic monoids are natural generalization of the families of syntactic semigroups of (a) finite/cofinite languages, (b) definite languages, (c) reverse definite languages, and (d) generalized definite languages, respectively. In the case of alphabets of one and two letters, the languages corresponding to the familyK of monoids are characterized, illustrating the above-mentioned analogy explicitly.This work was done partly at the University of Paris VI and VII under the scientific exchange program between Canada and France, and partly at the Institut für Rechner- und Programmstrukturen, Gesellschaft für Mathematik und Datenverarbeitung mbH. Bonn, Germany.     

Groups with an element permuting with finitely many of its conjugates

We study the problem as to which is the cardinality of connected components of the graph Γ_α, defined as follows. Let G be a group and a an element of G. The vertex set V(Γ_α) of the graph is the conjugacy class of elements,Cl _G(a), and two vertices x and y of the graph Γ_α are bridged by an edge iff x=y. If the intersectionC _G(a)∩Cl _G(a) is finite, Γ_α is locally finite. We prove that connected components of the locally finite graph Γ_α are finite in some classes of groups. Supported by RFFR grant No. 94-01-01084. Translated fromAlgebra i Logika, Vol. 35, No. 5, pp. 543–551, September–October, 1996.     

Construction of a certain class of line graphs

The construction of a line graph is described on the basis of a finite bipartite graph, for a given k > 1. An algorithm is set forth for the construction of the line graph and an example of its use is given.Translated from Dinamicheskie Sistemy, No. 4, pp. 107–116, 1985.     

An Adjacency Criterion for the Prime Graph of a Finite Simple Group

For every finite non-Abelian simple group, we give an exhaustive arithmetic criterion for adjacency of vertices in a prime graph of the group. For the prime graph of every finite simple group, this criterion is used to determine an independent set with a maximal number of vertices and an independent set with a maximal number of vertices containing 2, and to define orders on these sets; the information obtained is collected in tables. We consider several applications of these results to various problems in finite group theory, in particular, to the recognition-by-spectra problem for finite groups. Supported by RFBR grant No. 05-01-00797; by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1; by the RF Ministry of Education Developmental Program for Scientific Potential of the Higher School of Learning, project No. 8294; by FP “Universities of Russia,” grant No. UR.04.01.202; and by Presidium SB RAS grant No. 86-197. __________ Translated from Algebra i Logika, Vol. 44, No. 6, pp. 682–725, November–December, 2005.     

Cocliques of maximal size in the prime graph of a finite simple group

A prime graph of a finite group is defined in the following way: the set of vertices of the graph is the set of prime divisors of the order of the group, and two distinct vertices r and s are joined by an edge if there is an element of order rs in the group. We describe all cocliques of maximal size for finite simple groups.     

An approach to the zeta function of a finite factorgraph via the Markov topological chains

An approach to the zeta and the L-function of a finite connected graph via the theory of Markov topological chains (symbolic dynamics) is presented. The case of the L-function of a finite connected graph with labeling is considered. Bibliography: 12 titles. Dedicated to L. D. Faddeev on the occasion of his 60th birthday Published inZapiski Nauchnykh Seminarov POMI, Vol. 215, 1994, pp. 226–245. Translated by A. M. Nikitin.     

Recognition of finite groups by the prime graph

We obtain the first example of an infinite series of finite simple groups that are uniquely determined by their prime graph in the class of all finite groups. We also show that there exist almost simple groups for which the number of finite groups with the same prime graph is equal to 2. Supported by RFBR grant No. 05-01-00797, and by SB RAS Young Researchers Support grant No. 29 and Integration project No. 2006.1.2. __________ Translated from Algebra i Logika, Vol. 45, No. 4, pp. 390–408, July–August, 2006.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

On stationary characteristics of systems with element-wise supplement reserve of time

A system is considered that, contains elements which possess time reserve under a restoration. An analytic method of defining stationary characteristics of reliability is given by using compositions of semi-Markov processes with a finite set of states. An application of the results obtained is illustrated on an example of two model problems.Translated from Dinamicheskie Sistemy, No. 7, pp. 152–155, 1988.     

A logician's view of graph polynomials

Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.     

On inverse problems for the cycle graph operator

The cycle graph of a graph is the intersection graph of the edge set of all the induced cycles ofH. The main result of this paper is: A (K ₄−e)-free graph is a cycle graph if and only if it is a block graph where each vertex lies in a finite number of blocks. Some additional results are also given.     

Symmetrized Induced Ramsey Theory

We prove induced Ramsey theorems in which the monochromatic induced subgraph satisfies that all members of a prescribed set of its partial isomorphisms extend to automorphisms of the colored graph (without requirement of preservation of colors). We consider vertex and edge colorings, and extensions of partial isomorphisms in the set of all partial isomorphisms between singletons as considered by Babai and Sós (European J Combin 6(2):101–114, 1985), the set of all finite partial isomorphisms as considered by Hrushovski (Combinatorica 12(4):411–416, 1992), Herwig (Combinatorica 15:365–371, 1995) and Herwig-Lascar (Trans Amer Math Soc 5:1985–2021, 2000), and the set of all total isomorphisms. We observe that every finite graph embeds into a finite vertex transitive graph by a so called bi-embedding, an embedding that is compatible with a monomorphism between the corresponding automorphism groups. We also show that every countable graph bi-embeds into Rado’s universal countable graph Γ.     

Minimal extensions of graphs to absolute retracts

A graph H is an absolute retract if for every isometric embedding h of, into a graph G an edge-preserving map g from G to H exists such that g · h is the identity map on H. A vertex v is embeddable in a graph G if G ? v is a retract of G. An absolute retract is uniquely determined by its set of embeddable vertices. We may regard this set as a metric space. We also prove that a graph (finite metric space with integral distance) can be isometrically embedded into only one smallest absolute retract (injective hull). All graphs in this paper are finite, connected, and without multiple edges.     

Groups containing an element that permutes with a finite number of its conjugates

We study a group G containing an element g such that C_G(g)∩g^G is finite. The nonoriented graph Γ is defined as follows. The vertex set of Γ is the conjugacy class g^G. Vertices x and y of the graph G are bridged by an edge iff x≠y and xy=yx. Let Γ₀ be some connected component of G. On a condition that any two vertices of Γ₀ generate a nilpotent group, it is proved that a subgroup generated by the vertex set of Γ₀ is locally nilpotent. Supported by the RF State Committee of Higher Education. Translated fromAlgebra i Logika, Vol. 37, No. 6, pp. 637–650, November–December, 1998.     

Orthogonal latin square graphs

An orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. If G is an arbitrary finite graph, we say that G is realizable as an OLSG if there is an OLSG isomorphic to G. The spectrum of G [Spec(G)] is defined as the set of all integers n that there is a realization of G by latin squares of order n. The two basic theorems proved here are (1) every graph is realizable and (2) for any graph G, Spec G contains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a given n lies in the spectrum.