SMC/UVM Joint  Combinatorics Seminar, Fall 2008-Spring 2009.

(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 dan.archdeacon@uvm.edu).

Overview

For many years the Math and CS departments at UVM have conducted weekly discrete math/combinatorics/computer science seminars.  These seminars are now 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.

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

[Fall 2005-Spring 2006 Abstracts]  [Fall 2006-Spring 2007 Abstracts] [Fall 2007-Spring-Summer 2008 Abstracts]

Date: Thursday, November 20, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: Some problems with Beatty sequences

Speaker: Sam Northshield, SUNY Plattsburg

Abstract: A Beatty sequence is a sequence of the form [an+b] , n=1,2,3…
(a,b fixed reals) where [x] is the greatest integer not exceeding x. We
shall give a short geometric proof of Beatty’s theorem (a necessary and
sufficient condition for two Beatty sequences to partition the natural
numbers). We generalize this theorem and discuss Fraenkel’s conjecture
concerning when the natural numbers are partitioned by three or more
Beatty sequences. Another problem concerns the infinitude of primes in a
Beatty sequence (done first by Vinogradov). I will discuss attempts made
to solve this. Possibly, I will also discuss a problem concerning
composition of Beatty sequences.

Date: Thursday, November 13, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: Generalizing the degree sequence problem

Speaker: John Schmitt, Middlebury

Date: Thursday, November 6, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: The Existence of $N_2$ Resolvable Latin Squares

Speaker: Jeff Dinitz, UVM

An $N_2$ resolvable latin squares is a latin square with no $2 \times 2$ subsquares that also has an orthogonal mate. In this talk I show that $N_2$ resolvable latin squares exist for all orders $n$ with $n \neq 2,4,6,8$ This is joint work with Alan Ling and Adam Wolfe.

Date: Thursday, October 30, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: Coloring with an unruly partner

Speaker: Victor Larsen, Middlebury College

Competitive graph coloring considers the r-coloring game originally

introduced by Bodlaender in 1991, so it is a fairly new topic with many

unexplored possibilities. In this game, Alice and Bob alternately color

the vertices of a graph G with a set X of r colors. Alice seeks to color

the graph using the fewest possible number of colors. Bob, however,

tries to force Alice to use more colors. This game has been studied on

many classes of graphs (trees, planar graphs, partial k-trees, etc.) and

bounds have been proven for the different classes, some significantly

looser than others. We will give a brief introduction to this topic and

highlight some of the more significant theorems.

Date: Thursday, October 23, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: Graph Theory and Complex Systems in Statistical Mechanics.

Speaker: Jo Ellis-Monaghan, SMC

What do beer foam, ghetto formation, and tumor migration have in common? They are all complex systems where microscale nearest neighbor interactions (neighboring bubbles, neighboring residences, neighboring  cells) determine macroscale properties. These macroscale phenomena  can lead to bottling problems, segregation, or malignancy. How then do we model, and thereby predict, the behaviors of such systems?

Statistical mechanics provides one tool in the q-state Potts model.  Its nascent form, the Ising model, allows only two spins (up or down), and provides a model for magnetism.  The Potts model with q > 2 allows more spins (thousands in the case of foam models).  These models play important roles in the theory of phase transitions and critical phenomena in physics, and now have applications in every science.

The Potts model is typically constructed on various lattices.  When these lattices are viewed as graphs,  then, remarkably, the Potts model is also equivalent to one of the most renown graph invariants, the Tutte polynomial.  Thus, there has been a remarkable synergy between the two fields in recent years.  This talk will explore the Potts model, how it captures macroscale properties, its applications, and its relation to the Tutte and Chromatic polynomials.    

Date: Thursday, October 16, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: A partial dual of a polyhedron

Speaker: Dan Archdeacon, UVM

An example of geometric duality of polyhedra is "the dual of the cube is   the octahedron". In this classical dual the faces become vertices, the vertices become faces, and an edge joining two vertices at its ends   becomes an edge joining the two faces on its sides. It has the nice property that "the dual of the dual is the original".    What if one only required that a subset of edges switch their roles from   joining points to joining faces, or even if a single edge switches its role? What would be the vertices or faces of such a partial dual? Try an   example and you'll discover that the familiar concepts of point and face quickly become quite muddled.    In this talk I will describe how to make *some* sense out of such a   partial duality. This partial duality preserves the properties that a) repeating it twice returns to the original polyhedron, and b) dualizing   over all edges corresponds to the classical geometric duality. We'll examine some properties of our partial duality, including its geometric   interpretation, prove some quick results, and discuss where it might be applied. 

Date: Thursday, October 9, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: Perfect one-factorizations of the complete graph

Speaker: Jeff Dinitz, UVM

  A one factorization of the complete graph is perfect if the union of any two one-factors forms a Hamiltonian circuit. Perfect one-factorizations are known to exist in complete graphs of orders p+1 and 2p for primes p and for some other sporadic orders. Recently, our own Adam Wolfe constructed a perfect one-factorization or order 52. This is the first new “small” order found in nearly 20 years. In this talk I will give background information on perfect one-factorizations and discuss Adam Wolfe’s new result.        

Date: Thursday, October 2, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: Some results on Deletion/Insertion Codes

Speaker: Alan Ling, UVM

We present some spectrum-type results for delete/insertion codes on length 3 and 4.

Date: Friday, September 26, 2008

Time:  3:35-4:25  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: Car parking and combinatorics

Speaker: Thomas Prellberg, Queen Mary University of London

Abstract:

Suppose that m drivers each choose a preferred parking space in a linear car park with n spaces. Each driver goes to the chosen space and parks 
there if it is free, and otherwise takes the first available space with larger number (if any).

We will consider the combinatorial question of how many assignments of m drivers to n spaces lead to p spaces being occupied (or equivalently, 
the probability that for a randomly chosen assignment exactly p spaces get occupied).

This problem is relevant for computer science (hashing with linear probing) and has also been studied in the physics literature in the context of percolation.

Date: Thursday, September 18, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: On lattice polygons

Speaker: John Voight, UVM

Recently, we discovered (in joint work with Wouter Castryck at Leuven) an inequality that relates the number of interior and boundary lattice points of a lattice polygon, generalizing the elementary and beautiful "onion skin" theorem of Haase and Schicho (using work of Poonen and Rodriguez-Villegas).  In this talk we will discuss these matters and ask some basic open questions on lattice polygons.  Students are particularly encouraged to attend!

Date: Thursday, September 11, 2008

Time:  2:00-3:15  pm

Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus

Title: The crossing numbers of graphs on the plane, the torus, and the double torus

Speaker: Dan Archdeacon, UVM

Abstract: A common way to present a graph is to draw it on the plane   with as few crossings as possible. Also interesting, but less common, is to draw it on the torus with as few crossings as possible. Or on the   double torus. As we add handles we can decrease the number of crossings. How much can this number of crossings decrease, and which "sequences of   crossing numbers" are possible? The answer is surprising. Lots of pictures are promised.      

Date: Thursday, January 22, 2009

Time:  4:00-5:00 pm

Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus

Title: The topological Tutte polynomial of Bollobas and Riordan

Speaker:  Jo Ellis-Monaghan, Saint Michael's College

The ribbon graph polynomial of Bollobas and Riordan extends the classical Tutte polynomial to ribbon graphs, or graphs cellularly embedded in a two-dimensional surface.  We will introduce these ideas, and prove a recipe theorem for the ribbon graph polynomial that justifies calling it _the_ topological Tutte polynomial.  This talk will lay the ground work for a future second talk detailing further results in this area.

This is joint work with Irasema Sarmiento.

Date: Thursday, February 11, 2009

Time:  3:30-4:30 pm

Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus

Title: Strong Magic Labelings and Kotzig Completion

Speaker:  Daniel McQuillan, Norwich

Abstract:

A total labeling is a bijective assignment of integers 1,2,3,.. to the vertices and edges of a graph. A vertex-magic total labeling (VMTL) has the added property that for each vertex v, the sum of its label and its incident edge labels is a constant. A VMTL is strong if the smallest labels are assigned to the edges and the largest are assigned to the vertices. It is unknown which 2-regular graphs have a strong VMTL. We discuss recent progress on this problem, using many different applications of Kotzig arrays. A Kotzig array is a jxk matrix, each row being a permutation of {0,1,…,k-1} and each column having constant column sum.

Date: Thursday, February 26, 2009

Time:  3:30-4:30 pm

Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus

Title: Constructions for Hash families

Speaker: Alan Ling, CS, UVM

Abstract: A {\em perfect hash family} $\PHF(N; k, w, t)$ is an $N \times k$ array on $w$ symbols, in which in every $N \times t$ subarray, at least one row consists of distinct symbols. In this talk, we give various constructions for perfect hash families and its generalizations. In addition, various old and recent applications of hash families are discussed.

Date: Thursday, March 19, 2009

Time:  4:00-5:00 pm

Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus

Title:  Eight Queens and More

Speaker: Tom Zaslavsky, SUNY Binghamton

Abstract:  Zaslavsky abstract 3-19-09.pdf

Date: Thursday, March 26, 2009

Time:  4:00-5:00 pm

Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus

Title: Ported Parametrized Tutte Functions: Old and New Applications

Speaker: Seth Chaiken, CS, SUNY Albany

Abstract: Chaiken abstract 3-26-09.pdf

Slides: Chaiken slides 2.pdf

SPECIAL EVENT THIS WEEK!

UVM UNIVERSITY SCHOLAR LECTURE

Our own Jeff Dinitz has been named a UVM University Scholar for 2008-2009 in recognition of his “sustained excellence in research and scholarly activities” in the field of combinatorics.  (Congratulations Jeff!)  As part of this award, he will be presenting a special University Scholar Lecture, which we encourage all to attend in lieu of the usual combo seminar this week.  The University Scholar Lectures, open to the general public, present an accessible glimpse into the scholar’s work, so this will be an excellent opportunity to see a great overview of Jeff Dinitz’ specialty in design theory.

Combinatorics Seminar Special Event

Date: Wednesday, April 15, 2009

Time:  4:00-5:00 pm

Location:  Memorial Lounge, Waterman Building, UVM Campus (note change of venue and time)

Title: Thinking Deeply about Putting Numbers in Boxes

Speaker:  Jeff Dinitz, UVM

For more information, see:  http://www.uvm.edu/~uvmpr/?Page=News&storyID=14066

Date: Thursday,  May 14, 2009

Time:  2:00-3:00 pm

Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus

Speaker:  Iain Moffatt, University of Southern Alabama

Title: Partial and natural duality

Abstract: Partial duality is is a far reaching generalization of the natural dual (or Euler-Poincare dual) of a graph. Roughly speaking, a partial dual of a ribbon graph is constructed by forming the natural dual only at a subset of edges of the ribbon graph. In this talk, after giving a definition of partial duality and describing a few of its basic properties, I will explain how partially dual ribbon graphs can be viewed  as a decoration of a graph and its natural dual. The advantage of this point of view of partial duality is that it provides a way to extend know results about naturally dual graphs to results about partially dual graphs. As an illustration of this, I explain how Edmonds'  well known characterization of natural duals can be extended to give a characterization of partial duals.

Date: Wednesday, June 17, 2009

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

Location:  Halstead Lab (Basement of Jeanmarie Hall), SMC Campus

Title: A Mobius Drawing of the Petersen Graph

Speaker:  Thomas Zaslavsky, Binghamton University (SUNY)

Abstract:

Only a comparatively few graphs can be drawn in the plane so that no two edges cross.  When a graph does have such a plane drawing, it divides the plane into regions, whose boundaries are made up of edges of the graph.

There are several ways to prove a graph cannot be drawn in the plane: it may have too many edges, it may have a bad subgraph, it may look evil (sorry, forget that, it's not math).  If it can't be drawn in the plane, though, it might still be drawn in some other surface, with the aid of some handles attached to the plane (yes, handles, which can act like bridges for edges to cross over without touching).

Some of these handles might be twisted.  Passing through a twisted handle reverses orientation.  In fact, there are twisted half-handles, called crosscaps, which have the same reversing effect.  Explained naively, if I walk through a twisted handle or a crosscap, my left and right get switched, so my heart is on the right and my liver on the left.  I say my "orientation" has been reversed.  Having my heart in the wrong place does not mean I am evil.

Now I want to draw a graph in a surface so that, if I go along a closed path of odd length, my orientation is reversed.  I call this "parity embedding".  Specifically, I want to draw the famous Petersen graph this way.  (If you don't know that the Petersen graph is famous, that will not impede your understanding of the talk.)

Again, a graph may not be drawable without adding some crosscaps or handles.  It may have too many edges, or bad subgraphs.  I will show that the Petersen graph requires exactly 4 crosscaps in order to be drawn without crossing edges, by the unusual method of analyzing incompatibilities amongst potential face boundaries.

The Petersen graph's potential boundaries, called circles, have an intricate combinatorial structure that leads to proofs of several theorems, of which the parity embedding theorem is only one.

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.