Morphismen von Funktoren

Morphisms of functors or natural transformations between functors of different variance are investigated. In order to be able to define the usual compositions of morphisms of functors in this case, too, and to formulate the corresponding results smoothly, one is forced to define a morphism of functors essentially as a mapping from one category to another and not as usual as a mapping from the class of objects of one category to another category. Two new invariants of a morphism of functors, the parity and the exponent, arise in a natural way and are the main tools in proving all the results.

---

---

Research partially supported by the Air Force Office of Scientific Research, Office of Aerospace Research, United States Air Force, under AFOSR Grant No. 68-1572.     

Softness of hypercoherences and MALL full completeness

We prove a full completeness theorem for multiplicative–additive linear logic (i.e. MALL) using a double gluing construction applied to Ehrhard’s *-autonomous category of hypercoherences. This is the first non-game-theoretic full completeness theorem for this fragment. Our main result is that every dinatural transformation between definable functors arises from the denotation of a cut-free MALL proof.Our proof consists of three steps. We show:

• •Dinatural transformations on this category satisfy Joyal’s softness property for products and coproducts.
• •Softness, together with multiplicative full completeness, guarantees that every dinatural transformation corresponds to a Girard MALL proof-structure.
• •The proof-structure associated with any dinatural transformation is a MALL proof-net, hence a denotation of a proof. This last step involves a detailed study of cycles in additive proof-structures.

The second step is a completely general result, while the third step relies on the concrete structure of a double gluing construction over hypercoherences.     

Unicity of Enrichment over Cat or Gpd

Enrichment of ordinary monads over Cat or Gpd is fundamental to Max Kelly’s unified theory of coherence for categories with structure. So here, we investigate existence and unicity of enrichments of ordinary functors, natural transformations, and hence also monads, over Cat and Gpd. We show that every ordinary natural transformation between 2-functors whose domain 2-category has either tensors or cotensors with the arrow category is 2-natural. We use that to prove that an ordinary monad, or endofunctor, on such a 2-category has at most one enrichment over Cat or Gpd. We also describe a monad on Cat that has no enrichment. So enrichment over Cat is a non-trivial property of a monad rather than a structure that is additional to it. Finally, we present an example, due to Kelly, of V other than Cat or Gpd and an ordinary monad for which more than one enrichment over V exists, showing that our main theorem is specific to Cat and Gpd.     

On mixed block graphs

A mixed complete graph is obtained from a directed cycle of length at least three by adding all the possible arcs between any non-adjacent vertices of the underlying cycle. A mixed block graph is a strongly connected directed graph whose blocks are mixed complete graphs. In this paper, we give the inverse of the distance matrix of the mixed block graph.     

s-homotopy for finite graphs

We introduce the notion of “s-dismantlability” which will give in the category of finite graphs an analogue of formal deformations defining the simple-homotopy type in the category of finite simplicial complexes. More precisely, s-dismantlability allows us to define an equivalence relation whose equivalence classes are called “s-homotopy types” and we get a correspondence between s-homotopy types in the category of graphs and simple-homotopy types in the category of simplicial complexes by the way of classical functors between these two categories (theorem 3.6). Next, we relate these results to similar results obtained by Barmak and Minian (2006) within the framework of posets (theorem 4.2).     

Representation of proofs by colored graphs and the hadwiger conjecture

A tinted graph is a graph whose arcs are colored with certain colors. A colored graph is a graph whose vertices are colored with certain colors. If M is the set of tinted (or colored tinted) graphs of order k and G is a tinted (or colored tinted) graph, then we shall say that G is M-regular (or M-regularly colored) if all its subgraphs of order k belong to M. We shall show how, for any formula p of the first-order predicate calculus, to construct a finite set B_p of tinted graphs of order 3 and a finite set C_p of colored tinted graphs of order 2 such that ¦-p if and only if there exists a B_p-regular tinted graph not admitting a C_p-regular coloring. Hadwiger's conjecture (HC) is as follows: If no subgraph of a graph without loops G is contractible to a complete graph of order n, then the vertices of G can be colored in n–1 colors such that neighboring vertices are colored with different colors. We construct a formula X of the first-order predicate calculus such that HC is equivalent with X. Thus, HC reduces to HC₁: if all subgraphs of order 3 of the tinted graph G belong to B_X, then G is C_X-regularly colorable. Here B_X and C_X are specific finite sets of tinted graphs of order 3 and colored tinted graphs of order 2, respectively.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 209–216, 1979.     

Categorical principles,techniques and results for high-level-replacement systems in computer science

The aim of this paper is to give an introduction how to use categorical methods in a specific field of computer science: The field of high-level-replacement systems has its roots in the well-established theories of formal languages, term rewriting, Petri nets, and graph grammars playing a fundamental role in computer science. More precisely, it is a generalization of the algebraic approach to graph grammars which is based on gluing constructions for graphs defined as pushouts in the category of graphs. The categorical theory of high-level-replacement systems is suitable for the dynamic handling of a large variety of high-level structures in computer science including different kinds of graphs and algebraic specifications. In this paper we discuss the basic principles and techniques from category theory applied in the field of high-level-replacement systems and present some basic results together with the corresponding categorical proof techniques.     

Edge-swapping algorithms for the minimum fundamental cycle basis problem

We consider the problem of finding a fundamental cycle basis with minimum total cost in an undirected graph. This problem is NP-hard and has several interesting applications. Since fundamental cycle bases correspond to spanning trees, we propose a local search algorithm, a tabu search and variable neighborhood search in which edge swaps are iteratively applied to a current spanning tree. We also present a mixed integer programming formulation of the problem whose linear relaxation yields tighter lower bounds than other known formulations. Computational results obtained with our algorithms are compared with those from the best available constructive heuristic on several types of graphs. This article extends the conference paper (Amaldi et al. 2004).     

Spectral properties of complex unit gain graphs

A complex unit gain graph is a graph where each orientation of an edge is given a complex unit, which is the inverse of the complex unit assigned to the opposite orientation. We extend some fundamental concepts from spectral graph theory to complex unit gain graphs. We define the adjacency, incidence and Laplacian matrices, and study each of them. The main results of the paper are eigenvalue bounds for the adjacency and Laplacian matrices.     

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.     

Equitable partitions into matchings and coverings in mixed graphs

Matchings and coverings are central topics in graph theory. The close relationship between these two has been key to many fundamental algorithmic and polyhedral results. For mixed graphs, the notion of matching forest was proposed as a common generalization of matchings and branchings.In this paper, we propose the notion of mixed edge cover as a covering counterpart of matching forest, and extend the matching–covering framework to mixed graphs. While algorithmic and polyhedral results extend fairly easily, partition problems are considerably more difficult in the mixed case. We address the problems of partitioning a mixed graph into matching forests or mixed edge covers, so that all parts are equal with respect to some criterion, such as edge/arc numbers or total sizes. Moreover, we provide the best possible multicriteria equalization.     

Mixed unit interval graphs

The class of intersection graphs of unit intervals of the real line whose ends may be open or closed is a strict superclass of the well-known class of unit interval graphs. We pose a conjecture concerning characterizations of such mixed unit interval graphs, verify parts of it in general, and prove it completely for diamond-free graphs. In particular, we characterize diamond-free mixed unit interval graphs by means of an infinite family of forbidden induced subgraphs, and we show that a diamond-free graph is mixed unit interval if and only if it has intersection representations using unit intervals such that all ends of the intervals are integral.     

Graph transformations preserving the stability number

We analyse the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number.     

On the Dimension of Posets with Cover Graphs of Treewidth 2

In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276.     

Splitting criteria for homotopy functors of spectra

We explore the interaction between the Taylor tower and cotower, as defined in deriving calculus with cotriples and dual calculus for functors to spectra of functors of spectra. This leads to new splitting criteria which generalize the results in dual calculus for functors to spectra.

     

Equistable graphs

An equistable graph is a graph for which the incidence vectors of the maximal stable sets are the 0–1 solutions of a linear equation. A necessary condition and a sufficient condition for equistability are given. They are used to characterize the equistability of various classes of perfect graphs, outerplanar graphs, and pseudothreshold graphs. Some classes of equistable graphs are shown to be closed under graph substitution.     

Partial inversion for linear systems and partial closure of independence graphs

We introduce and study a calculus for real-valued square matrices, called partial inversion, and an associated calculus for binary square matrices. The first, applied to systems of recursive linear equations, generates new sets of parameters for different types of statistical joint response models. The corresponding generating graphs are directed and acyclic. The second calculus, applied to matrix representations of independence graphs, gives chain graphs induced by such a generating graph. Chain graphs are more complex independence graphs associated with recursive joint response models. Missing edges in independence graphs coincide with structurally zero parameters in linear systems. A wide range of consequences of an assumed independence structure can be derived by partial closure, but computationally efficient algorithms still need to be developed for applications to very large graphs. AMS subject classification (2000) 00A71, 15A09, 15A23, 05C99, 62H99, 62J05     

On the reconstruction of graph invariants

The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the U-polynomial, the universal edge elimination polynomial ξ and the colored versions of the latter two are reconstructible.We also present a method of reconstructing boolean graph invariants, or in other words, proving recognizability of graph properties (of colored or uncolored graphs), using first order logic.     

Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.     

Chromatic polynomial, q-binomial counting and colored Jones function

We define a q-chromatic function and q-dichromate on graphs and compare it with existing graph functions. Then we study in more detail the class of general chordal graphs. This is partly motivated by the graph isomorphism problem. Finally we relate the q-chromatic function to the colored Jones function of knots. This leads to a curious expression of the colored Jones function of a knot diagram K as a chromatic operator applied to a power series whose coefficients are linear combinations of long chord diagrams. Chromatic operators are directly related to weight systems by the work of Chmutov, Duzhin, Lando and Noble, Welsh.