Overview Schedule and Abstracts Participating Directions and Parking UVM    SMC    IBM
 SMC Math Dept. SMC Home Jo Ellis-Monaghan Home UVM Math Dept. UVM CS Dept. UVM Home Dan Archdeacon Home

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).

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.

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.

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-2-09 Dan Archdeacon Three Petes Don't Complete 9-9-09 Greg Warrington A combinatorial variant of Sylvester's four-point problem 9-23-09 Alan Ling Constructions for Hash families 9-30-09 Jeff Dinitz Some new and old results regarding Room squares and related designs 10-7-09 Sam Northshield A short proof of Lagrange's theorem on continued fractions 10-14-09 President's Distinguished Lecture Peter D. Lax, "John von Neumann: The Most Powerful Mind of the 20th Century" 10-21-09 Greta Pangborn Selecting a Set of Influential Nodes 10-28-09 Kirsten Stor Superthrackles on other surfaces 11-4-09 Melanie Brown Fitting a Square Peg into a Triangular Hole: Embeddings of Complete Graphs with Regular Bipartite Duals 11-18-09 Greg Warrington Kazhdan-Lusztig polynomials of maximum possible degree 2-3-10, 2-10-10, 2-17-10 Jo Ellis-Monaghan Twisted duality and the ribbon group of an embedded graph: a leisurely exploration in three parts. 3-3-10 John Schmitt Minimum Saturated Graphs and Ramsey Graphs 3-24-10 Vincent Vatter Growth Rates of Permutation Classes 4-7-10 Doug Stinson Putting dots in triangles

Combinatorics Seminar

Dates: Wednesday, April 7, 2010.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title: Putting Dots in Trianlges.

Speaker: Douglas R. Stinson, David R. Cheriton School of Computer Science

University of Waterloo

Abstract:  Abstract-Stinson.pdf

Date: Wednesday, March 24, 2010.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title: Growth Rates of Permutation Classes

Speaker: Vincent Vatter, Dartmouth College

Abstract:

A permutation class is a set of permutations closed under the natural notion of subpermutation. The resolution, early this century, by Marcus and Tardos of the Stanley-Wilf conjecture has focused attention on the exponential growth rates of these classes. I will discuss the problem of characterizing the growth rates which can occur.

Date: Wednesday, March 3, 2010.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title: Minimum Saturated Graphs and Ramsey Graphs

Speaker: John Schmitt, Middlebury College

Abstract:

Given a family of graphs ${\cal F}$, a graph $G$ is ${\cal F}$-saturated if no member of ${\cal F}$ is a subgraph of $G$ but the addition of any new edge to $G$ creates a copy of some member of ${\cal F}$.  Let $sat(n, {\cal F})$ denote the minimum number of edges in an ${\cal F}$-saturated graph of order $n$.  We say that a graph $H$ arrows a $t$-tuple $(H_1, \ldots ,H_t)$ if any $t$-coloring of the edges of $H$ contains a monochromatic $H_i$-subgraph in color $i$ for some $i\in[t]$.  We consider saturated graphs with respect to the family of graphs that arrow $(K_3,K_3)$ (and separately $(K_3, P_3)$) and precisely determine the value of the $sat$-function for this family.  In doing the latter, we confirm the smallest non-trivial case of a conjecture of Hanson and Toft.

This is joint work with Guantao Chen, Mike Ferrara, Ron Gould, and Colton Magnant.

Dates: Wednesdays, February 3, 10, 17, 2010.

Time:  4:00-4:50  pm

Location: Jeanmarie 380, Saint Michael's College Campus

Title: Twisted duality and the ribbon group of an embedded graph: a leisurely exploration in three parts.

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

Abstract:

Part I.  Representations of ribbon graphs and twisted duality.  (2/3/10)

Part II.  The ribbon graph group, with orbits and classifications. (2/10/10)

Part III.  Those pesky polynomials. (2/17/10)

We consider two operations on the edge of an embedded (ribbon) graph: giving a half-twist to the edge and taking the partial dual with respect to the edge.   These two operations give rise to an action of ${S_3}^{e(G)}$, the ribbon group of G,  on $G$.  We show that this ribbon group action gives a complete characterization of duality in that if $G$ is any cellularly embedded graph with medial graph G_m, then the orbit of G under the group action is precisely the set of all graphs with medial graphs isomorphic (as abstract graphs) to G_m. We then show how this group action leads to a deeper understanding of the properties of, and relationships between, various graph polynomials such as the generalized transition polynomial, an extension of the Penrose polynomial to embedded graphs, and the topological Tutte polynomials of Las Vergnas and also Bollob\'as and Riordan, as well as various knot and link invariants.

This is joint work with Iain Moffatt.

Date: Wednesday, November 18, 2009

Time:  4:00-5:00 pm

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

Title: Kazhdan-Lusztig polynomials of maximum possible degree

Speaker: Greg Warrington, UVM

Abstract: Kazhdan-Lusztig polynomials, which are indexed by pairs of permutations, have several important interpretations in algebra and geometry. Fortunately, they satisfy a simple recursive formula. Unfortunately, our combinatorial understanding of the coefficients of these polynomials is still very weak. In this talk I'll describe what we do know and what we are still trying to figure out.

Date: Wednesday, November 4, 2009

Time:  4:00-5:00 pm

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

Title: Fitting a Square Peg into a Triangular Hole: Embeddings of Complete Graphs with Regular Bipartite Duals

Speaker: Melanie Brown, UVM

Abstract:  The graph K_n triangulates some orientable surface if and only if n = 0, 3, 4, 7 (mod 12). These triangulations are particularly interesting when the embeddings is face 2-colorable. In such an embedding, we can consider the three vertices of each triangular face as a triple, and these triples form a Steiner triple system on each of the two color classes. We seek to expand these results to find face 2-colorable embeddings of K_n for admissible n in which one color class consists of all triangles and the other color class consists of all quadrilaterals.

These embeddings would simultaneously give a Steiner triple system and a 4-cycle system. I will present an example of such an embedding and some related embeddings in addition to discussing some techniques that can be used to derive these embeddings.

Date: Wednesday, October 21, 2009

Time:  4:00-5:00 pm

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

Title: Some new and old results regarding Room squares and related designs

Speaker: Greta Pangborn, CS department, Saint Michael's College

Abstract:  This talk will focus on results of Kempe, Tardos, and Kleinberg on maximizing the spread of influence in social network. Given a relationship graph and information about how nodes influence one another, we will look at selecting a set of k nodes that will cause the maximum cascade of influence in the network. In particular, we will look at approximation algorithms for the linear threshold and independent cascade influence models. (Time permitting we will mention a few of the other possible models.)

Date: Wednesday, October 7, 2009

Time:  4:00-5:00 pm

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

Title: A short proof of Lagrange's theorem on continued fractions

Speaker: Sam Northshield, Mathematics Department, SUNY Plattsburg

Abstract:  Lagrange was the first to prove that every irrational root of a quadratic polynomial with integer coefficients has an eventually repeating continued fraction expansion (e.g., the square root of 3 equals 1+1/(1+1/(2+1/(1 +1/(2+1/(1+1/(2+1/(1+ … ))) ). I'll present a short, elementary, and possibly new proof of this result. This proof readily generalizes.

Date: Wednesday, September 30, 2009

Time:  4:00-5:00 pm

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

Title: Some new and old results regarding Room squares and related designs

Speaker: Jeff Dinitz, Mathematics Department, UVM

Abstract:  In 1972 Wallis wrote the book on Room squares. Since that time there has been much work in the area of Room squares and related designs, but some problems are still unsolved. In this talk I will discuss some of these problems, in particular I will look at certain classes of Room squares, frames and 3-dimensional Howell designs. The talk will end with a piece of music which is based on a large set of Room squares.

Date: Wednesday, September 23, 2009

Time:  4:00-5:00 pm

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

Title: Constructions for Hash families

Speaker: Alan Ling, CS Department, 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.

Bio: Prof. Ling is an Associate Professor at the Department of Computer Science in the University of Vermont. He has published papers in various journals, including, IEEE Trans. on Inform. Theory, IEEE Trans. on Computer, Bioinformatics, SIAM J. on Discrete Math., and Journal of Combinatorial Designs.

Date: Wednesday, September 9, 2009

Time:  4:00-5:00 pm

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

Title: A combinatorial variant of Sylvester's four-point problem

Speaker: Greg Warrington

Abstract: Sylvester's Four-Point Problem asks for the probability that four points chosen at random from a region R have a quadrilateral as their convex hull. If R is convex, the answer has bee shown to range between 2/3 and 0.704, depending on the particular region R. We present a combinatorial version of this problem involving permutations for which the answer appears to be exactly 3/4.

Date: Wednesday, September 2, 2009

Time:  4:00-5:00 pm

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

Title: Three Petes Don't Complete

Speaker: Dan Archdeacon, Mathematics Department, UVM

Abstract:  Can the complete graph on 10 vertices be written as the edge-disjoint union of three copies of the Petersen graph? The simple necessary conditions work out, but that's not sufficient. Come see some cool proofs it ain't so.

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.