A constructive approach to the finite congruence lattice representation problem

A finite lattice is representable if it is isomorphic to the congruence lattice of a finite algebra. In this paper, we develop methods by which we can construct new representable lattices from known ones. The techniques we employ are sufficient to show that every finite lattice which contains no three element antichains is representable. We then show that if an order polynomially complete lattice is representable then so is every one of its diagonal subdirect powers. Received August 30, 1999; accepted in final form November 29, 1999.     

Ideals of Graph Homomorphisms

In combinatorial commutative algebra and algebraic statistics many toric ideals are constructed from graphs. Keeping the categorical structure of graphs in mind we give previous results a more functorial context and generalize them by introducing the ideals of graph homomorphisms. For this new class of ideals we investigate how the topology of the graphs influences the algebraic properties. We describe explicit Gröbner bases for several classes, generalizing results by Hibi, Sturmfels, and Sullivant. One of our main tools is the toric fiber product, and we employ results by Engström, Kahle, and Sullivant. The lattice polytopes defined by our ideals include important classes in optimization theory, as the stable set polytopes.     

Graphs and their associated inverse semigroups

Directed graphs have long been used to gain an understanding of the structure of semigroups, and recently the structure of directed graph semigroups has been investigated resulting in a characterization theorem and an analog of Frucht’s Theorem. We investigate two inverse semigroups defined over undirected graphs constructed from the notions of subgraph and vertex set induced subgraph. We characterize the structure of the semilattice of idempotents and lattice of ideals of these inverse semigroups. We prove a characterization theorem that states that every graph has a unique associated inverse semigroup up to isomorphism allowing for an algebraic restatement of the Edge Reconstruction Conjecture.     

Ring graphs and complete intersection toric ideals

We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Gröbner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Gröbner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation.     

The automorphism group of the universa distributive lattice

We describe the normal subgroup lattice of the automorphism groups of the countable universal homogeneous distributive lattice and of the countable atomless generalized Boolean lattice. Also, we show that subgroups of these automorphism groups of index less than lie between the pointwise and the setwise stabilizer of a finite set. Received March 8, 1999; accepted in final form September 16, 1999.     

Schnyder Woods and Orthogonal Surfaces

In this paper we study connections between planar graphs, Schnyder woods, and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and the dimension theory of orders. Orthogonal surfaces explain connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says, that the face lattice of a 3-polytope minus one face has order dimension three. Our proof yields a linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondence with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder’s face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.     

Gibbs partitions: The convergent case

We study Gibbs partitions that typically form a unique giant component. The remainder is shown to converge in total variation toward a Boltzmann‐distributed limit structure. We demonstrate how this setting encompasses arbitrary weighted assemblies of tree‐like combinatorial structures. As an application, we establish smooth growth along lattices for small block‐stable classes of graphs. Random graphs with n vertices from such classes are shown to form a giant connected component. The small fragments may converge toward different Poisson Boltzmann limit graphs, depending along which lattice we let n tend to infinity. Since proper addable minor‐closed classes of graphs belong to the more general family of small block‐stable classes, this recovers and generalizes results by McDiarmid (2009).     

Duplication of directed graphs and exponential blow up of proofs

We develop a combinatorial model to study the evolution of graphs underlying proofs during the process of cut elimination. Proofs are two-dimensional objects and differences in the behavior of their cut elimination can often be accounted for by differences in their two-dimensional structure. Our purpose is to determine geometrical conditions on the graphs of proofs to explain the expansion of the size of proofs after cut elimination. We will be concerned with exponential expansion and we give upper and lower bounds which depend on the geometry of the graphs. The lower bound is computed passing through the notion of universal covering for directed graphs.

In this paper we present ground material for the study of cut elimination and structure of proofs in purely combinatorial terms. We develop a theory of duplication for directed graphs and derive results on graphs of proofs as corollaries.     

Entropic measure of the order-disorder character in lattice systems in the representation of coordination Cayley tree graphs

We systematically expound the infodynamical method for analyzing lattice and grid systems. We establish the logic and algorithm for mapping given objects to coordination Cayley tree graphs and present their main properties. Tree graphs of grid systems are complicated objects, and the principle of cluster-type simplicial decomposition can be used to study them. Based on a simplicial decomposition, we construct the enumerating structures, from which we construct entropy-type functionals. We pose the percolation problem on Cayley tree graphs in a nonconventional sense, which may be considered for both enumerating structures and their entropies. The corresponding entropy percolational dependences and their critical indices can be considered sufficiently universal measures of order in lattice systems. The simpliciality also implies an analogy with the fractality principle. We introduce three types of fractal characteristics and give analytic expressions for fractal dimensions for the tangential and streamer representations and for the Mandelbrot shell.     

Graph algebras and graph varieties

Graph algebras establish a connection between graphs (i.e. binary relations) and universal algebras. A structure theorem of Birkhoff-type is given which characterizes graph varieties, i.e. classes of graphs which can be defined by identities for their corresponding graph algebras: A class of finite directed graphs without multiple edges is a graph variety iff it is closed with respect to finite restricted pointed subproducts and isomorphic copies. Several applications are given, e.g., every loopless finite directed graph is an induced subgraph of a direct power of a graph with three vertices. Graphs with bounded chromatic number or density form graph varieties characterizable by identities of special kind.Presented by R. W. Quackenbush.     

Complexity of quasivariety lattices for varieties of differential groupoids. II

We continue the study of the lattice of quasivarieties of differential groupoids. We suggest a method for constructing differential groupoids from graphs. We prove that, for every variety of differential groupoids, the cardinality of the lattice of subquasivarieties is either finite or equal to 2 ^ω .     

Universal deformation rings and cyclic blocks

In this paper we determine the universal deformation rings of certain modular representations of finite groups which belong to cyclic blocks. The representations we consider are those for which every endomorphism is stably equivalent to multiplication by a scalar. We then apply our results to study the counterparts for universal deformation rings of conjectures about embedding problems in Galois theory. Received July 19, 1999 / Revised May 13, 2000 / Published online October 30, 2000     

Covering theory for complexes of groups

We develop an explicit covering theory for complexes of groups, parallel to that developed for graphs of groups by Bass. Given a covering of developable complexes of groups, we construct the induced monomorphism of fundamental groups and isometry of universal covers. We characterize faithful complexes of groups and prove a conjugacy theorem for groups acting freely on polyhedral complexes. We also define an equivalence relation on coverings of complexes of groups, which allows us to construct a bijection between such equivalence classes, and subgroups or overgroups of a fixed lattice Γ in the automorphism group of a locally finite polyhedral complex X.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Partial Characterizations of 1‐Perfectly Orientable Graphs

We study the class of 1‐perfectly orientable graphs, that is, graphs having an orientation in which every out‐neighborhood induces a tournament. 1‐perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1‐perfectly orientable graphs. In particular, we (i) give a characterization of 1‐perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1‐perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1‐perfectly orientable graphs, and (iv) characterize the class of 1‐perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1‐perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.     

Some loose ends on unbounded order convergence

The notion of almost everywhere convergence has been generalized to vector lattices as unbounded order convergence, which proves to be a very useful tool in the theory of vector and Banach lattices. In this short note, we establish some new results on unbounded order convergence that tie up some loose ends. In particular, we show that every norm bounded positive increasing net in an order continuous Banach lattice is uo-Cauchy and that every uo-Cauchy net in an order continuous Banach lattice has a uo-limit in the universal completion.     

A characterization of 3-nets

Laskar introduced 3-nets as a 3 dimensional analogue to Bruck's notion of net. Affine 3-spaces are an example of 3-nets, and cubic lattice graphs provide another example. Freeman introduced and Laskar extended a class of examples of 3-nets, here called Freeman-Laskar 3-nets. We show that every finite 3-net is either a cubic lattice 3-net or a Freeman-Laskar 3-net. We also show that every infinite 3-net either is a cubic lattice 3-net or arises from a vector space over a skew field.     

整数规划中的正则分解

In this paper, we study the problem of regular decomposition in integer programming. We apply the radical of binomial ideal and universal Gr¨obner bases to get the regular decomposition forms of a finite integer lattice point set. We indicate the relationship between state polytope and regular decompositions, i.e., an edge of state polytope corresponds to a binomial which decides one of regular decomposition forms of a finite integer lattice point set.