DISCRETE FUNCTORS

Abstract

The concept of a T-discrete object is a generalization of the notion of discrete spaces in concrete categories. In this paper. T-discrete objects are used to define discrete functors. Characterizations of discrete functors are given and their relation to other important functors are studied. A faithful functor T: A → X is discrete iff the full subcategory B of A consisting of all T-discrete objects is (X-iso)-coreflective in A. It follows that the existence of bicoreflective subcategories is equivalent to the existence of suitable discrete functors. Finally, necessary and sufficient conditions are found such that for a given functor T: A → X, the full subcategory B of A consisting of all T-discrete A-objects is monocoreflective in A.     

ALGEBRAIC HULLS OF ADJOINT FUNCTORS AS INJECTIVE HULLS

Abstract

For each adjoint functor U: A → X where X is an (?, M)-category having enough ?-projectives, we construct an (?, M)-algebraic hull E: (A, U) → (Â, Û), i.e., (Â, Û) is (epsiv; M)-algebraic and E has a certain denseness property. We show that there is a conglomerate of functors over X with respect to which the (? M)-algebraic categories are exactly the injective objects and characterize (? M)-algebraic hulls as injective hulls.     

ORDER EXTENSIONS AS ADJOINT FUNCTORS

Abstract

A standard extension (resp. standard completion) is a function Z assigning to each poset P a (closure) system ZP of subsets such that x ? y iff x belongs to every Z ε ZP with y ε Z. A poset P is Z -complete if each Z ε 2P has a join in P. A map f: P → P′ is Z—continuous if f^?1 [Z′] ε ZP for all Z′ ε ZP′, and a Z—morphism if, in addition, for all Z ε ZP there is a least Z′ ε ZP′ with f[Z] ? Z′. The standard extension Z is compositive if every map f: P → P′ with {x ε P: f(x) ? y′} ε ZP for all y′ ε P′ is Z -continuous. We show that any compositive standard extension Z is the object part of a reflector from IP_Z, the category of posets and Z -morphisms, to IR_Z, the category of Z -complete posets and residuated maps. In case of a standard completion Z, every Z -continuous map is a Z -morphism, and IR2 is simply the category of complete lattices and join—preserving maps. Defining in a suitable way so-called Z -embeddings and morphisms between them, we obtain for arbitrary standard extensions Z an adjunction between IP_Z and the category of Z -embeddings. Many related adjunctions, equivalences and dualities are studied and compared with each other. Suitable specializations of the function 2 provide a broad spectrum of old and new applications.     

SOME TOPOLOGICAL FUNCTORS ARISING FROM ALGEBRAIC GEOMETRY

Abstract

A synthesis of notions arising from algebraic geometry, especially those developed by Verdier in Séminaire de Géométric Algébrique IV, and the notion of topological functor (in the sense of G.C.L. Brümmer and R.-E. Hoffmann) is made. In particular, Grothendieck topologies are shown to be topological over the category of categories with pullbacks and pullback preserving functors, and consequences derived.     

Set maps, umbral calculus, and the chromatic polynomial

Some important properties of the chromatic polynomial also hold for any polynomial set map satisfying

     

EPIREFLECTIONS VERSUS BIREFLECTIONS FOR TOPOLOGICAL FUNCTORS

Abstract

In this paper it is proved that if T: A → X is a topological functor satisfying certain conditions, then there is a Galois Connection between the class of bireflective subcategories of A and the class of epireflective subcategories of A that are not bireflective and that are contained in the subcategory of separated objects of A. In general such a correspondence is not bijective.     

NETS AND GRAPHS AS PINAL COMPLETIONS AND THE RELATIONS BETWEEN THEM

Abstract

Nets and graphs, both used in Computer Science, are studied from a categorical point of view. It is shown that they may be constructed via final completions of very simple small concrete categories and that their nice properties, namely to form topological categories which are quasitopoi with concrete powers such that products of final maps are final, depend on this fact. Furthermore, the relations between them can be described by means of adjoint functors.     

Equiarboreal graphs

A graphX is said to beequiarboreal if the number of spanning trees containing a specified edge inX is independent of the choice of edge. We prove that any graph which is a colour class in an association scheme (and thus any distance regular graph) is equiarboreal. We note that a connected equiarboreal graph withM edges andn vertices has edge-connectivity at leastM/(n−1).     

When is a natural duality ‘good’?

Building on the most current work in the theory of natural dualities, we continue the study of strong dualities for the quasi-variety generated by a finite algebra. We investigate ten different versions of what we would like to mean by a good duality. Each version concerns, among other things, a specific restriction on the type of the structures in the dual category which insures that the dual structures will in a useful sense be simple. Through each investigation we seek a theorem characterizing, in terms of finitely verifiable conditions, those finite algebras generating a quasi-variety which admits a strong duality meeting the given restrictions. Our study includes a careful treatment of coproducts, logarithmic dualities and strong dualities by various unary structures.Dedicated to the memory of Alan DayPresented by J. Sichler.Research supported by a 1992 ARC Grant (Davey).     

Structural entailment

We give a number of characterizations of structural entailment. In particular, we show that an alter ego structurally entails an algebraic relation s on a finite algebra if and only if s can be obtained via a local construct from . We show, via a range of applications, that, whereas entailment is important in the study of dualisability, structural entailment is important in the study of full and strong dualisability. We also give an application to the transfer of strong dualities that connects this paper to our earlier paper [9] on full versus strong duality. Received June 27, 2003; accepted in final form May 12, 2005.     

Strong duality of finite algebras that generate the same quasivariety

We show that if two finite algebras generate the same quasivariety and one is strongly dualizable, then the other is also strongly dualizable.     

Sign patterns allowing nilpotence of index 3

Suppose P is a property referring to a real matrix. We say that a sign pattern A allows P if there exists at least one matrix with the same sign pattern as A that has the property P. In this paper, we study sign patterns allowing nilpotence of index 3. Four methods for constructing sign patterns that allow nilpotence of index 3 are obtained. All tree sign patterns that allow nilpotence of index 3 are characterized. Sign patterns of order 3 that allow nilpotence are identified.     

Exponents of 2-coloring of symmetric digraphs

A 2-coloring (G₁,G₂) of a digraph is 2-primitive if there exist nonnegative integers h and k with h+k>0 such that for each ordered pair (u,v) of vertices there exists an (h,k)-walk in (G₁,G₂) from u to v. The exponent of (G₁,G₂) is the minimum value of h+k taken over all such h and k. In this paper, we consider 2-colorings of strongly connected symmetric digraphs with loops, establish necessary and sufficient conditions for these to be 2-primitive and determine an upper bound on their exponents. We also characterize the 2-colored digraphs that attain the upper bound and the exponent set for this family of digraphs on n vertices.     

Minimum rank problems

A graph describes the zero-nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303-316, C.R. Johnson, A. Leal Duarte, The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra 46 (1999) 139-144], trees allowing loops [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness. Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl. 418 (2006) 389-415], and directed trees allowing loops [F. Barioli, S. Fallat, D. Hershkowitz, H.T. Hall, L. Hogben, H. van der Holst, B. Shader, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra 18 (2000) 126-145]. We survey these results from a unified perspective and solve the minimum rank problem for simple directed trees.     

Generalized characteristic polynomials of graph bundles

In this paper, we find computational formulae for generalized characteristic polynomials of graph bundles. We show that the number of spanning trees in a graph is the partial derivative (at (0,1)) of the generalized characteristic polynomial of the graph. Since the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, consequently, the Bartholdi zeta function of a graph bundle can be computed by using our computational formulae.     

Transitive parabolic unitals in semifield planes

Every semifield plane with spread in PG(3,K), where K is a field admitting a quadratic extension K⁺, is shown to admit a transitive parabolic unital. The author gratefully acknowledges helpful comments of the referee in the writing of this article.     

The weighted complexity and the determinant functions of graphs

The complexity of a graph can be obtained as a derivative of a variation of the zeta function [S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B 74 (1998) 408-410] or a partial derivative of its generalized characteristic polynomial evaluated at a point [D. Kim, H.K. Kim, J. Lee, Generalized characteristic polynomials of graph bundles, Linear Algebra Appl. 429 (4) (2008) 688-697]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [H. Mizuno, I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory Ser. B 89 (2003) 17-26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the complexity from a variation of the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

Enlargements of filtrations and path decompositions at non stopping times

Azéma associated with an honest time L the supermartingale and established some of its important properties. This supermartingale plays a central role in the general theory of stochastic processes and in particular in the theory of progressive enlargements of filtrations. In this paper, we shall give an additive characterization for these supermartingales, which in turn will naturally provide many examples of enlargements of filtrations. We combine this characterization with some arguments from both initial and progressive enlargements of filtrations to establish some path decomposition results, closely related to or reminiscent of Williams' path decomposition results. In particular, some of the fragments of the paths in our decompositions end or start with a new family of random times which are not stopping times, nor honest times.