Combinatorics Seminars Academic year 2005-2006 |
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 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 ).
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.
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/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.
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 vertexnullity 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 vertexnullity interlace polynomial. Here, using the medial graph of a planar graph, we relate the one variable vertexnullity interlace polynomial to the classical Tutte polynomial when x = y, and conclude that, like the Tutte polynomial, it is in general #Phard 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 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.