Combinatorics Seminars

Academic year 2005-2006

 

 

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 2005-Spring 2006.

(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 jellis-monaghan@smcvt.edu or dan.archdeacon@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/12/05 Bruce Sagan Congruences for Combinatorial Sequences
9/28/05 Teresa Jin Real number graph labelings with distance conditions
10/5/05 John Schmitt On the Minimum Size of F-saturated Graphs
10/21/05 Rosa Orellana (UVM Colloquium)
10/24/05 Rebecca Mercuri E-Voting: Perils and Promises (SMC special event)
11/2/05 John Jungck Topological Toys, Tinkering Thinking: Knot Theory for the Three R's of DNA
11/30/05 Teresa Jin Real number graph labelings with distance conditions (II)
2/6/06 Joshua Cooper A Deterministic Random Walk on the Integers
2/22/06 Florian Pfender

Spherical Codes and Delsarte's Method

3/6/06 Ron Graham Mathematics in the 21st century: Problems and Prospects (SMC special event)
4/16/06 Dalibor Froncek Decomposition of complete graphs into pompous cycles
4/27/06 Jamey Lewis Computer Chip Design with Force Directed Graphing
5/2/05 Jo Ellis-Monaghan Distance Hereditary Graphs and the Interlace Polynomial

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

Date: Monday, 9/12/05

Time:  3:45-4:45 pm

Location: Science  (a.k.a. Cheray) 201, SMC campus

 

Title: Congruences for Combinatorial Sequences

Speaker:  Bruce Sagan, Department of Mathematics, Michigan State University

Abstract:

We derive congruences for various sequences involving binomial coefficients.  In particular, we are able to prove some conjectures of Benoit Cloitre.  Surprisingly, the Thue-Morse sequence (from the theory of combinatorics on words) makes an appearance.  This is joint work with Emeric Deutsch.

Date: Wednesday, 9/28/05

Time:  3:35-4:25 pm

Location: Math Conference Room, 16 Colchester Ave, UVM campus

 

Title: Real number graph labelings with distance conditions

Speaker:  Teresa Jin, Department of Mathematics, University of Vermont

Abstract:

The integer graph labeling problem with distance conditions, as a generalized graph coloring problem, originally comes from a radio channel assignment problem in wireless communication networks that seeks to model efficient channel assignments for a network of transmitters. Griggs and Yeh (1991) formulated the  integer $L(2,1)$-labeling problem, and mentioned the integer  $L(k_1,k_2,\ldots,k_p)$-labeling problem.

To prevent interference, labels for nearby vertices must be separated by specified amounts $k_i$ depending on the distance $i$, $1\le i\le p$. Here we expand the model to allow real number labels and separations. The main finding (``$D$-set

Theorem") is that for any graph, possibly infinite, with maximum degree at most $\Delta$, there is a labeling of minimum span in which all of the labels have the form $\sum_{i=1}^p a_i k_i$, where the $a_i$'s are integers $\ge 0$.  We show that the minimum span is a continuous function of the $k_i$'s, and is piecewise linear for $p=2$ or finite graphs. We conjecture that it is piecewise linear with finitely many pieces. Our stronger conjecture is that the coefficients $a_i$ can be bounded by a constant depending only on $\Delta$ and $p$.  We give formulas for the minimum spans of several graphs with general conditions at distance two, including paths, cycles, wheels, the triangular lattice, the square lattice, and the hexagonal lattice.

Date: Wednesday, 10/5/05

Time:  3:35-4:25 pm

Location: Math Conference Room, 16 Colchester Ave, UVM campus

 

Title: On the Minimum Size of F-saturated Graphs

 

Speaker: John Schmitt, Middlebury College

 

Abstract:

A graph G is said to be F-saturated if G does not contain a copy of a F as a subgraph and G + e  contains a copy of F as a subgraph for any edge e contained in the complement of G.  The famous problem of Turán seeks to determine the maximum number of edges, ex(n, F), in such a graph.  Here we consider the dual, that is we are interested in the minimum  number of edges, sat(n, F), in such a graph.  We will outline the history of the problem, present recent results when F is a bi-(multi-)partite graph or a cycle, and discuss open problems and conjectures.

 

UVM Mathematics Colloquium

Date: Friday, October 21, 2005

Time:  3:45-4:45 (refreshments at 3:30)

Location: Kalkin 003, UVM Campus

 

Title: Descents and Peaks

 

Speaker:  Rosa Orellana, Dartmouth College

 

Abstract:

The descent algebra of the symmetric group has played an important role in the understanding of the symmetric group and mathematics in general. One famous example of their applicability is that of Bayer and Diaconis who used a subalgebra of the descent algebra to determine the minimum number of shuffles needed to "randomize" a deck of cards. The descent algebra has also been used towards understanding the representations of the symmetric group. One of the most important properties of this algebra is that there exists a surjection from this algebra to the Burnside Ring of the symmetric group spanned by induced characters. Further, this algebra has close ties to quasi-symmetric function and is related to an important algebra, called the peak algebra.

 

The first part of the talk will present a combinatorial introduction to the descent and peak algebras. During the second part of the talk I will discuss recent work with Mathas on a generalization of descent algebras to complex reflection groups. In particular, we have introduced an algebra that follows the construction given by Solomon in terms of "Young" subgroups. This talk will be presented from a combinatorial perspective and it will be self-contained.

 

This talk will be accessible to advanced undergraduates.

Combinatorics Seminar

Date: Wednesday, November 2, 2005

Time:  3:45-4:45 (refreshments at 3:30)

 

Location: Farrell Room, St. Edmunds Building, SMC Campus.

 

Title: Topological Toys, Tinkering Thinking: Knot Theory for the Three R's of DNA

 

Speaker:  John Jungck, Beloit College, http://www.beloit.edu/~biology/jungck.html

 

Abstract:

 

Work co-authored with  Srebrenka Robic, UC Berkely.

 

Does DNA simply unzip in replication, recombination, and repair? Imagine the string in your junk drawer multiplied many times and you will have some idea of how tangled exceptionally long strings of DNA are in the cell.  Such supercoiled DNA is demonstratably almost impossible to unknot simply by unraveling.  Mathematicians pointed this out to biologists shortly after Watson, Crick, Wilkins, and Franklin solved the three dimensional geometry of DNA.  Geometry and topology are quite different.  Topology is geometry on rubberized graph paper or as DeWitt Summers has said: "Topology is geometry in California all twisted and bent out of shape."  DNA topology is able to deal with writhing (bends extending over a long distance), twisting (local coiling), links (over and under crossovers or the sum of negatively and positive supercoils), and knots in DNA. Mathematicians predicted that enzymes (topoisomerases) must exist that catalyze the breaking and re-joining of DNA in order to unravel DNA and that these enzymes must have holes in them.  What if replicated DNA strands were tied in a knot and a cell tries to divide?  Might this be a problem in some diseases? How can knot theory help us understand DNA packing?  How can we estimate the rates at which enzymes unknot DNA? My presentation will be filled with audience involvement with supercoiled zipper models of DNA unwinding, velcro ribbon models and telephone cords & connector models to demonstrate the action of type I and II DNA topoisomerases, "Why Knots," the University of Minnesota Supercomputer movie "Not Knot," wire sculpture models by the artist Dennis Dreher (a student of "Bucky" Fuller) of polysomes folded into chromosomes (coiled-coiled-coiled-coils), macrame' coils, tensegritoy models of actin and microtubule networks inside of cells,, and numerous slides.  Come to understand why mathematical biologists help experimentalists through visualization made possible by theory, or, as goes Dolf Seilacher's adage: "I wouldn't have seen it, if I hadn't believed it."

Date: Wednesday, 11/30/05

Time:  3:45-4:35 pm

Location: Jean Marie 373, SMC campus

 

Title: Real number graph labelings with distance conditions (II)

 

Speaker:  Teresa Jin, Department of Mathematics, University of Vermont

 

Abstract:

The problem of radio channel assignments with multiple levels of interference can be modeled using graph theory. The theory of integer vertex-labelings of graphs with distance conditions has been investigated for several years now, and we recently introduced a new model of real number labelings that is giving deeper insight into the problems.  Here we present the formulas for the optimal span of labelings with conditions at distance two for paths, cycles, planar regular lattices, as well as the proofs.

Besides contributing to the theory, the

techniques illustrated in the proof are of interest.

We conclude with some directions for future research.

 

Date: Tuesday 2/6/06

Time:  3:30-5:00 pm

Location: 205 Votey, UVM campus

Title: A Deterministic Random Walk on the Integers

Speaker:  Joshua Cooper, Candidate for Math Faculty Position in Combinatorics and Graph Theory

Abstract:

Jim Propp's P-machine, also known as the “rotor-router model,” is a simple deterministic process that simulates a random walk on a graph.  Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order.

 We investigate how well this process simulates a random walk.  For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant, which is approximately 2.29.  For intervals of length L, this improves to a difference of .  For the  average of a contiguous set of intervals it improves to .

 Joint work with Benjamin Doerr, Joel Spencer, and Gabor Tardos.

Date: Wednesday, February 22, 2006

Time:  1:25-2:25 pm

Location: 102 Perkins, UVM campus

Title: Spherical Codes and Delsarte's Method

Speaker:  Florian Pfender, Candidate for Mathematics Faculty Position in Combinatorics

 

Abstract:

In coding theory, a lot of energy is spend to find good codes. But very often it is hard to give good quality guarantees as upper bounds on sizes of codes are hard to come by. In the 70s, Phillippe Delsarte developed an approach which gives the best known bounds for many problems. In this talk we will take a closer look at this approach and see some recent improvements to the method. This leads to some new upper bounds for kissing numbers in several dimensions, the number of unit balls which can simultaneously touch one central ball.

The Saint Michael's College Gamma Chapter of Phi Beta Kappa is honored this semester to host Phi Beta Kappa Visiting Scholar Dr. Ronald Graham, Professor of Computer and Information Science at the University of San Diego .

He will be speaking at 7:00 pm Monday, March 6, 2006,  at the McCarthy Arts Center on the SMC campus, with a reception to follow.

ANNOUNCEMENT POSTER

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/

Combinatorics Seminar

Date: Wednesday, April 19, 2006

Time:  1:15-2:05 pm

Location: Math Department Conference Room, Lord House, UVM Campus

 

Title: Decomposition of complete graphs into pompous cycles

 

Speaker:  Dalibor Froncek, University of Minnesota Duluth

 

Abstract:  pompous cycles.pdf

 

Combinatorics Seminar

Date: Thursday, April 27, 2006

Time:  4:15-5:05 pm

Location: Math Department Conference Room, Lord House, UVM Campus

 

Title: Computer Chip Design with Force Directed Graphing

 

Speaker:  Jamey T. Lewis, St. Michael's College

 

Abstract: 

 

Force-directed graphing involves applying a physical analogy to graphs of nodes and edges, allowing forces of attraction and repulsion to push and pull the system into a state of equilibrium. This method has been implemented to aid in computer chip design, simulating the structure of gates and wires in the chip as nodes and edges.  We have further modified the basic model in order to apply it to the floorplanning stage of chip design, in which the set of gates in the chip is partitioned into logical clusters or blocks which are then placed in the chip space as a pre-processing step for the actual placement and routing. In this presentation I will discuss the basic "spring-embedder" force-directed algorithm, as well as our additions to it, such as the use of nodes with width and height, effective repelling perimeter and pressure equalization equations. I will also present a brief summary of the experimental results that demonstrate the feasibility of this approach. This work responds to an industry problem presented by Cadence Design Systems, a company that develops chip layout tools, and IBM.

 

Combinatorics Seminar

Date: Tuesday, May 2, 2006

Time:  3:35-4:25 pm

Location: Math Department Conference Room, Lord House, UVM Campus

 

Title: Distance Hereditary Graphs and the Interlace Polynomial

 

Speaker:  Joanna A. Ellis-Monaghan, St. Michael's College

 

Abstract: 

 

The vertex­nullity interlace polynomial of a graph, described by Arratia, Bollobas, and Sorkin as evolving from questions of DNA sequencing, and then extended to a two variable interlace polynomial, evokes many open questions.  These include relations between the interlace polynomial and the Tutte polynomial and the computational complexity of the vertex­nullity interlace polynomial.  Here, using the medial graph of a planar graph, we relate the one variable vertex­nullity interlace polynomial to the classical Tutte polynomial when x = y, and conclude that, like the Tutte polynomial, it is in general #P­hard to compute. 

 

We define the gamma invariant as the coefficient of x in the vertex-nullity interlace polynomial, analogously to the beta invariant, which is the coefficient of x in the Tutte polynomial.  We then turn to distance hereditary graphs, characterized by Bandelt and Mulder as being constructed by a sequence of adding pendant and duplicate vertices, and show that graphs in this class have gamma invariant a power of 2.  We furthermore show that bipartite distance hereditary graphs are exactly the class of graphs with gamma invariant 2, just as series parallel graphs are exactly the class of graphs with beta invariant 1. 

 

We show that a bipartite distance hereditary graph arises precisely as the circle graph of any Euler circuit in the oriented medial graph of a series parallel graph.  From this we conclude that the interlace polynomial is polynomial time to compute for bipartite distance hereditary graphs.

Joint work with Irasema Sarmiento.

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://www.uvm.edu/map  (the Math Department is 16 Colchester, the visitor lot is across College street from Waterman building).
 

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.