CiteULike: AbnerCYH's order

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

Marc Tedder — 2008-07-18T17:42:46-00:00

Automata, Languages and Programming (2008), pp. 634-645.

Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures.

Shellable Nonpure Complexes and Posets. II

Anders Bjorner — 2008-05-27T08:00:27-00:00

Vol. 349, No. 10. (October 1997), pp. 3945-3975.

Shellable Nonpure Complexes and Posets. I

Anders Bjorner — 2008-05-27T07:58:17-00:00

Transactions of the American Mathematical Society, Vol. 348, No. 4. (April 1996), pp. 1299-1367.

Combinatorics and Partially Ordered Sets: Dimension Theory (Johns Hopkins Studies in the Mathematical Sciences)

William Trotter — 2008-05-18T16:33:30-00:00

(01 May 1992)

Primarily intended for research mathematicians and computer scientists, Combinatorics and Partially Ordered Sets: Dimension Theory also serves as a useful text for advanced students in either field. William Trotter concentrates on combinatorial topics for finite partially ordered sets, and with dimension theory serving as a unifying theme, research on partially ordered sets or posets is linked to more traditional topics in combinatorial mathematics -- including graph theory, Ramsey theory, probabilistic methods, hypergraphs, algorithms, and computational geometry. The book's most important contribution is to collect, organize, and explain the many theorems on partially ordered sets in a way that makes them available to the widest possible audience. Chapters: Introduction to Dimension • Crowns, Splits, Stacks, Sums and Products • Characterization Problems for Posets, Lattices, Graphs, and Families of Sets • Hypergraph Coloring, Computational Complexity, and Irreducible Posets • Planar Posets and Trees • Planar Graphs, Planar Maps and Convex Polytopes • Probabilistic Methods in Dimension Theory • Interval and Geometric Containment Orders • Greedy Dimension, Back-Tracking, and Depth First Search • Products of Chains of Bounded Length • Large Minimal Realizers

Properties of intersecting families of ordered sets

Ori Einstein — 2008-05-06T09:19:11-00:00

Combinatorica, Vol. 28, No. 1. (30 January 2008), pp. 37-44.

Abstract The first part of this paper deals with families of ordered k-tuples having a common element in different position. A quite general theorem is given and special cases are considered. The second part deals with t families of sets with some intersection properties, and generalizes results by Bollobás, Frankl, Lovász and Füredi to this case.

Geometric Discrepancy: An Illustrated Guide (Algorithms and Combinatorics)

Jiri Matousek — 2008-04-16T02:19:13-00:00

(15 July 1999)

What is the "most uniform" way of distributing n points in the unit square? How big is the "irregularity" necessarily present in any such distribution? Such questions are treated in geometric discrepancy theory. The book is an accessible and lively introduction to this area, with numerous exercises and illustrations. In separate, more specialized parts, it also provides a comprehensive guide to recent research. Including a wide variety of mathematical techniques (from harmonic analysis, combinatorics, algebra etc.) in action on non-trivial examples, the book is suitable for a "special topic" course for early graduates in mathematics and computer science. Besides professional mathematicians, it will be of interest to specialists in fields where a large collection of objects should be "uniformly" represented by a smaller sample (such as high-dimensional numerical integration in computational physics or financial mathematics, efficient divide-and-conquer algorithms in computer science, etc.).

The Complexity of the Partial Order Dimension Problem

Mihalis Yannakakis — 2008-03-31T17:42:26-00:00

SIAM Journal on Algebraic and Discrete Methods, Vol. 3, No. 3. (1982), pp. 351-358.

Representation of an order as union of interval orders

Christian Capelle — 2008-04-01T01:36:35-00:00

Vol. 831 (1994)

We present an practical method to obtain a compact computer memory representation of orders and to compute pairwise comparisons efficiently. The principle of this method is to represent an order P as a union of interval orders P i for which an optimal representation is already known (i.e. a union representation of P [Wes85]). For a directed acyclic graph G = (X, U) representing an order P = (X, <p), the preprocessing time complexity is not better than the transitive closure computation cost. In the worst case, the size of the representation is the same that the size of the transitive closure. However, experimental tests give better results, and comparison with the compression technique of Agrawal & al. [ABJ89] is at the advantage of our method for dense orders.

On the Interplay Between Interval Dimension and Dimension

S Felsner — 2008-04-01T00:57:50-00:00

SIAM Journal on Discrete Mathematics, Vol. 7, No. 1. (1994), pp. 32-40.

Comparability invariance of the fixed point property

B Dreesen — 2008-03-29T11:43:56-00:00

Order, Vol. 2, No. 3. (1985), pp. 269-274.

We show that the fixed point property is comparability invariant for finite ordered sets; that is, if P and Q are finite ordered sets with isomorphic comparability graphs, then P has the fixed point property if and only if Q does. In the process we give a characterization of comparability invariants which can also be used to give shorter proofs of some known results.

Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs

Wen Hsu — 2008-03-26T14:07:41-00:00

SIAM Journal on Computing, Vol. 28, No. 3. (1998), pp. 1004-1020.

Pages 1004-1020,

Efficient reductions among lattice problems

Daniele Micciancio — 2008-03-19T08:12:40-00:00

(2008), pp. 84-93.

Decompositions of two-dimensional simplicial complexes

Masahiro Hachimori — 2008-03-14T19:02:06-00:00

Discrete Mathematics, Vol. 308, No. 11. (6 June 2008), pp. 2307-2312.

We show that the class of Cohen-Macaulay complexes, that of complexes with constructible subdivisions, and that of complexes with shellable subdivisions differ from each other in every dimension d[greater-or-equal, slanted]2. Further, we give a characterization of two-dimensional simplicial complexes with shellable subdivisions, and show also that they are constructible.

Maximal dimensional partially ordered sets I. Hiraguchi's theorem

Kenneth Bogart — 2008-03-14T04:34:59-00:00

Discrete Mathematics, Vol. 5, No. 1. (May 1973), pp. 21-31.

In this paper, I give a new proof of Hiraguchi's Theorem that the dimension of an n-element partially ordered set is at most [frcase1/2n]. The significant feature of the proof is the lemma which states that a partially ordered set has either a cover of rank 0 or a pair of covers with elements of one incomparable with elements of the other.

A recognition algorithm for orders of interval dimension two

Larry Langley — 2008-03-14T04:32:01-00:00

Discrete Applied Mathematics, Vol. 60, No. 1-3. (23 June 1995), pp. 257-266.

From a partially ordered set (X, <) one may construct the collection PS(X) consisting of a collection of subsets of X ordered by inclusion. We show that the interval dimension of X equals the dimension of PS(X) and give an O(n3) algorithm to determine whether X has interval dimension [less-than-or-equals, slant]2 and construct an interval realizer of X.

Partial orders and their convex subsets

Haiko Muller — 2008-03-14T04:31:12-00:00

Discrete Mathematics, Vol. 165-166 (15 March 1997), pp. 507-517.

We introduce some visibility relations between convex subsets of a partial order that are partial orders themselves. As a consequence we obtain a general framework for partial orders providing an interesting coding, and some new characterizations of some known classes of partial orders.

Interval dimension is a comparability invariant

Michel Habib — 2008-03-14T02:08:09-00:00

Discrete Mathematics, Vol. 88, No. 2-3. (19 April 1991), pp. 211-229.

We allow orders (ordered sets) to be infinite. An interval order is an order that does not contain 2+2 as an induced suborder. The interval dimension of an order is the minimum number of interval orders (on the same set) whose intersection is the given order. We show that orders with the same comparability graph have the same interval dimension, answering a question raised by Dagan, Golumbic and Pinter for finite orders. We also obtain the analogous result for some other notions of dimension.

Space Efficient Algorithms for Ordered Tree Comparison

Lusheng Wang — 2008-01-21T20:53:33-00:00

Algorithmica

Abstract In this paper we present techniques to significantly improve the space complexity of several ordered tree comparison algorithms without sacrificing the corresponding time complexity. We present new algorithms for computing the constrained ordered tree edit distance and the alignment of (ordered) trees. The techniques can also be applied to other related problems.

A note on chordal bound graphs and posets

Shin-Ichi Iwai — 2008-01-14T08:00:00-00:00

Discrete Mathematics, Vol. 308, No. 5-6. (28 March 2008), pp. 955-961.

We study relations between induced subgraphs and (n,m)-subposets. Using properties of (n,m)-subposets, we consider a characterization of chordal double bound graphs in terms of forbidden subposets. Furthermore, we deal with properties of a poset whose double bound graph is isomorphic to its upper bound graph or its comparability graph, etc.

Kolmogorov complexities Kmax, Kmin on computable partially ordered sets

Marie Ferbus-Zanda — 2008-01-04T12:39:00-00:00

(2 Jan 2008)

We introduce a machine free mathematical framework to get a natural formalization of some general notions of infinite computation in the context of Kolmogorov complexity. Namely, the classes Max^X\to D_PR and Max^X\to D_Rec of functions X \to D which are pointwise maximum of partial or total computable sequences of functions where D = (D,<) is some computable partially ordered set. The enumeration theorem and the invariance theorem always hold for Max^X\to D_PR, leading to a variant KD;max of Kolmogorov complexity. We characterize the orders D such that the enumeration theorem (resp. the invariance theorem) also holds for Max^X\to D_Rec . It turns out that Max^X\to D_Rec may satisfy the invariance theorem but not the enumeration theorem. Also, when Max^X\to D_Rec satisfies the invariance theorem then the Kolmogorov complexities associated to Max^X\to D_Rec and Max^X\to D_PR are equal (up to a constant). Letting K^D_min = K^D^rev_max, where D^rev is the reverse order, we prove that either K^D_min =_ct K^D_max =_ct K^D (=_ct is equality up to a constant) or K^D_min, K^D_max are <=_ct incomparable and <_ct K^D and >_ct K^0',D. We characterize the orders leading to each case. We also show that K^D_min, K^D_max cannot be both much smaller than K^D at any point. These results are proved in a more general setting with two orders on D, one extending the other.

Partially Complemented Representations of Digraphs

Elias Dahlhaus — 2007-12-26T05:33:38-00:00

Discrete Mathematics & Theoretical Computer Science, Vol. 5, No. 1. (2002), pp. 147-168.

A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent if one can be obtained from the other by a sequence of such operations. We show that given an adjacency-list representation of a digraph G, many fundamental graph algorithms can be carried out on any member G' of G's equivalence class in O(n+m) time, where m is the number of arcs in G, not the number of arcs in G' . This may have advantages when G' is much larger than G. We use this to generalize to digraphs a simple O(n + m log n) algorithm of McConnell and Spinrad for finding the modular decomposition of undirected graphs. A key step is finding the strongly-connected components of a digraph F in G's equivalence class, where F may have ~(m log n) arcs.

P4-trees and substitution decomposition

Jeremy Spinrad — 2007-12-13T08:08:48-00:00

Discrete Applied Mathematics, Vol. 39, No. 3. (11 November 1992), pp. 263-291.

This paper introduces a new data structure called a P4-tree, and uses the data structure as part of an algorithm to find the substitution decomposition of a graph in O(m[alpha](m,n)) time.

An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs

A Ehrenfeucht — 2007-12-12T19:31:12-00:00

Journal of Algorithms, Vol. 16, No. 2. (March 1994), pp. 283-294.

This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O(n2) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition. The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.

Homogeneity vs. Adjacency: generalising some graph decomposition algorithms

Binh — 2007-12-12T18:52:30-00:00

(13 Mar 2006)

In this paper, a new general decomposition theory inspired from modular graph decomposition is presented. Our main result shows that, within this general theory, most of the nice algorithmic tools developed for modular decomposition are still efficient. This theory not only unifies the usual modular decomposition generalisations such as modular decomposition of directed graphs or decomposition of 2-structures, but also star cutsets and bimodular decomposition. Our general framework provides a decomposition algorithm which improves the best known algorithms for bimodular decomposition.

Partition Refinement Techniques: An Interesting Algorithmic Tool Kit

Michel Habib — 2007-12-12T10:19:20-00:00

Int. J. Found. Comput. Sci., Vol. 10, No. 2. (1999), pp. 147-170.

Partition refinement techniques lead to simple and efficient algorithms for various applications: automaton minimization, string sorting . . . and also for algorithms on graphs. A generic algorithm that can be used for all these applications is presented and briefly discussed. Such an approach is interesting in an algorithmic tool kit perspective. New instances of the generic algorithm are presented: O(n + m log n) very simple and practical algorithms for cographs recognition and for modular...

Graph Decompositions and Factorizing Permutations

Christian Capelle — 2007-12-12T10:10:17-00:00

Discrete Mathematics and Theoretical Computer Science, Vol. 5, No. 1. (2002), pp. 55-70.

A factorizing permutation of a given graph is simply a permutation of its vertices of which all decomposition sets are factors. Such a concept appears to play a central role in recent papers dealing with graph decomposition. It is applied here for modular decomposition of directed graphs, and we propose a simple linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided. The approach of using parenthesized factors of a list was first used by Hopcroft and Tarjan for triconnected components search . Our algorithm can be seen as a common generalization of Hsu and Ma for modular decomposition of chordal graphs and Habib, Huchard and Spinrad for inheritance graphs decomposition. It also suggests many new decomposition algorithms for various notions of graph decompositions.

Modular decomposition and transitive orientation

Ross Mcconnell — 2007-12-12T09:05:44-00:00

Discrete Mathematics, Vol. 201, No. 1-3. (28 April 1999), pp. 189-241.

A module of an undirected graph is a set X of nodes such for each node x not in X, either every member of X is adjacent to x, or no member of X is adjacent to x. There is a canonical linear-space representation for the modules of a graph, called the modular decomposition. Closely related to modular decomposition is the transitive orientation problem, which is the problem of assigning a direction to each edge of a graph so that the resulting digraph is transitive. A graph is a comparability graph if such an assignment is possible. We give O(n + m) algorithms for modular decomposition and transitive orientation, where n and m are the number of vertices and edges of the graph. This gives linear time bounds for recognizing permutation graphs, maximum clique and minimum vertex coloring on comparability graphs, and other combinatorial problems on comparability graphs and their complements.

Simple, linear-time modular decomposition

Marc Tedder — 2007-12-12T08:48:43-00:00

(21 Oct 2007)

Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. Despite considerable effort, such an algorithm has remained elusive. The linear-time algorithms to date are impractical and of mainly theoretical interest. In this paper we present the first simple, linear-time algorithm to compute the modular decomposition tree of an undirected graph. The breakthrough comes by combining the best elements of two different approaches to the problem.

Multiple sequence alignment using partial order graphs.

C Lee — 2005-06-30T17:56:12-00:00

Bioinformatics, Vol. 18, No. 3. (March 2002), pp. 452-464.

MOTIVATION: Progressive Multiple Sequence Alignment (MSA) methods depend on reducing an MSA to a linear profile for each alignment step. However, this leads to loss of information needed for accurate alignment, and gap scoring artifacts. RESULTS: We present a graph representation of an MSA that can itself be aligned directly by pairwise dynamic programming, eliminating the need to reduce the MSA to a profile. This enables our algorithm (Partial Order Alignment (POA)) to guarantee that the optimal alignment of each new sequence versus each sequence in the MSA will be considered. Moreover, this algorithm introduces a new edit operator, homologous recombination, important for multidomain sequences. The algorithm has improved speed (linear time complexity) over existing MSA algorithms, enabling construction of massive and complex alignments (e.g. an alignment of 5000 sequences in 4 h on a Pentium II). We demonstrate the utility of this algorithm on a family of multidomain SH2 proteins, and on EST assemblies containing alternative splicing and polymorphism. AVAILABILITY: The partial order alignment program POA is available at http://www.bioinformatics.ucla.edu/poa.

Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions

RH Möhring — 2007-12-04T10:30:47-00:00

Annals of Operations Research, Vol. 4, No. 1. (1 December 1985), pp. 195-225.

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.

Efficient and Practical Algorithms for Sequential Modular Decomposition

Elias Dahlhaus — 2006-07-03T16:08:06-00:00

Journal of Algorithms, Vol. 41, No. 2. (November 2001), pp. 360-387.

A module of an undirected graph G = (V, E) is a set X of vertices that have the same set of neighbors in V\X. The modular decomposition is a unique decomposition of the vertices into nested modules. We give a practical algorithm with an O(n + m[alpha](m, n)) time bound and a variant with a linear time bound.

Algorithmic Aspects of a General Modular Decomposition Theory

Binh-Minh Bui-Xuan — 2007-11-21T16:30:21-00:00

(20 Nov 2007)

A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, the terminology “module” not only captures the classical graph modules but also allows to handle 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan 1994 is generalised and yields a very efficient solution to the associated decomposition problem.

A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension

Michel Habib — 2007-11-21T16:27:20-00:00

Algorithm Theory - SWAT 2004, Vol. 3111 (2004), pp. 187-198.

The first polynomial time algorithm () for modular decomposition appeared in 1972 [8] and since then there have been incremental improvements, eventually resulting in linear-time algorithms [22,7,23,9]. Although having optimal time complexity these algorithms are quite complicated and difficult to implement. In this paper we present an easily implementable linear-time algorithm for modular decomposition. This algorithm uses the notion of factorizing permutation and a new data-structure, the Ordered Chain Partitions.

Entropy of capacities on lattices and set systems

Aoi Honda — 2007-11-14T08:37:40-00:00

(13 Nov 2007)

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.

No Sorting? Better Searching!

Gianni Franceschini — 2007-11-08T17:09:15-00:00

(2004), pp. 491-498.

A Proof of Dilworth's Chain Decomposition Theorem

Fred Galvin — 2007-11-08T11:10:08-00:00

The American Mathematical Monthly, Vol. 101, No. 4. (1994), pp. 352-353.

The Discrete Fundamental Group of the Order Complex of $B_n$

Hélène Barcelo — 2007-11-07T12:25:51-00:00

(6 Nov 2007)

A few years ago Kramer and Laubenbacher introduced a discrete notion of homotopy for simplicial complexes. In this paper, we compute the discrete fundamental group of the order complex of the Boolean lattice. As it turns out, it is equivalent to computing the discrete homotopy group of the 1-skeleton of the permutahedron. To compute this group we introduce combinatorial techniques that we believe will be helpful in computing discrete fundamental groups of other polytopes. More precisely, we use the language of words, over the alphabet of simple transpositions, to obtain conditions that are necessary and sufficient to characterize the equivalence classes of cycles. The proof requires only simple combinatorial arguments. As a corollary, we also obtain a combinatorial proof of the fact that the first Betti number of the complement of the 3-equal arrangement is equal to $2^n-3(n^2-5n+8)-1.$ This formula was originally obtained by Björner and Welker in 1995.

Should Tables Be Sorted?

Andrew Yao — 2007-02-07T06:23:11-00:00

J. ACM, Vol. 28, No. 3. (July 1981), pp. 615-628.

Every decision tree has an influential variable

Ryan O'Donnell — 2007-10-23T09:19:47-00:00

(2005), pp. 31-39.

Products and Help Bits in Decision Trees

Noam Nisan — 2007-10-23T09:15:36-00:00

SIAM Journal on Computing, Vol. 28, No. 3. (1998), pp. 1035-1050.

Pages 1035-1050,

2-Dimension from the Topological Viewpoint

Jonathan Barmak — 2007-10-23T08:12:30-00:00

Order, Vol. 24, No. 1. (17 February 2007), pp. 49-58.

Abstract In this paper we study the 2-dimension of a finite poset from the topological point of view. We use homotopy theory of finite topological spaces and the concept of a beat point to improve the classical results on 2-dimension, giving a more complete answer to the problem of all possible 2-dimensions of an n-point poset.

Fractional dimension of partial orders

Graham Brightwell — 2007-10-23T03:31:33-00:00

Order, Vol. 9, No. 2. (21 June 1992), pp. 139-158.

Given a partially ordered setP=(X, =), a collection of linear extensions L1,L2,...,Lr is arealizer if, for every incomparable pair of elementsx andy, we havexy in someLi (andyx in someLj). For a positive integerk, we call a multiset L1,L2,...,Lt ak-fold realizer if for every incomparable pairx andy we havexy in at leastk of theLi's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask?8. We prove various results about the fractional dimension of a poset.

On the Complexity of Partial Order Properties

Stefan Felsner — 2007-10-23T03:27:23-00:00

Order, Vol. 17, No. 2. (1 June 2000), pp. 179-193.

The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k = n2 / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.

Combinatorial representation and convex dimension of convex geometries

Paul Edelman — 2007-10-23T03:26:09-00:00

Order, Vol. 5, No. 1. (1 March 1988), pp. 23-32.

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.

Every poset has a good comparison

Jeff Kahn — 2007-10-19T14:02:59-00:00

(1984), pp. 299-301.

Planar graphs and poset dimension

Walter Schnyder — 2005-11-28T13:54:05-00:00

Order, Vol. 5, No. 4. (1989), pp. 323-343.

Given a graph $G=(V, E)$, we can form its incidence poset $<_G$ by setting $a<_G\,b$ if and only if $a$ is a vertex and $b$ is an edge with $a$ one of its endpoints. One can then ask how properties of $G$ are reflected in properties of $<_G$. The striking result proved in this paper is that the order-dimension of $<_G$ is at most 3 if and only if $G$ is planar. In proving this result, the author develops various tools for handling representations of planar graphs which may be useful in other contexts. The main theorem implies several other known results concerning planar graphs. For instance, one obtains proofs that every planar graph has arboricity at most 3, and that every planar graph has a straight-line representation.

Poset Topology: Tools and Applications

Michelle Wachs — 2006-02-13T19:05:40-00:00

(11 Feb 2006)

These lecture notes for the IAS/Park City Graduate Summer School in Geometric Combinatorics (July 2004) provide an overview of poset topology. These notes include introductory material, as well as recent developments and open problems. Some of the topics covered are: subspace arrangements, graph complexes, group actions on poset homology, shellability, recursive techniques, and fiber theorems.

Lattices and Ordered Algebraic Structures (Universitext)

TS Blyth — 2007-10-17T07:18:06-00:00

(22 March 2005)

Lattices and Ordered Algebraic Structures provides a lucid and concise introduction to the basic results concerning the notion of an order. Although as a whole it is mainly intended for beginning postgraduates, the prerequisities are minimal and selected parts can profitably be used to broaden the horizon of the advanced undergraduate. The treatment is modern, with a slant towards recent developments in the theory of residuated lattices and ordered regular semigroups. Topics covered include: residuated mappings; Galois connections; modular, distributive, and complemented lattices; Boolean algebras; pseudocomplemented lattices; Stone algebras; Heyting algebras; ordered groups; lattice-ordered groups; representable groups; Archimedean ordered structures; ordered semigroups; naturally ordered regular and inverse Dubreil-Jacotin semigroups. Featuring material that has been hitherto available only in research articles, and an account of the range of applications of the theory, there are also many illustrative examples and numerous exercises throughout, making it ideal for use as a course text, or as a basic introduction to the field for researchers in mathematics, logic and computer science.

A combinatorial approach to correlation inequalities

Graham Brightwell — 2007-10-09T07:12:37-00:00

Discrete Mathematics, Vol. 257, No. 2-3. (28 November 2002), pp. 311-327.

In this paper, we initiate a combinatorial approach to proving correlation inequalities for finite partially ordered sets. A new proof is provided for the strong form of the XYZ theorem, due to Fishburn. We also use our method to give a new proof of a related correlation result of Shepp involving two sets of relations. Our arguments are entirely combinatorial in the sense that they do not make use of the Ahlswede/Daykin theorem or any of its relatives.

On the Comparison Cost of Partial Orders

Joseph Culberson — 2007-10-09T01:12:42-00:00

A great deal of effort has been directed towards determining the minimum number of binary comparisons sufficient to produce various partial orders given some partial order. For example, the sorting problem considers the minimum number of comparisons sufficient to construct a total order starting from n elements. The merging problem considers the minimum number of comparisons sufficient to construct a total order from two total orders. The searching problem can be seen as a special case of the...