Schedule of Talks

All talks will be in Fuller Labs, Room 320.

Friday, October 31.

1:30- 2:30 Coffee and Registration

2:30- 2:55 Louis Kalikow Priority Queues and Parking Functions

3:00- 3:25 Ansuman Bagchi Generalizing Median Polish

3:30- 3:55 S. S. Ravi Improving Networks Under Budget Constraints

4:00- 4:30 Herman Servatius Dual-Eulerian graphs

5:00- 7:00 Dinner - Higgins House, WPI Faculty Club

7:30- ?:00 Party - 15 Trowbridge Road "on campus". Treats provided. Bring tricks.

Saturday, November 1.

8:00- 9:00 Coffee, juice and bagles.

9:00- 9:25 Peter R. Christopher Walks on Binomial Graph

9:30-9:55 Nancy Eaton Defective List Colorings of Planar Graphs

10:00-10:25 Laszlo Liptak Upper Bound for the Possible Facets With Fixed Defect of the Stable Set Polytope

Coffee Break/Problem Session

11:00-11:25 Lee Rudolph Representation of Seifert Surfaces

11:30-11:50 Dan Archdeacon A New Characterization of Planarity

Lunch - Higgins House, WPI Faculty Club

1:30- 1:55 Ruth Haas Decomposing graphs into trees: a construction

2:00- 2:25 Jeffrey Hall Packing a graph with initial graphs

2:30- 2:55 Seth Chaiken Oriented Matroids and Electrical Networks

3:00- 3:25 Van H. Vu Coloring pseudo-random graphs

Generalizing Median Polish: An Active Set Algorithm for Two-Way Layouts,

Ansuman Bagchi bagchi@WPI.EDU Mathematical Sciences Department, Worcester Polytechnic Institute

Nilotpal Chakravarti, Indian Institute of Management, Calcutta, India

In this talk we consider the statistical problem of determining the best additive decomposition of a two-way layout, in the least absolute value sense. We use a linear programming formulation for this combinatorial optimization problem to derive an active set solution algorithm. The algorithm directly generalizes median polish (Tukey, 1977) and in a finite number of steps determines an optimal solution. Computational results will be presented.

Abstract Index

Some thoughts on dual eulerian graphs,

Herman Servatius hservat@WPI.EDU and Brigitte Servatius Mathematical Sciences Department, Worcester Polytechnic Institute

In the consideration of planar networks to be used in VLSI layouts, there is a natural role for the dual graph. Some optimization conditions have given rise to the concept of a {\em dual eulerian} graph, i.e., a graph with a planar embedding which has an euler trail whose dual is also an euler trial of the dual graph. In this talk we discuss some characterizations of dual eulerian graphs and some recognition criteria.

Abstract Index

A Combinatorial Representation of Seifert Surfaces

Lee Rudolph Department of Mathematics and Computer Science, Clark University

A Seifert surface is a compact oriented surface in 3-space without unbounded components. A link is the boundary of a Seifert surface; a knot is a connected link. Call two subsets of 3-space isotopic if some diffeomorphism of 3-space carries X onto X'. The problem of classifying knots and links up to isotopy has been attacked with many varied tools; one of the most successful has been the algebraic/combinatorial method of "closed braids". I will describe "braided surfaces", a simple but powerful combinatorial description of Seifert surfaces.

Abstract Index

On the construction of directed triplewhist tournaments

University of Rhode Island

This report will focus on some recent joint work with Ian Anderson, University of Glasgow. A general construction will be introduced and it will be demonstrated how it leads to Z-cyclic directed triplewhist tournaments for primes p such that 29 <<= p < 10000. Extension of these results to products of such primes will also be discussed. (Unfortunately, Norman Finzio will not attend.)

Abstract Index

Priority Queues and Parking Functions

Louis Kalikow, kalikow@BINAH.CC.BRANDEIS.EDU Brandeis University and Julian Gilbey, Queen Mary and Westfield College, London, UK

A priority queue is an abstract data type supporting the operations \INS\ and \DEL.

When a permutation $\sigma$ is used as the input stream of a priority queue, the output stream will be another permutation $\tau$ and the resulting pair $(\sigma, \tau)$ is called an allowable pair. A parking function on $[n]$ is a function $p:[n] \to [n]$ which can be thought of as a rule for parking cars on a one-way street; it satisfies $|\{i:p(i)\le m\}| \ge m$ for all~$m\in [n]$. We present a bijection between allowable pairs of permutations of $[n]$ and parking functions on $[n]$. This bijection has two nice properties: it is output-preserving, meaning the pair $(\sigma, \tau)$ corresponds to a parking function which parks cars in permutation $\tau$; and it is breakpoint-preserving, which means the two sets of objects can be decomposed in analogous ways. We then obtain an interpretation of the inversion enumerator for trees for allowable pairs. Finally, we introduce valet parking functions, which generalize parking functions, and give a bijection between those functions and allowable pairs of permutations of a multiset.

Abstract Index

Packing a graph with initial graphs,

Jeffrey Hall, University of New Hampshire

A "matroidal family of graphs," F, is a set of graphs such that for any finite graph G, the subgraphs of G isomorphic to members of F form the independent sets of a matroid.

We discuss two other ways to obtain a greedoid from a matroidal family of graphs. One of these constructions is useful for estimating dimensions of character varieties of finitely presented groups.

Abstract Index

Improving Networks Under Budget Constraints,

S. S. Ravi, Department of Computer Science, University at Albany - State University of New York, Albany, NY 12222

We consider budget constrained network improvement problems. An example of such a problem is the following. Suppose we are given an edge weighted graph, a cost function for each edge that gives the cost of reducing the weight of the edge by a specified amount, and a budget on the total reduction cost. The goal is to devise a strategy for reducing the weights of the edges so that the total reduction cost is within the budget and the graph with the modified edge weights has the smallest possible minimum spanning tree over all reduction strategies that obey the budget constraint. In general, such problems are NP-hard. So we consider the problem of obtaining near-optimal solutions. If the budget constraint must be met exactly, we show that even obtaining a near-optimal solution is NP-hard. We then present approximation algorithms that produce solutions where the budget constraint is violated by a small factor and the modified graph has a spanning tree whose weight is within a small factor of the optimal value. We also discuss extensions to other related problems.

The above results were obtained jointly with Kai-Uwe Drangmeister, Sven Krumke, Hartmut Noltemeier (all from University of Wuerzburg, Germany) and Madhav Marathe (Los Alamos National Laboratory, Los Alamos, NM).

Abstract Index

Oriented Matroids and Electrical Networks,

Seth Chaiken Computer Science Department, SUNY at Albany

Matroid theory has classically been applied to linear electrical network analysis. We find that a natural model for solvability questions about electrical networks with monotone nonlinearities (or with positive linear coefficients of unknown magnitudes, or for matrix sign solvability) is a pair of oriented matroids with a common ground set. Two theorems motivated by this application are presented: (1) Subject to rank conditions, two common bases of ML and MR with opposite relative orientation imply ML* and MR have a common non-zero covector. (2) When ML and MR are certain minors of a common ported oriented matroid M, the ported Tutte polynomial of M indicates common bases with specified relative orientations.

Abstract Index

Decomposing graphs into trees: a construction,

Ruth Haas Mathematics Department, Smith College, Northampton, MA, 01063

We give several characterizations for the following two classes of graphs: (i) graphs for which adding {\em any} l edges produces a graph which is decomposible into k spanning trees and (ii) graphs for which adding {\em some} l edges produces a graph which is decomposible into k spanning trees. In particular, we show when Henneberg type constructions can be used to construct such graphs and give a nonconstructive proof for this characterization.

Abstract Index

A New Characterization of Planarity,

Dan Archdeacon University of Vermont, Burlington, VT 05405

A theta graph is a homeomorph of K_{2,3}. In an embedded planar graph the local rotation at one degree-three vertex of a theta graph determines the local rotation at the other degree-three vertex. Using this observation, I give a characterization of planar graphs in terms of balance in an associated signed graph whose vertices are K_{1,3} subgraphs and whose edges correspond to theta graphs.

Abstract Index

Defective List Colorings of Planar Graphs,

Dr. Nancy Eaton,, and Thomas Hull University of Rhode Island

We combine the concepts of list colorings of graphs with the concept of defective colorings of graphs and introduce the concept of defective list colorings. Both list colorings and defective list colorings are generalizations of proper colorings. For this talk, all colorings are of the vertices of the graph.

Some Definitions: A proper coloring of a graph is an assignment of colors to the vertices so that each color class corresponds to an independent set in the graph. A defective coloring with defect d is a coloring of the vertices such that each color class corresponds to an induced subgraph with maximum degree at most d. A k-list assignment L, is an assignment of sets to the vertices so that |L(v)| = k, for all vertices v. A L-list coloring is a proper coloring such that the color assigned to v is in L(v) for all vertices v, and a d-defective L-list coloring is a defective coloring with defect $d$ such that the color assigned to v is in L(v) for all vertices v.

For a given graph G and defect d, we are interested in the smallest number k such that all k-list assignments L are d-defective L-list colorable. This talk will focus on results pertaining to list colorings, defect colorings and defective list colorings of different classes of planar graphs. For example, outerplanar graphs are L-list colorable for any 3-list assignment L. This is the best possible since an odd cycle cannot be properly 2 colored. But allowing a defect of size 2, allows a coloring with at most 2 colors and there exist outerplanar graphs which cannot be 2-colored with defect 1.

We will show that for outerplanar graphs, any 2-list assignment L has a 2-defective L-list coloring, which is also best possible due to the results given above. Also, for planar graphs in general, any 3-list assignment L has a 2-defective L-list coloring. We will give results of this form pertaining other classes of planar graphs.

Abstract Index

Coloring pseudo-random graphs

Van H. Vu vu-ha-van@MATH.YALE.EDU Dept of Math, Yale Univ.

Pseudo-random graphs on n vertices (with edge probability p, 0 < p < 1) are graphs where each vertex has degree roughly d=np, and any pair of vertices has roughly np^2 neighbors in common These are ramdomlike properties. Our main result says that for any p, the chromatic number of a pseudo-random graph is O(d/log d). This generalizes a result of Kim on coloring K_3 and C_4 free graphs. This also matches the well known bound for (genuine) random graphs (due to Bollobas and Luczak ) in order of magnitude. Since many constructions of pseudo-random graphs come from algebra (well known example is Paley graphs where p = 1/2, our theorem implies interesting algebraic consequences.

From the algorithmic point of view, the proof provides a polynomial coloring algorithm. Our result also holds for choice number if p is small (p < n^{1-\epsilon} for any positive \epsilon).

Abstract Index

Walks on Binomial Graph

Peter R. Christopher Mathematical Sciences Department, Worcester Polytechnic Institute

The nth binomial graph Bn is defined for each non-negative integer n. The vertex set of Bn is Vn = {vj, j = 0,1,...2^n - 1}; vi and vj are adjacent if and only if the binomial 'i+j choose i' is odd. Bn has n distinct eigenvalues and these are powers of the golden mean. The number of closed walks of lenth k in Bn with initial vertex vo is equal to the nth power of the (k+1)-st Fibonacci number. The total number of closed walks of length k in Bn is the nth power of the kth Lucas number.

Abstract Index

Upper Bound for the Possible Facets With Fixed Defect of the Stable Set Polytope,

Laszlo Liptak liptak@MATH.YALE.EDU Yale University

The stable set polytope of a graph is the convex hull of the $0$-$1$ vectors corresponding to stable sets of vertices. To any nontrivial, full-dimensional facet $\sum_{i=1}^{n}a_i x_i\leq b$ of this polytope we can associate an integer $\delta$, called the {\it defect\/} of the facet, by $\delta=\sum_{i=1}^{n}a_i-2b$. We will show that for any fixed $\delta$ there is a finite collection of graphs (called ``basis'') such that any graph with a facet of defect $\delta$ contains a subgraph which can be obtained from one of the graphs in the basis by a simple subdivision operation.

Abstract Index

Return to NE Symposium