DIMACS DREI '99
Week 3 Topic: Graphs, Posets, and Algorithms
August 2  6, 1999
Abstracts
James Abello,
AT&T Research
Massive Multidigraphs
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 multidigraphs.
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.
Geir Agnarsson,
University of Iceland
Distancek 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 singlestrand DNAmodel, 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 nset be in order to meet
every maximal antichain? That is, what is the minimum size
of a socalled "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 2n3.
Eric Gottlieb,
Rhodes College
Kequal partitions
The sublattice \Pi_n^k of the partition lattice, known
as the kequal 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 ELshelling.
Bj\"orner and Sagan defined an analogous real subspace arrangement whose
intersection lattice is the h, kequal signed partition lattice \ol
\Pi_n^{h, k}, a sublattice of the signed partition lattice. They found
an ELshelling 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, kequal Dowling lattice. This
lattice generalizes both \Pi_n^k and \ol \Pi_n^{h, k}. We find an
ELshelling 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 antichains 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 ClementsLindstrom Theorem
We derive a simplified version of the ClementsLindstrom
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 problemsolving.
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^{n1} 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 ksets
A collection C of ksets 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 online 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>yx>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 proofone 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, FriedmanHanlon on the homology of the chessboard
complex and ReinerRoberts 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 illuminationand for our intellectual, rather than
pecuniary, amusement.
