DIMACS DREI '99
Week 3 Topic: Graphs, Posets, and Algorithms
August 2 - 6, 1999

Abstracts

James Abello, AT&T Research

Massive Multi-digraphs
Joint work with A. Buschbaum, S.Krishnan, P. Pardalos,
M. Resende, A. Ucko, J. Westbrook and S. Sudarsky

A variety of massive data sets exhibit an underlying structure that can be modeled as dynamic weighted multi-digraphs. Their sizes range from tens of gigabytes to terabytes. The sheer volume of these graphs brings with it an interesting series of computational and visualization challenges. We will discuss external memory algorithms for connectivity, minimum spanning trees and maximal matchings together with heuristics for quasiclique finding and diameter computations. From the visualization store we will describe an external memory hierarchy that allow us to use computer graphics techniques like dynamic visibility to provide navigation control. We will present experimental results with graphs having on the order of 200 million vertices and we will point out some mathematical problems that have surfaced along the way.

#### Distance-k Coloring Planar Graphs

For a planar graph G, we derive a sharp upper bound for the inductiveness of G^2, and hence an upper bound for the number of colors needed to vertex color G^2. Moreover, we show that for general k, the chromatic number and the inductiveness of G^k is Theta (Delta ^{\lfloor k/2 \rfloor }), where Delta is the maximum degree of G.
Helene Barcelo, Arizona State University

#### A new combinatorial invariant for geometric lattices

A new invariant is introduced and studied for flag complexes of buildings of finite type. Originally, this invariant was defined by R. Laubenbacher for simplicial complexes, in the context of discrete models for influence flow in information and decision networks. These invariants exist in all dimensions up to the dimension of the top homology of the flag complex. They behave well under join of simplicial complexes. The talk will focus on presenting many of the open problems.
Kenneth P. Bogart, Dartmouth College

#### The Combinatorics of Trapezoid Orders

In this talk we will survey the classification of Trapezoid orders with respect to the properties of being unit, proper, parallelogram, and triangle orders and the various combinations thereof. Most of these classes of orders contain all interval orders and thus have unbounded dimension. However the unit parallelogram orders are orders of semiorder dimension two and thus have dimension at most six. We give a construction of a unit parallelogram order of dimension 4.
Eva Czabarka, University of South Carolina

#### A dynamic programming algorithm for optimizing production DNA sequencing

In recent years quantitative technologies have taken on enormous importance for molecular biology. One of the most fundamental problems facing biologists today is sequencing the Human Genome entirely. According to the latest DOE estimates, achieving the current goal of sequencing the entire Human Genome by 2003 will, according to the latest DOE estimates, require a two- to threefold improvement over current technologies. David Torney and Allon Percus have developed appropriate models and simple algorithms for optimized DNA sequencing. They work could, based on preliminary result, lead to an efficiency gain of 25% over current methods. We will discuss a polynomial time dynamic algorithm, which solves the problem for their single-strand DNA-model, and the (full) double strand model, for which the problem is still unsolved.
Dwight Duffus, Emory University

#### Maximal Chains and Antichains in Distributive Lattices

There are several well known results and conjectures involving maximal antichains and chains in Boolean lattices. Some of the most interesting involve minimum and maximum sizes of sets guaranteed to intersect all maximal chains or all maximal antichains. For instance, how large must a subset of the Boolean lattice of subsets of an n-set be in order to meet every maximal antichain? That is, what is the minimum size of a so-called "fibre"? We shall present some old results due to Duffus, Winkler and Sands and some new observations of Duffus, Luczak and Sands on these sorts of subsets. In particular, we provide bounds on the minimum size of fibres for finite distributive lattices.
Stefan Felsner, Freie Universitat

The complexity of partial order properties
Joint work with Ravi Kant, C.Pandu Rangan and Dorothea Wagner

A well studied {recognition problem} on sets arising in the context of representing sets in computer storage is defined by the following game. Given a finite set S and a property {P} of subsets of S, i.e. { P} {2^{S}} (the powerset of S), a player A wants to know if an unknown set $X\subseteq S is in {P} by asking questions about elements of S. For his questions A chooses some x S and asks Is x X?", player B answers yes" or no". The aim of A is to minimize the number of questions, while B tries to force A to ask as many questions as possible. Faigle and Tur\'an suggested to play the game on properties of partial orders. Here player A asks for the comparability status of two elements a and b, and B answers ab or a and b are incomparable." The goal of player A is to decide whether the hidden partial order P has a certain property. We study the complexity, i.e., the optimal number of questions, of this game for several properties: P has exactly k comparable pairs. P is an interval order. P is a lattice. P is of height gq k. P has width k. Peter Fishburn, AT&T Labs - Research #### Linear extensions of semiorders The problem addressed is to determine all posets on n points with k ordered pairs in their ordering relation that maximize the number of linear extensions of such posets at (n,k). Fishburn and Trotter showed previously that the maximizing posets are always semiorders. and gave the complete solution for all (n,k) with k <= n. New work considers solutions for k between n+1 and 2n-3. Eric Gottlieb, Rhodes College #### K-equal partitions The sublattice \Pi_n^k of the partition lattice, known as the k-equal partition lattice, first appeared in the work of Bj\"orner, Lov\'asz, and Yao as the intersection lattice of a real subspace arrangement. They computed the M\"obius function of \Pi_n^k in a step towards determining the computational complexity of the following problem: given n numbers, are any k of them the same? Bj\"orner and Welker computed the Betti numbers and homotopy type of$\Pi_n^k, and Bj\"orner and Wachs found an EL-shelling. Bj\"orner and Sagan defined an analogous real subspace arrangement whose intersection lattice is the h, k-equal signed partition lattice \ol \Pi_n^{h, k}, a sublattice of the signed partition lattice. They found an EL-shelling for \ol \Pi_n^{h, k} and computed its Betti numbers. The Dowling lattice generalizes the partition lattice and the signed partition lattice. We define a sublattice Q_n^{h, k}(G) of the Dowling lattice which we refer to as the h, k-equal Dowling lattice. This lattice generalizes both \Pi_n^k and \ol \Pi_n^{h, k}. We find an EL-shelling and use it to describe the (co)homology and compute the Betti numbers of Q_n^{h, k}(G). When G is cyclic, Q_n^{h, k}(G) is the intersection lattice of a complex subspace arrangement.
Serkan Hosten, M.S.R.I.

#### Order dimension of the complete graph and scarf complexes

In this talk we will give a formula for the order dimension of the complete graph on n vertices as a function of n. This formula depends on counting certain anti-chains in the subset lattice of a finite set. We will also make connections to certain simplicial complexes called Scarf complexes which have been recently studied by algebraists. This is joint work with Walter Morris.
Glenn Hurlbert, Arizona State University

#### New extensions and applications of the Clements-Lindstrom Theorem

We derive a simplified version of the Clements-Lindstrom Theorem which can be used to prove the existence of thresholds for monotone families of submultisets of a set, analogous to the use of Lovasz's version of the Kruskal- Katona Theorem in proving the existence of thresholds for monotone families of subsets of a set. In particular, this result proves the existence of pebbling thresholds for arbitrary graph sequences.
Andy Liu, University of Alberta

#### A Mathematical Sherlock Holmes in the Classroom

At the University of Alberta, we have introduced an innovative course in discrete mathematics at the sophomore level. We use as text the mathematical novel "The Puzzling Adventures of Dr. Ecco" by Dennis Shasha of the Courant Institute. The emphasis is on problem-solving. The course has been going for five years now, and enrolment is climbing steadily. It is not a required course in any program, and yet we attract students from no less than six faculties. Dr. Ecco is a mathematical version of Sherlock Holmes, with a consulting agency to which government, industry and others bring mathematical problems. He even has a Dr. Watson (in the character of Prof. Scarlet) who is his chronicler and inadvertent assistant. Most of the problem arise from theoretical computing sciences. We have written a companion text titled "Prof. Scarlet's Notebook" which contains some theoretical background material as well as additiional problems.
Dianne Maclagan, University of California, Berkeley

#### Antichains of monomial ideals are finite

The main result of this talk is that the poset of order ideals of N^n, ordered by inclusion, has no infinite antichains. This is a reformulation of the title. We will give some applications of this result to computational algebra and geometric combinatorics, and discuss generalizations to other posets.
Walter D. Morris, Jr., George Mason University

#### Convex dimension of locally planar convex geometry

We prove that convex geometries of convex dimension n that satisfy two properties satisfied by nondegenerate sets of points in the plane, may have no more than 2^{n-1} points. We give examples of such convex geometries that have {n \choose 4} + {n \choose 2} + {n \choose 0} points.
Dhruv Mubayi, Georgia Tech

#### Minimal completely separating systems of k-sets

A collection C of k-sets of [n] is a completely separating system if, for all distinct i,j\in [n], there is an S \in C for which i \in S and j\not\in S. Let R(n,k) denote the minimum size of such a C. Our results include determining the asymptotic value of R(n_k,k) when n_k is a sequence with k \ll n_k \ll k^{1+\epsilon} for every \epsilon >0. This is joint work with Andre Kundgen and Prasad Tetali.
Jim Schmerl, University of Connecticut

#### Graph coloring and reverse mathematics

Motivated by results about recursive coloring of recursive graphs and by on-line coloring of graphs, I will discuss how graph coloring is related to reverse mathematics. It is hoped that this talk will suggest more questions than it answers.
John Shareshian, California Technical University

#### Topology of monotone graph properties

A monotone graph property is a collection P of graphs on a fixed labelled vertex set V (which we assume to be {1,...,n}) satisfying the two conditions
(A) If G is in P and H is a subgraph of G then H is in P, and
(B) If G is in P then so is every graph on vertex set V which is isomorphic to G. In other words, P is a simplicial complex whose vertices correspond to the edges of K_n, which admits a natural action of the symmetric group S_n. The topology of a geometric realization of an arbitrary monotone graph property P was investigated by Kahn, Saks and Sturtevant in their work on the evasivenes conjecture. More recently, particular classes of monotone graph properties have arisen in various problems from combinatorics and topology. I will discuss some of these recent developments.
Tom Trotter Chair, Arizona State University

#### A New approach to correlation inequalities

There are several correlation inequalities which were originally proved by using the Ahlswede/Daykin four functions theorem and its relatives. One such result is the xyz'' theorem: P[x>y]\le P[x>y|x>z]. This inequality was proved by Shepp using the FKG inequality, and the strong version by Fishburn with multiple applications of AD. However, these proofs do not apparently yield natural'' maps between the corresponding finite sets. In joint work with Graham Brightwell, we have found a combinatorial proof---one which sheds additional light on the structure of the poset in question. The starting point is a new proof of the following lemma of Fishburn.
Michelle Wachs, University of Miami

#### Bounded degree graph complexes

Let G be a graph, digraph or multigraph and let b be a positive integer. The set of subgraphs of G for which every node has degree at most b forms a simplicial complex. Some important special cases which have arisen in various contexts in the recent literature are the matching complex (G is a complete graph and b=1) and the chessboard complex (G is a complete bipartite graph and b=1). In this talk I will first discuss work of Bouc on the homology of the matching complex, Friedman-Hanlon on the homology of the chessboard complex and Reiner-Roberts on the homology of bounded degree graph complexes when G is a complete (bipartite) graph. I will then describe some new results extending these results to digraph and multigraph complexes.
Peter Winkler, Bell Laboratories

#### Games people don't play

Centuries ago games provided much of the motivation for studying mathematics, especially combinatorics and probability. We will go a step further and talk about some games which were devised specifically for mathematical illumination---and for our intellectual, rather than pecuniary, amusement.
Updated 07/14/99