Combinatorics Seminars Academic year 2007-2008 |
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 2007-Spring 2008.
(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.
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 |
10/10/07 | Peter Winkler | Adventures at the Interface of Combinatorics and Statistical Physics |
11/1/07 | Bill Martin | Cometric Association Schemes |
11/16/07 | Sam Northshield | 1121323143525341… etc. |
1/25/08 | Caroline (Carly) Klivans | A Simplical Matrix Tree Theorem |
4/28/08 | Sylwia Cichacz | Decomposition of bipartite graphs into (0,j)-prisms |
8/25/08 | Summer Combo in Vermont Miniconference | 11 speakers from the region on a variety of topics. Schedule and abstracts. |
(The spring Combo seminar was largely replaced by UVM interview talks not advertised here--contact Dan Archdeacon for abstracts)
[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]
Date: Wednesday, October 10, 2007
Time: 3:00-4:00 pm
Location: 102 Saint Edmunds, SMC Campus
Title: Adventures at the Interface of Combinatorics and Statistical Physics
Speaker: Peter Winkler, Dartmouth College
Lately there has been a startling burst of activity resulting from the discovery by statistical physicists and combinatorialists that they have many objectives in common, and can benefit from each other's techniques. We'll concentrate on three particularly combinatorial models: the hard-core gas model, percolation, and branched polymers.
Date: Thursday, November 1, 2007
Time: 3:30-4:30 pm
Location: 102 Saint Edmunds, SMC Campus
Title: Cometric Association Schemes
Speaker: William J. Martin, Worcester Polytechnic Institute
Abstract:
Association schemes are combinatorial structures which can be viewed as abstractions of transitive group actions on finite sets.
A symmetric association scheme consists of a base set $X$ together with a set $\A = {A_0, . . . , A_d }$ of 01-matrices with rows and columns indexed by $X$ satisfying conditions (i)-(iv) below:
(i) $A_0 = I$;
(ii) $A_0 + A_1 + \cdots + A_d = J$, the matrix of all ones;
(iii) $A_i^T = A_i$ (i.e., each $A_i$ is a symmetric matrix);
(iv) there exist integers $p_{ij}^k$ ($0\le i,j,k \le d$) such that
$A_i A_j = \sum_k p_{ij}^k A_k$.
(One may equivalently specify a collection of binary relations $R_i$ on $X$ or graphs $(X,R_i)$.)
Much emphasis has been placed on ``$P$-polynomial'' (or ``metric'') association schemes, which are essentially equivalent to distance-regular graphs. In 1973, Delsarte defined ``$Q$-polynomial'' (or ``cometric'') association schemes.
While this class includes many important structures, such as the so-called ``classical schemes'' and schemes arising from optimal combinatorial designs and spherical designs, very little was known about their structure until about 10 years ago.
The goal of this talk is to introduce this family of association schemes, draw connections to other parts of mathematics, discuss what is known about them, and to list the most important open problems in the area. I will not assume more than a knowledge of introductory graduate algebra and an interest in combinatorial structures.
NOTE: This talk is partially based on joint work with Jason Williford, University of Colorado at Denver
Date: Friday, November 16, 2007
Time: 2:30-3:30 pm
Location: Jean Marie 380, SMC Campus
Title: 1121323143525341… etc.
Speaker: Sam Northshield, SUNY Plattsburgh
Abstract:
We will look at Stern’s Diatomic Sequence 11213231435… and some of its many fascinating properties. Along the way, we shall touch upon Pascal’s triangle and other geometric arrays, Fibonacci numbers, an enumeration of the rational numbers, the Euclidean algorithm, and continued fractions. Time permitting; we will discuss the ‘Fibonacci Diatomic Sequence’ (1112122132231…) and some of its many interesting properties.
This talk will be accessible to students. Be sure to bring a pencil.
Date: Friday, January 25, 2008
Time: 3:30-4:30 pm
Location: 102 Perkins, UVM Campus
Title: A Simplicial Matrix Tree Theorem
Speaker: Caroline Klivans, University of Chicago
Abstract:
We generalize the deﬁnition and enumeration of spanning trees from the setting
of graphs to that of arbitrary-dimensional simplicial complexes K. We prove a
simplicial version of the classical Matrix-Tree Theorem that counts simplicial
spanning trees, weighted by the squares of the orders of their top-dimensional
integral homology groups, in terms of the combinatorial Laplacian of K. As in
the graphic case, one can obtain a more ﬁnely weighted generating function for
simplicial spanning trees by assigning an indeterminate to each vertex of K and
replacing the entries of the Laplacian with Laurent monomials. In particular we
investigate the case when K is a shifted complex and give a combinatorial
interpretation of the eigenvalues of its weighted Laplacian, generalizing known
results about this class of Laplacian integral complexes.
Date: Monday, April 28, 2008
Time: 3:00-3:50 pm
Location: Mathematics Department Conference Room, UVM campus.
Title: Decomposition of bipartite graphs into (0,j)-prisms
Speaker: Dr. Sylwia Cichacz,Visiting Fulbright Scholar, University of Minnesota, Duluth
Abstract:
R. Haggkvist proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K_{6n,6n}. We establish a necessary and sufficient condition for the existence of factorization of the complete bipartite graph K_{n,n} into some families of 3-regular graphs of order 2n. We will also show that some families of 3-regular graphs of order 2n decompose the complete bipartite graph K_{(3n/2),(3n/2)}.
Directions to SMC: From major cities, see SMC
Directions
Once on Interstate 89 see below:
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).
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.