Weakly representable atom structures that are not strongly representable,with an application to first order logic

Letn > 2. A weakly representable relation algebra that is not strongly representable is constructed. It is proved that the set of all n by n basic matrices forms a cylindric basis that is also a weakly but not a strongly representable atom structure. This gives an example of a binary generated atomic representable cylindric algebra with no complete representation. An application to first order logic is given. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Existence of u‐Representation of Graphs

Recently, Jones et al. (Electron J Comb 22(2) (2015), #P2.53) introduced the study of u‐representable graphs, where u is a word over containing at least one 1. The notion of a u‐representable graph is a far‐reaching generalization of the notion of a word‐representable graph studied in the literature in a series of papers. Jones et al. have shown that any graph is 11???1‐representable assuming that the number of 1s is at least three, while the class of 12‐representable graphs is properly contained in the class of comparability graphs, which, in turn, is properly contained in the class of word‐representable graphs corresponding to 11‐representable graphs. Further studies in this direction were conducted by Nabawanda (M.Sc. thesis, 2015), who has shown, in particular, that the class of 112‐representable graphs is not included in the class of word‐representable graphs. Jones et al. raised a question on classification of u‐representable graphs at least for small values of u . In this article, we show that if u is of length at least 3 then any graph is u‐representable. This rather unexpected result shows that from existence of representation point of view there are only two interesting nonequivalent cases in the theory of u‐representable graphs, namely, those of and .     

Representations of graphs modulo n

A graph is representable modulo n if its vertices can be labeled with distinct integers between 0 and n, the difference of the labels of two vertices being relatively prime to n if and only if the vertices are adjacent. Erd?s and Evans recently proved that every graph is representable modulo some positive integer. We derive a combinatorial formulation of representability modulo n and use it to characterize those graphs representable modulo certain types of integers, in particular integers with only two prime divisors. Other facets of representability are also explored. We obtain information about the values of n modulo which paths and cycles are representable.     

Algebras of Recursively Enumerable Sets and Their Applications to Fuzzy Logic

Algebras of operations defined on recursively enumerable sets of different kinds are considered. Every such algebra is specified by a list of operations involved and a list of basic elements. An element of an algebra is said to be representable in this algebra if it can be obtained from given basic elements by operations of the algebra. Two kinds of recursively enumerable sets are considered: recursively enumerable sets in the usual sense and fuzzy recursively enumerable sets. On binary, i.e., two-dimensional recursively enumerable sets of these kinds, algebras of operations are introduced. An algebra θ is constructed in which all binary recursively enumerable sets are representable. A subalgebra θ⁰ of θ is constructed in which all binary recursively enumerable sets are representable if and only if they are described by formulas of Presburger’s arithmetic system. An algebra Ω is constructed in which all binary recursively enumerable fuzzy sets are representable. A subalgebra Ω⁰ of the algebra Ω is constructed such that fuzzy recursively enumerable sets representable in Ω⁰ can be treated as fuzzy counterparts of sets representable by formulas of Presburger’s system. Bibliography: 16 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 304, 2003, pp. 75–98.     

Bifunctional-elementary relation algebras

A relation algebra is bifunctional-elementary if it is atomic and for any atom a, the element a;1;a is the join of at most two atoms, and one of these atoms is bifunctional (an element x is bifunctional if ’). We show that bifunctional-elementary relation algebras are representable. Our proof combines the representation theorems for: pair-dense relation algebras given by R. Maddux; relation algebras generated by equivalence elements provided corresponding relativizations are representable by S. Givant; and strong-elementary relation algebras dealt with in our earlier work. It turns out that atomic pair-dense relation algebras are bifunctional elementary, showing that our theorem generalizes the representation theorem of atomic pair-dense relation algebras. The problem is still open whether the related classes of rather elementary, functional-elementary, and strong functional-elementary relation algebras are representable. Received July 15, 2007; accepted in final form March 17, 2008.     

Representable orientations of the free spikes

All orientations of binary and ternary matroids are representable [R.G. Bland, M. Las Vergnas, Orientability of matroids, J. Combinatorial Theory Ser. B 24 (1) (1978) 94–123; J. Lee, M. Scobee, A characterization of the orientations of ternary matroids, J. Combin. Theory Ser. B 77 (2) (1999) 263–291]. In this paper we show that this is not the case for matroids that are representable over GF(p^k) where k2. Specifically, we show that there are orientations of the rank-k free spike that are not representable for all k4. The proof uses threshold functions to obtain an upper bound on the number of representable orientations of the free spikes.     

Banaschewski’s theorem for generalized <Emphasis Type="Italic">MV</Emphasis>-algebras

A generalized MV-algebra A is called representable if it is a subdirect product of linearly ordered generalized MV-algebras. Let S be the system of all congruence relations ϱ on A such that the quotient algebra A/ϱ is representable. In the present paper we prove that the system S has a least element. This work was supported by Science and Technology Assistance Agency under Contract No AVPT-51-032002. The work has been partially supported by the Slovak Academy of Sciences via the project Center of Excellence-Physics of Information (grant I/2/2005).     

Representable Functions on the Unit Ball of a Banach Space

In this paper we treat the problem of integral representation of analytic functions over the unit ball of a complex Banach space X using the theory of abstract Wiener spaces. We define the class of representable functions on the unit ball of X and prove that this set of functions is related with the classes of integral k–homogeneous polynomials, integral holomorphic functions and also with the set of L ^p –representable functions on a Banach space.     

On neat embeddings of cylindric algebras

We show that certain properties of dimension complemented cylindric algebras, concerning neat embeddings, do not generalize much further. Let α ≥ ω. There are non‐isomorphic representable cylindric algebras of dimension α each of which is a generating subreduct of the same β dimensional cylindric algebra. We also show that there exists a representable cylindric algebra ?? of dimension α, such that ?? is a generating subreduct of ?? and ??′, both in CA_{α +ω} , however ?? and ??′ are not isomorphic. This settle questions raised by Henkin, Monk and Tarski (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

Intervals in l-groups as L-algebras

L-algebras are related to algebraic logic and quantum structures. They were introduced by the first author [J. Algebra 320 (2008)], where a self-similar closure S(X) of any L-algebra X was employed to derive a criterion for X to be representable as an interval in a lattice-ordered group. In the present paper, this criterion is improved without using the embedding. It is shown that an L-algebra is representable as an interval in a lattice-ordered group if and only if it is semiregular with a smallest element and bijective negation. Any such L-algebra gives rise to a perfect dual with respect to the inverse of the negation. This is proved by a self-dual characterization of semiregularity.     

Combinatorial geometries representable over GF(3) and GF(q). II. Dowling geometries

Letq be an odd prime power not divisible by 3. In Part I of this series, it was shown that the number of points in a rank-n combinatorial geometry (or simple matroid) representable over GF(3) and GF(q) is at mostn ². In this paper, we show that, with the exception ofn = 3, a rank-n geometry that is representable over GF(3) and GF(q) and contains exactlyn ² points is isomorphic to the rank-n Dowling geometry based on the multiplicative group of GF(3).This research was partially supported by the National Science Foundation under Grants DMS-8521826 and DMS-8500494.     

Orienting Matroids Representable Over BothGF(3) andGF(5)

For matroids representable over both GF(3) and GF(5) , we provide a method for constructing an orientation.     

Irrepresentability of short semilattices by euclidean subspaces

A semilatticeS isrepresentable by subspaces of R ^k if, to eachx S we can assign a subspace so thatx y=z inS if and only if . Every height-2 semilattice is representable inR ². We show that for everyk there is a height-3 semilattice which is not representable by subspaces ofR ^k.Presented by J. Berman.Research supported in part by the National Science Foundation.Research supported in part by the Office of Naval Research.     

The problem of envelopes for Banach spaces

LetX be a Banach space. A Banach spaceY is an envelope ofX if (1)Y is finitely representable inX; (2) any Banach spaceZ finitely representable inX and of density character not exceeding that ofY is isometric to a subspace ofY. Lindenstrauss and Pelczynski have asked whether any separable Banach space has a separable envelope. We give a negative answer to this question by showing the existence of a Banach space isomorphic tol ₂, which has no separable envelope. A weaker positive result holds: any separable Banach space has an envelope of density character ≦ℵ₁ (assuming the continuum hypothesis).     

Non-effective deformations of Grothendieck’s Hilbert functor

We show that the Hilbert functor of rank one families on a non-separated scheme X admits deformations that are not effective. For such ambient schemes we have that the Hilbert functor is not representable by a scheme or an algebraic space.     

Matroids and quotients of spheres

For any linear quotient of a sphere, where is an elementary abelian p–group, there is a corresponding representable matroid which only depends on the isometry class of X. When p is 2 or 3 this correspondence induces a bijection between isometry classes of linear quotients of spheres by elementary abelian p–groups, and matroids representable over Not only do the matroids give a great deal of information about the geometry and topology of the quotient spaces, but the topology of the quotient spaces point to new insights into some familiar matroid invariants. These include a generalization of the Crapo–Rota critical problem inequality and an unexpected relationship between and whether or not the matroid is affine. Received: 7 February 2001; in final form: 30 October 2001/ Published online: 29 April 2002     

Estimate for the Best Approximation of Summable Functions of Several Variables with a Certain Symmetry of Fourier Coefficients

An upper bound for the best approximation of summable functions of several variables by trigonometric polynomials in the metric of L is determined in terms of Fourier coefficients. We consider functions representable by trigonometric series with certain symmetry of coefficients satisfying a multiple analog of the Sidon–Telyakovskii conditions.     

Brown representability for the dual

Let T be the homotopy category of all spectra. Brown proved that a homological functor H: T ^{o p} → Ab is representable if it takes coproducts to products. That is, the functors [−,h] may be characterised as the homological functors taking coproducts to products. In this article, we will prove the dual. A covariant functor H:T → Ab which takes products to products is representable; it is of the form [h,−]. Oblatum 10-VII-1997 & 23-VII-1997     

On the homogeneous representation of interval graphs

An interval graph G is homogeneously representable if for every vertex v of G there exists an interval representation of G with v corresponding to an end interval. We show that the homogeneous representation of interval graphs is rooted in a deeper property of a class of graphs that we characterize by forbidden configurations.