Primitive positive clones of groupoids

We prove that if two finite groupoids with unity have the same ternary compatible relations, then they have the same primitive positive clones. Received October 23, 2007; accepted in final form February 22, 2008.     

Cancellation in entropic algebras

We describe the equational theory of the class of cancellative entropic algebras of a fixed type. We prove that a cancellative entropic algebra embeds into an entropic polyquasigroup, a natural generalization of a quasigroup. In fact our results are even more general and some corollaries hold also for non-entropic algebras. For instance an algebra with a binary cancellative term operation, which is a homomorphism, is quasi-affine. This gives a strengthening of K. Kearnes’ theorem. Our results generalize theorems obtained earlier by M. Sholander and by J. Ježek and T. Kepka in the case of groupoids. The work on this paper was conducted within the framework of INTAS project no. 03 51 4110 “Universal algebra and lattice theory”. The author was also supported by the Statutory Grant of Warsaw University of Technology no. 504G11200013000.     

CD(4) has bounded width

We prove that the constraint languages invariant under a short sequence of Jónsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves a previous result by Kiss and Valeriote and presents some evidence that the Larose–Zádori conjecture holds in the congruence-distributive case. The first author was supported by EPSRC grant EP/C54384X/1. The second author was supported by the MEC under grant TIN 2006-15387-C03-03, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The third author was supported by grant no. 144011G of the Ministry of Science and Environment of Serbia. The fourth author was partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant nos. T 48809 and K 60148.     

The inflation class operator

We consider the inflation class operator, denoted by F, where for any class K of algebras, F(K) is the class of all inflations of algebras in K. We study the interaction of this operator with the usual algebraic operators H, S andP, and describe the partially-ordered monoid generated by H, S, P andF (with the isomorphism operator I as an identity). Received February 3, 2004; accepted in final form January 3, 2006.     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

On a graph packing conjecture by Bollobás,Eldridge and Catlin

Two graphs G ₁ and G ₂ of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets are disjoint. In 1978, Bollobás and Eldridge, and independently Catlin, conjectured that if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ n + 1, then G ₁ and G ₂ pack. Towards this conjecture, we show that for Δ(G ₁),Δ(G ₂) ≥ 300, if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ 0.6n + 1, then G ₁ and G ₂ pack. This is also an improvement, for large maximum degrees, over the classical result by Sauer and Spencer that G ₁ and G ₂ pack if Δ(G ₁)Δ(G ₂) < 0.5n. This work was supported in part by NSF grant DMS-0400498. The work of the second author was also partly supported by NSF grant DMS-0650784 and grant 05-01-00816 of the Russian Foundation for Basic Research. The work of the third author was supported in part by NSF grant DMS-0652306.     

Equational theories as congruences of enriched monoids

The problem of characterizing the lattices of equational theories is still unsolved. In this paper we describe a class of monoids enriched by two unary operations and show that a lattice L is a lattice of equational theories if and only if L is isomorphic to a lattice of congruences of some enriched monoid belonging to . The author was supported by INTAS grant 03-51-4110 and The Alexander von Humboldt Foundation.     

Types of polynomial completeness of expanded groups

The polynomial functions of an algebra preserve all congruence relations. In addition, if the algebra is finite, they preserve the labelling of the congruence lattice in the sense of Tame Congruence Theory. The question is for which algebras every congruence preserving function, or at least every function that preserves the labelling of the congruence lattice, is a polynomial function. In this paper, we investigate this question for finite algebras that have a group reduct. Presented by K. Kaarli. Received March 12, 2006; accepted in final form October 16, 2008. The second author is supported by Grant No. 144011 of the Ministry of Science of the Republic of Serbia, and the Scholarship “One-Month Visits to Austria for University Graduates” WUS-Austria, from the Austrian Ministry of Education, Science and Culture.     

On the semidistributivity of elements in weak congruence lattices of algebras and groups

Weak congruence lattices and semidistributive congruence lattices are both recent topics in universal algebra. This motivates the main result of the present paper, which asserts that a finite group G is a Dedekind group if and only if the diagonal relation is a join-semidistributive element in the lattice of weak congruences of G. A variant in terms of subgroups rather than weak congruences is also given. It is pointed out that no similar result is valid for rings. An open problem and some results on the join-semidistributivity of weak congruence lattices are also included. This research of the second and third authors was partially supported by Serbian Ministry of Science and Environment, Grant No. 144011 and by the Provincial Secretariat for Science and Technological Development, Autonomous Province of Vojvodina, grant ”Lattice methods and applications”.     

The toric ideal of a graphic matroid is generated by quadrics

Describing minimal generating sets of toric ideals is a well-studied and difficult problem. Neil White conjectured in 1980 that the toric ideal associated to a matroid is generated by quadrics corresponding to single element symmetric exchanges. We give a combinatorial proof of White’s conjecture for graphic matroids.     

The superstar packing problem

Hell and Kirkpatrick proved that in an undirected graph, a maximum size packing by a set of non-singleton stars can be found in polynomial time if this star-set is of the form {S ₁, S ₂, ..., S _k } for some k∈ℤ₊ (S _i is the star with i leaves), and it is NP-hard otherwise. This may raise the question whether it is possible to enlarge a set of stars not of the form {S ₁, S ₂, ..., S _k } by other non-star graphs to get a polynomially solvable graph packing problem. This paper shows such families of depth 2 trees. We show two approaches to this problem, a polynomial alternating forest algorithm, which implies a Berge-Tutte type min-max theorem, and a reduction to the degree constrained subgraph problem of Lovász. Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No. 504438.     

The parity problem of polymatroids without double circuits

According to the present state of the theory of the matroid parity problem, the existence of a good characterization to the size of a maximum matching depends on the behavior of certain substructures, called double circuits. In this paper we prove that if a polymatroid has no double circuits then a partition type min-max formula characterizes the size of a maximum matching. Applications to parity constrained orientations and to a rigidity problem are given. Research is supported by OTKA grants K60802, TS049788 and by European MCRTN Adonet, Contract Grant No. 504438.     

Proof of the bandwidth conjecture of Bollobás and Komlós

In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r ? 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most β n and maximum degree at most Δ, then G contains a copy of H.     

Note making a <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free graph bipartite

We show that every K ₄-free graph G with n vertices can be made bipartite by deleting at most n ²/9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete 3-partite graph with parts of size n/3. This proves an old conjecture of P. Erdős. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

The product of two von Neumann n-frames, its characteristic, and modular fractal lattices

Let L be a bounded lattice. If for each a₁ < b₁ ∈ L and a₂ < b₂ ∈ L there is a lattice embedding ψ: [a₁, b₁] → [a₂, b₂] with ψ(a₁) = a₂ and ψ(b₁) = b₂, then we say that L is a quasifractal. If ψ can always be chosen to be an isomorphism or, equivalently, if L is isomorphic to each of its nontrivial intervals, then L will be called a fractal lattice. For a ring R with 1 let denote the lattice variety generated by the submodule lattices of R-modules. Varieties of this kind are completely described in [16]. The prime field of characteristic p will be denoted by F_p. Let be a lattice variety generated by a nondistributive modular quasifractal. The main theorem says that is neither too small nor too large in the following sense: there is a unique , a prime number or zero, such that and for any n ≥ 3 and any nontrivial (normalized von Neumann) n-frame of any lattice in , is of characteristic p. We do not know if in general; however we point out that, for any ring R with 1, implies . It will not be hard to show that is Arguesian. The main theorem does have a content, for it has been shown in [2] that each of the is generated by a single fractal lattice L_p; moreover we can stipulate either that L_p is a continuous geometry or that L_p is countable. The proof of the main theorem is based on the following result of the present paper: if is a nontrivial m-frame and is an n-frame of a modular lattice L with m, n ≥ 3 such that and , then these two frames have the same characteristic and, in addition, they determine a nontrivial mn-frame of the same characteristic in a canonical way, which we call the product frame. Presented by E. T. Schmidt.     

Endomorphisms of monadic Boolean algebras

A classical result about Boolean algebras independently proved by Magill [10], Maxson [11], and Schein [17] says that non-trivial Boolean algebras are isomorphic whenever their endomorphism monoids are isomorphic. The main point of this note is to show that the finite part of this classical result is true within monadic Boolean algebras. By contrast, there exists a proper class of non-isomorphic (necessarily) infinite monadic Boolean algebras the endomorphism monoid of each of which has only one element (namely, the identity), this being the first known example of a variety that is not universal (in the sense of Hedrlín and Pultr), but contains a proper class of non-isomorphic rigid algebras (that is, the identity is the only endomorphism). Received February 3, 2006; accepted in final form September 5, 2006.     

Convexities of partial monounary algebras

In the present paper we prove that the collection of all convexities of partial monounary algebras is finite; namely, it has exactly 23 elements. Further, we show that for each element there exists a subset of such that is generated by and card . This work was supported by the Science and Technology Assistance Agency under the contract No. APVT-20-004104. Supported by Grant VEGA 1/3003/06.     

Semidirect products of lattices

The semidirect product of lattices is a lattice analogue of the semidirect product of groups. In this article we introduce this construction, show some basic facts and study a class of lattices closed under semidirect products. We also generalise this notion presenting the semidirect product of semilattices. Received February 22, 2005; accepted in final form August 29, 2006.     

Terms that are self-dual in Boolean algebras but not in MO 2

An absorption law is an identity of the form p = x. The ternary function x+y+z (ring addition) in Boolean algebras satisfies three absorption laws in two variables. If a term satisfies these three identities in a variety, it is called a minority term for that variety. We construct a minority term p for orthomodular lattices such the identity defines Boolean algebras modulo orthomodular lattices. (The dual of p is denoted by .) Consequently, having a unique minority term function characterizes Boolean algebras among orthomodular lattices. Our main result generalizes this example to arbitrary arity and arbitrary consistent sets of 2-variable absorption laws. Presented by J. Berman.