Combinatorics Seminars

Academic year 2004-2005

 

 

Overview Schedule and Abstracts Participating Directions and Parking

UVM    SMC    IBM

SMC Math Dept. 

SMC CS Dept. 

SMC Home  Jo Ellis-Monaghan Home
UVM Math Dept. UVM CS Dept. UVM Home Dan Archdeacon Home

 

SMC/UVM Joint  Combinatorics Seminar, Fall 2004-Spring 2005.

(Note:  If you are on the announcement distribution list, and wish to be removed, or if you or someone you know would like to be added, please contact the organizers at: jellis-monaghan@smcvt.edu or archdeac@emba.uvm.edu ).

 

Overview

For many years the Math and CS departments at UVM have conducted weekly discrete math/combinatorics/computer science seminars.  This year, the seminars will be held jointly with St. Michael's college, with the location alternating campuses. Recently, in addition to traditional talks in theoretical combinatorics, there has also been a focus on the applications of combinatorics.  Our goal is to bring together academic and industry researchers for a productive exchange of the theory and applications of combinatorics.  This fall's seminar series will continue and build on the foundations laid in the previous semesters.

Examples of areas of application in computer science include data mining, storage in disk arrays, the design of parallel algorithms, software testing, database formatting, file organization, the analysis of algorithms, the design of networks, and interconnection strategies for networks.  Applications in information theory include wireless networking (the design of radio and satellite networks), internet communication protocols, signal processing, timing analysis and multiaccess communications. Combinatorial techniques are also used to address problems involving scheduling, packing, data compression, and book-width and fault-tolerant processing.  In molecular biology/biotechnology, applications include mapping genomes, forming the clone libraries, and designing chips for DNA probes.  In the past year and a half, new applications have even come out of Wall Street; (t,m,s)-nets are being used in numerical integration problems in financial mathematics.

A wide range of combinatorial techniques and theory is available for such applications.  In recent years a great deal of work has been done on developing new constructions, and a powerful theory of combinatorial constructions is emerging.  These applications come at a time when the power of combinatorial constructions combined with computational methods is beginning to be fully realized.  The problems appearing in these applications are providing us with new and challenging existence questions as well as surprising applications of familiar and long studied combinatorial techniques.

 

Participating

These seminars are open to the public.  No registration or fees are required to attend. 

Both industry and academic users of combinatorial techniques are invited to  share their own particular interests by conducting one of the seminars.  If you have an industry problem or other application that you are working with, this is an opportunity to present it to group of people who may be able to offer some approaches to it using newly developed techniques.  If you are a mathematician or computer scientist, this is a chance to hear about interesting problems and to share your techniques with people who might have a real need for them.  

The format of the seminars may be presentations, workshops, background followed by discussion, or even brain-storming sessions, at the discretion of the individual speakers.  If you are interested in conducting a session, please contact the organizers at joellis@emba.uvm.edu or archdeac@emba.uvm.edu  with a brief description of what you would like to talk about.

Schedule and Abstracts

The seminars generally will occur every other week, mid-afternoon on Monday, Wednesday or Friday, depending on the speaker's schedule.  Check specific abstracts for details.

Links to on-line slides and other resources from the various talks (if available) are provided at the end of each abstract.

Date

Speaker

Title
9-1-04 Mike Dinitz Full Rank Tilings of Finite Abelian Groups  
9-28-04 Dan Archdeacon Graphs on grids: area/volu me tradeoffs in circuit layout
10-13-04 Dan McQuillan Recent Results in Vertex Magic Total Labelings of Graphs.
10-18-04 Ron Graham

(Two Talks)

2:30--Archimedes, Combinatorics and the Stomachion

4:00--Searching for the Shortest Network

10-26-04

Mary Cox  The Continued Fraction in Combinatorial Game Theory
11-8-04

Dr. Eugene H. Spafford

Exploring Grand Challenges in Trustworthy Computing
2-17-05 David Wood Fast Separation in Graphs with an Excluded Minor
  2-18-05 David Wood Drawing of Graphs in Two and Three Dimensions (UVM Colloquium talk)
  4-7-05 John Schmidt A Problem in Extremal Graph Theory
  5-5-05 Alice Dean Characterizations of Unit-Bar Visibility Graphs
  7-20-05 Tom Zaslavsky Inside-Out Polytopes and the Geometry of Graph Coloring

 

[Fall 2001 Abstracts]  [Spring 2001 Abstracts] [Spring 2002 Abstracts] [Fall 2003 - Spring 2004 Abstracts]

Date:   Wednesday, September 1, 2004

Ti me :  2:30 – 3:30 pm

Location:   Mathematics Depart ment Conference Room, Lord House, 16 Colchester Ave. , UVM Campus.

Title: Full Rank Tilings of Finite Abelian Groups

Speaker:  Mike Dinitz, Princeton University

Abstract:  

A tiling of a finite abelian group G is a pair (V,A) of subsets of G such that 0 is in both V and A and every g \in G can be uniquely written as g=v+a with v \in V and a \in A. Tilings are a special case of nor me d factorizations, a type of factorization by subsets that was introduced by Hajos in 1949. A tiling is said to be full rank if both V and A generate G. Cohen et al. proved that any tiling of {Z}_2^n can be decomposed into full rank and trivial tilings. We generalize this decomposition from {Z}_2^n to all finite abelian groups. We also show how to generate larger full rank tilings from smaller ones, and give two sufficient conditions for a group to admit a full rank tiling, showing that many groups do admit them.

Date:   Tuesday, September 28, 2004

Ti me :  3:30 – 4:30 pm

Location:   Farrell Room, STE 315 , SMC Campus.

 

Title: Graphs on grids: area/volu me tradeoffs in circuit layout

 

Speaker:  Dan Archdeacon , Depart me nt of Mathematics, University of Vermont

 

Abstract:  

 Finding a layout for a computer circuit can be considered as drawing a graph on an n x n grid or me sh. There are several me asures of how efficient the layout is: the first strives to minimize the area, a second examines the maximum wire run, a third bounds the number of bends in the wires. So me ti me s a circuit that is good in one sense is bad in another. We examine these tradeoffs. We also examine what happens when we layout circuits in 3-di me nsional n x n x n grids.

 

Flat tori: geometric realizations of toroidal triangulations (PowerPoint, 7MB)

Date:   Wednesday, October 13, 2004

Time :  2:30 – 3:30 pm

Location:   Math Conference Room, Lord House, 16 Colchester Ave., UVM Campus.

 

Title:  Recent Results in Vertex Magic Total Labelings of Graphs. (based on work with students: Katy Smith, Aaron Thurston and Karthik

Raman, all of Norwich University .)

 

Speaker:  Dan McQuillan, Norwich University .

 

Abstract:  

A Total Labeling is an assign me nt of consecutive integers

1,2,3,... to the vertices and edges of a graph. It is called magic if

the "weight" at each vertex is the sa me . This weight is called the

magic constant of the labeling. For most regular graphs, there are many

vertex magic total labelings (VMTL's). Furthermore, there are usually

many different possible magic constants. We describe the classification

of the set of all possible magic constants for the odd complete graphs,

among others.

Date:   Monday, October 18, 2004

Time :  2:30 - 3:30   and 4:00 - 5:00 (TWO TALKS)

Location:   UVM campus--see below for building/room

 

 

Speaker:  Ronald L. Graham.

As part of the President's Distinguished Lecture Series the Department of Mathematics and Statistics is pleased to host Ronald Graham.

He will be speaking at

4:00pm Monday October 18th in Angell B106 on the UVM campus.

A reception will follow in Billing's Apse.

Dr. Graham is the current president of the Mathematical Association of America, past president of the American Mathematical Society, and of the International Jugglers Association. He is in the Guinness Book of World Records for the largest number ever used in a mathematical proof, and in Ripley's Believe it or Not for his skills as a trampolinist and juggler.

For more details on Dr. Graham see: http://www.math.ucsd.edu/~fan/ron/

Title: Searching for the shortest network

Abstract: There are many situations in which one would like to connect a collection of points together by a network having the minimum possible total length. Such problems occur in the design of telephone networks, railroad lines, oil and gas pipeline networks, heating and air-conditioning duct systems, the layout of VLSI chips, and the inference of evolutionary pathways for living organisms, for example. In this talk we give a summary of what is known (and unknown) about this classical problem, and how current developments in computer science have impacted it.

If you only go to one math talk this year, this should be it!

There is also a second, earlier, talk:

Archimedes, Combinatorics and the Stomachion

Professor Ron Graham

University of California at San Diego

Monday, October 18, 2004

2:30-3:20 PM

Room L200 Lafayette
Reception to follow in Billings Apse at 5:00pm

Abstract:

Greek mathematics has long been known for its fundamental contributions to geometry and diophantine equations, for example  However, there is now evidence that ancient Greek mathematicians were also interested in various combinatorial problems. In this talk, I will describe some recent work exploring this theme which arose from the analysis of a puzzle called the Stomachion, which was recently discovered in a long lost manuscript of Archimedes.

 

Date:  Tuesday, October 26, 2004

Time:  3:30 – 4:30 pm

Location:  Jeanmarie 391, SMC Campus.

 

Title:  The Continued Fraction in Combinatorial Game Theory

 

Speaker:  Mary Cox, UVM.

 

 

Abstract:  

 

The origin of continued fractions is traditionally placed at the time of the creation of Euclid's Algorithm; in fact, continued fractions are intimately related to Euclid's Algorithm.  In the 19th Century, there was an explosion of growth within this subject, with contributions by Jacobi, Perron, Hermite, Gauss, Cauchy, and Stieljes.  Since the beginning of the 20th Century continued fractions have made their appearance in other fields, including chaos theory, within computer algorithms for computing rational approximations to real numbers, solving indeterminate equations, and knot theory.  Very recently, continued fractions have also been used in the relatively young field of combinatorial game theory.

 

In this talk, we define the general and simple continued fraction, and give a short demonstration of a traditional number theoretic use -- solving Pell's equation.  We then outline the basics of combinatorial game theory, and then demonstrate the use of continued fractions in this area of mathematics by demonstrating the evaluation of a game of Contorted Fractions.

 

This talk is accessible to a general audience.

Combinatorial Game Theory, The Continued Fraction: Two Little-Known Uses

 

Date:   Monday, November 8, 2004

Time :  4:00-5:00 pm

Location:   McCarthy Auditorium, SMC Campus.

 

This is a Special Event Sponsored by the SMC Computer Science Department in honor of St. Michael's College Centennial Celebration.

 

Title:  Exploring Grand Challenges in Trustworthy Computing

 

Speaker:  Dr. Eugene H. Spafford, Purdue University

 

Abstract:  

We are presented with numerous challenges to make our information systems more secure, increase our confidence in our stored data, and protect the privacy of our personal information. However, under the steady barrage of attacks and flaws, it is sometimes difficult to think in terms of "big" challenges that can inspire us to make revolutionary, rather than evolutionary, strides.

In this presentation I will discuss a few of the trends and problems that have been occupying researchers and industry over the last few years. I will explain why advances against these challenges are unlikely to provide long-term improvements in the security of our infrastructure. From this, I will then discuss the results of the recent CRA Grand Challenges conference on information security, including some discussion of how we might proceed to make progress on each of these four grand challenges.

Dr. Eugene H. Spafford is a professor of Computer Sciences at Purdue University, where he also holds courtesy positions in the following departments: Philosophy, Communication, Electrical and Computer Engineering. He is the Executive Director of CERIAS – the Center for Education and Research in Information Assurance and Security – which is a campus-wide multi-disciplinary Center, with a broadly-focused mission to explore issues related to protecting information and information resources.

Dr. Spafford has written extensively about information security, cybercrime, software engineering, and professional ethics, and is a Fellow of the ACM, AAAS, and IEEE. He is also a member of the President’s Information Technology Advisory Council.

Date: 2/17/05

Time:  4:00 – 5:00 p.m.

Location:  Farrell Room (St. Edmunds, Room 315), St. Michael’s College

 

Title:  Fast Separation in Graphs with an Excluded Minor

 

 

Speaker:  David Wood, McGill University, Montreal

 

Abstract:   A separator in a graph is a set of vertices whose removal splits the graph into two roughly equal sized pieces. In 1977, Lipton and Tarjan proved that every planar graph on n vertices has a separator of O(\sqrt{n}) vertices.

This result has found applications in numerous areas including approximation algorithms for NP-hard problems, solving sparse systems of linear equations, pebbling games, and graph drawing. In 1990, Alon, Seymour and Thomas generalised the Lipton-Tarjan result by proving that every graph with a fixed excluded minor (eg planar graphs have no K_5 and no K_{3,3} minor) has a separator of O(\sqrt{n}) vertices. Unfortunately, the running time of the resulting algorithm was O(n^{3/2}), compared to O(n) in the planar case. We present a preprocessing step to the Alon-Seymour-Thomas algorithm which leads to a O(n) time algorithm, at the expense of a slightly larger separator. This is joint work with Bruce Reed.

 

See David Wood's Website at

http://www.cs.mcgill.ca/~wood/

Talk overheads: DavidWood-Separators.pdf

Date: 2/18/05

Time:  4:00 – 5:00 p.m.

Location:  004 Kalkin, UVM Campus

 

Title:  Drawing of Graphs in Two and Three Dimensions

 

Speaker:  David Wood, McGill University, Montreal

 

Abstract: Graph theory has its origins in drawings of planar graphs. Recently there has been renewed interest in graph drawings due to interesting results and numerous applications in diverse areas including software engineering, information visualisation, and VLSI circuit design. In this talk I will introduce the discipline of graph drawing, and survey a few of the main results. The focus will be on drawings of graphs in three dimensions, in which the vertices are positioned at integer grid-points, and the edges are non-crossing straight line-segments. While it is folklore that every graph has such a representation, I shall consider three-dimensional drawings with small bounding box volume. A survey of this problem will be presented, along with lower and upper bounds on the minimum volume for various classes of graphs.

 

See David Wood's Website at

http://www.cs.mcgill.ca/~wood/

Talk overheads: DavidWood-GraphDrawing.pdf

 

 

Date: Thursday, 4/7/05

Time:  3:30 – 4:30 p.m.

Location: SMC Campus, Jeanmarie 362

 Title:  A Problem in Extremal Graph Theory

 Speaker:  John Schmidt, Department of Mathematics, Emory University

 Abstract:

Graphs have proven to be a very important mathematical model. For example, computer or telephone networks can be viewed as graphs.  Often, one would like to build a graph  that has a certain property.  A natural question then arises:

"How much does one have to spend to build the graph with the desired property?" 

 We will discuss such a question as asked by Paul Erdos and its solution.

No previous knowledge of graph theory is assumed.

Combo_Seminar/overheads/JohnSchmitttalk.pdf

Date: Thursday, 05/05/05

Time:  3:30 – 4:30 p.m.

Location: SMC Campus, Jeanmarie 362

 Title:  Characterizations of Unit-Bar Visibility Graphs

 Speaker:  Alice Dean, Department of Mathematics and Computer Science, Skidmore College

 Abstract:

Representations of graphs using horizontal bars for vertices and vertical visibilities for edges have been studied since the mid 1980s, motivated by applications to circuit design and display of data. Graphs that can be represented in this way have been fully characterized, but the bar lengths may differ by impractical amounts. I consider graphs that can be represented using bars all of equal length. These graphs, called unit-bar visibility graphs (or UBVGs), have not been fully characterized. I will discuss results for several classes of graphs, including trees and outerplanar graphs. The final result is a characterization of the triangulated polygons (TPs) that are UBVGs. The characterization uses a character string associated with each TP to determine if a UBV layout exists and if so, to produce such a layout.

This is joint work with E. Gethner and J. Hutchinson and, separately, with N. Veytsel.

Combo_Seminar/overheads/AliceDeanUBVGs.pdf

Date: Wedneday, 07/20/05

Time:  10:00 – 11:00 a.m.

Location: Mathematics Department Conference Room, Lord House, 16 Colchester Ave., UVM campus.

 

Title: Inside-Out Polytopes and the Geometry of Graph Coloring

 

Speaker:  Tom Zaslavsky, Department of Mathematics, SUNY Binghamton

 

Abstract:

A rational inside-out polytope consists of a convex polytope P with rational vertices in Eucldean space together with a finite set of rational hyperplanes. The number of 1/t-integral points in the interior of P but not in any of the hyperplanes is a function of t = 1,2,3,... that is given by a quasipolynomial (a cyclically repeating sequence of polynomials).

We -- that is, Matthias Beck and I -- deduce this from Ehrhart's theory of rational polytopes (without hyperplanes).

 

The theory explains why a graph has one chromatic polynomial but a signed graph has two.  It shows that the number of magic squares of fixed size is a quasipolynomial function of the magic sum; the number of antimagic labellings of a fixed graph by integers from 1 to t is a quasipolynomial function of t; and more....

Date:   TBA

Time :  TBA

Location:   math department conference room, Lord house, 16 Colchester Ave

Title:  Isotropic systems, DNA sequencing and the interlace polynomial

Speaker:  Jo Ellis-Monaghan, department of mathematics, Saint Michael’s College

Abstract: 

The interlace polynomial of a graph, described in [R. Arratia, B. Bollob \'as, G. Sorkin, The Interlace Polynomial: a New Graph Polynomial, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, Jan. 2000, 237-245.] as evolving from problems in DNA sequencing, evokes many open questions.  By exploiting the machinery of Tutte-Martin polynomials of isotropic systems and a recent paper of Bouchet [A. Bouchet,Graph Polynomials Derived from Tutte-Martin Polynomials, in press] that realizes the interlace polynomial of a graph as a special case of a Tutte-Martin polynomial of an isotropic system, we are able to resolve several open questions presented by Arratia, Bollob\'as and Sorkin.  These include the relation between the interlace polynomial and the Tutte polynomial, the computational complexity of the interlace polynomial, and perhaps most importantly, an interpretation of exactly what the interlace polynomial of a graph counts.  We conclude by presenting a class of graphs on which the interlace polynomial is polynomial time to compute and which is characterized by an invariant $\gamma$ analogously to the way series parallel graphs are characterized by the $\beta$ invariant.

This talk should be accessible to students who we have some background in elementary graph theory and linear algebra.

 

Directions and Parking
 

SMC


Directions to SMC:  From major cities, see SMC Directions
Once on Interstate 89 see below:

Main Entrance:
Bear right off of exit 15, Interstate 89.  Stay in right lane and follow Route 15 through two lights.  After second light bear right into jug handle and go through intersection to campus.  The Office of Admission is located in the Hoehl Welcome Center on the left, with visitor's parking at the entrance.  (Coming from IBM on Route 15, turn right at the lights across from the jughandle)
 
South Entrance:
Bear right off of exit 15, Interstate 89 and get into left lane.  At first set of lights, take left into parking lot.  McCarthy Arts Center is on your right.  Ross Sports Center is on left at back of parking lot.  Visitor parking is marked in this lot (stay straight as you enter, and look to your left).  (Coming from IBM on Route 15, turn right at the lights by Purple Knight's Pizza.)


Maps: There are campus maps on the SMC website at SMC Campus Map 

Most talks are likely to be held in Jeanmarie, St. Edmunds Hall, or the Science building.

UVM
Picture: There is a picture of the Math Department building (Lord House, 16 Colchester Avenue) at http://www.emba.uvm.edu/math .

The seminars are often held here in the conference room on the first floor.

Parking: The easiest place to park is probably the Visitor Lot at Waterman. 
It is located on College Street, across the street from the Waterman administration building.  Parking is paid, 75 cents/hour, 7 a.m. to 5 p.m., Monday through Friday, and free after 5 p.m. and on weekends and holidays.

Directions to the Vistors' lot:
From I-89: Take Exit 14W into Burlington. This puts you heading west on Williston Road going up hill. 
Turn right onto North Prospect Street. Take first left onto College Street. Take first left into visitor parking lot. 

Heading north from Route 7: Follow Shelburne Road/Route 7 into Burlington. At rotary, bear right. Approximately 1/4 mile to first four-way stop, turn right onto Cliff Street. Head uphill to end of Cliff; take left onto South Prospect Street. Cross Main Street/Route 2. Take first left onto College Street. Take first left into visitor parking lot.

Maps: There are campus maps on the UVM website, and the direct URAL is: http://scripts.uvm.edu/www/map.php3

Click on the map to zoom in, or use the "locate" button at the bottom to find specific buildings or parking lots (the Math Department is 16 Colchester, the visitor lot is across College street from Waterman building).

A map of the whole campus with visitor parking colored green is at http://www.uvm.edu/~tpswww/images/oncampus.jpg, but you need a LARGE monitor to read the labels.

IBM--Williston Site

From Interstate 89:  Coming from the north or south, take exit 12. From the north, turn left off exit ramp; from the south, turn right onto Route 2A. Follow the road past three traffic lights, over a bridge and up a hill. Watch for (and turn into) IBM entrance signs on the right. 

For the WILLISTON LOBBY:  After turning into IBM, go straight.  Pass the “Main Lobby” signs.  Go around the S-curve and over bridge. Take third left-hand turn into the visitor parking lot.

Map: Here is a map of the area near IBM.  The Williston site is the dark rectangle just to the south of the rectangle marked IBM.