Combinatorics Seminars Academic year 2004-2005 |
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 2004-Spring 2005.
(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 joellis@emba.uvm.edu
or archdeac@emba.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-1-04 | Mike Dinitz |
Full
Rank Tilings of Finite Abelian Groups |
9-28-04 | Dan Archdeacon |
Graphs
on grids: area/volu |
10-13-04 | Dan McQuillan | Recent Results in Vertex Magic Total Labelings of Graphs. |
10-18-04 |
Ron Graham (Two Talks) |
2:30--Archimedes, Combinatorics and the
Stomachion 4:00--Searching for the Shortest Network |
Mary Cox | The Continued Fraction in Combinatorial Game Theory | |
11-8-04 | Exploring Grand Challenges in Trustworthy Computing | |
2-17-05 | David Wood | Fast Separation in Graphs with an Excluded Minor |
2-18-05 | David Wood | Drawing of Graphs in Two and Three Dimensions (UVM Colloquium talk) |
4-7-05 | John Schmidt | A Problem in Extremal Graph Theory |
5-5-05 | Alice Dean | Characterizations of Unit-Bar Visibility Graphs |
7-20-05 | Tom Zaslavsky | Inside-Out Polytopes and the Geometry of Graph Coloring |
[Fall 2001 Abstracts] [Spring 2001 Abstracts] [Spring 2002 Abstracts] [Fall 2003 - Spring 2004 Abstracts]
Date:
Ti
Location:
Mathematics Depart
Title:
Full
Rank Tilings of Finite Abelian Groups
Speaker:
Mike
Dinitz,
Abstract:
A
tiling of a finite abelian group G is a pair (V,A) of subsets of G such that 0
is in both V and A and every g \in G can be uniquely written as g=v+a with v \in
V and a \in A. Tilings are a special case of nor
Date:
Ti
Location:
Farrell Room,
Title:
Graphs
on grids: area/volu
Speaker:
Abstract:
Flat tori:
geometric realizations of toroidal triangulations (PowerPoint, 7MB)
Date:
Ti
Location: Math Conference Room, Lord House, 16 Colchester Ave., UVM Campus.
Title:
Recent
Results in Vertex Magic Total Labelings of Graphs. (based on work with students:
Katy Smith, Aaron Thurston and Karthik
Raman,
all of
Speaker:
Dan
McQuillan,
Abstract:
A
Total Labeling is an assign
1,2,3,...
to the vertices and edges of a graph. It is called magic if
the
"weight" at each vertex is the sa
magic
constant of the labeling. For most regular graphs, there are many
vertex
magic total labelings (VMTL's). Furthermore, there are usually
many
different possible magic constants. We describe the classification
of
the set of all possible magic constants for the odd complete graphs,
among
others.
Date:
Ti
Location: UVM campus--see below for building/room
Speaker:
Ronald L. Graham.
As part of the President's Distinguished Lecture Series the Department of Mathematics and Statistics is pleased to host Ronald Graham.
He will be speaking at
4:00pm Monday October 18th in Angell B106 on the UVM campus.
A reception will follow in Billing's Apse.
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/
Title: Searching for the shortest network
Abstract: There are many situations in which one would like to connect a collection of points together by a network having the minimum possible total length. Such problems occur in the design of telephone networks, railroad lines, oil and gas pipeline networks, heating and air-conditioning duct systems, the layout of VLSI chips, and the inference of evolutionary pathways for living organisms, for example. In this talk we give a summary of what is known (and unknown) about this classical problem, and how current developments in computer science have impacted it.
If you only go to one math talk this year, this should be it!
There is also a second, earlier, talk:
Archimedes, Combinatorics and the
Stomachion
Professor Ron Graham
University of California at San Diego
Monday, October 18, 2004
2:30-3:20 PM
Room L200 Lafayette
Reception to follow in Billings Apse at 5:00pm
Abstract:
Greek mathematics has long been known for its fundamental
contributions to geometry and diophantine equations, for example
However, there is now evidence that ancient Greek mathematicians were
also interested in various combinatorial problems. In this talk, I
will describe some recent work exploring this theme which arose from
the analysis of a puzzle called the Stomachion, which was recently
discovered in a long lost manuscript of Archimedes.
Date: Tuesday, October 26, 2004
Time: 3:30 – 4:30 pm
Location: Jeanmarie 391, SMC Campus.
Title: The Continued Fraction in Combinatorial Game Theory
Speaker: Mary Cox, UVM.
Abstract:
The origin of continued fractions is traditionally placed at the time of the creation of Euclid's Algorithm; in fact, continued fractions are intimately related to Euclid's Algorithm. In the 19th Century, there was an explosion of growth within this subject, with contributions by Jacobi, Perron, Hermite, Gauss, Cauchy, and Stieljes. Since the beginning of the 20th Century continued fractions have made their appearance in other fields, including chaos theory, within computer algorithms for computing rational approximations to real numbers, solving indeterminate equations, and knot theory. Very recently, continued fractions have also been used in the relatively young field of combinatorial game theory.
In this talk, we define the general and simple continued fraction, and give a short demonstration of a traditional number theoretic use -- solving Pell's equation. We then outline the basics of combinatorial game theory, and then demonstrate the use of continued fractions in this area of mathematics by demonstrating the evaluation of a game of Contorted Fractions.
This talk is accessible to a general audience.
Combinatorial Game Theory, The Continued Fraction: Two Little-Known Uses
Date:
Ti
Location: McCarthy Auditorium, SMC Campus.
This is a Special Event Sponsored by the SMC Computer Science Department in honor of St. Michael's College Centennial Celebration.
Title: Exploring Grand Challenges in Trustworthy Computing
Speaker: Dr. Eugene H. Spafford, Purdue University
Abstract:
We are presented with numerous challenges to make our information systems more secure, increase our confidence in our stored data, and protect the privacy of our personal information. However, under the steady barrage of attacks and flaws, it is sometimes difficult to think in terms of "big" challenges that can inspire us to make revolutionary, rather than evolutionary, strides.
In this presentation I will discuss a few of the trends and problems that have been occupying researchers and industry over the last few years. I will explain why advances against these challenges are unlikely to provide long-term improvements in the security of our infrastructure. From this, I will then discuss the results of the recent CRA Grand Challenges conference on information security, including some discussion of how we might proceed to make progress on each of these four grand challenges.
Dr. Eugene H. Spafford is a professor of Computer Sciences at Purdue University, where he also holds courtesy positions in the following departments: Philosophy, Communication, Electrical and Computer Engineering. He is the Executive Director of CERIAS – the Center for Education and Research in Information Assurance and Security – which is a campus-wide multi-disciplinary Center, with a broadly-focused mission to explore issues related to protecting information and information resources.
Dr. Spafford has written extensively about information security, cybercrime, software engineering, and professional ethics, and is a Fellow of the ACM, AAAS, and IEEE. He is also a member of the President’s Information Technology Advisory Council.
Date: 2/17/05
Time: 4:00 – 5:00 p.m.
Location: Farrell Room (St. Edmunds, Room 315), St. Michael’s College
Title: Fast Separation in Graphs with an Excluded Minor
Speaker: David Wood, McGill University, Montreal
Abstract: A separator in a graph is a set of vertices whose removal splits the graph into two roughly equal sized pieces. In 1977, Lipton and Tarjan proved that every planar graph on n vertices has a separator of O(\sqrt{n}) vertices.
This result has found applications in numerous areas including approximation algorithms for NP-hard problems, solving sparse systems of linear equations, pebbling games, and graph drawing. In 1990, Alon, Seymour and Thomas generalised the Lipton-Tarjan result by proving that every graph with a fixed excluded minor (eg planar graphs have no K_5 and no K_{3,3} minor) has a separator of O(\sqrt{n}) vertices. Unfortunately, the running time of the resulting algorithm was O(n^{3/2}), compared to O(n) in the planar case. We present a preprocessing step to the Alon-Seymour-Thomas algorithm which leads to a O(n) time algorithm, at the expense of a slightly larger separator. This is joint work with Bruce Reed.
See David Wood's Website at
http://www.cs.mcgill.ca/~wood/
Talk overheads: DavidWood-Separators.pdf
Date: 2/18/05
Time: 4:00 – 5:00 p.m.
Location: 004 Kalkin, UVM Campus
Title: Drawing of Graphs in Two and Three Dimensions
Speaker: David Wood, McGill University, Montreal
Abstract: Graph theory has its origins in drawings of planar graphs. Recently there has been renewed interest in graph drawings due to interesting results and numerous applications in diverse areas including software engineering, information visualisation, and VLSI circuit design. In this talk I will introduce the discipline of graph drawing, and survey a few of the main results. The focus will be on drawings of graphs in three dimensions, in which the vertices are positioned at integer grid-points, and the edges are non-crossing straight line-segments. While it is folklore that every graph has such a representation, I shall consider three-dimensional drawings with small bounding box volume. A survey of this problem will be presented, along with lower and upper bounds on the minimum volume for various classes of graphs.
See David Wood's Website at
http://www.cs.mcgill.ca/~wood/
Talk overheads: DavidWood-GraphDrawing.pdf
Date: Thursday, 4/7/05
Time: 3:30 – 4:30 p.m.
Location: SMC Campus, Jeanmarie 362
Title: A Problem in Extremal Graph Theory
Speaker: John Schmidt, Department of Mathematics, Emory University
Abstract:
Graphs have proven to be a very important mathematical model. For example, computer or telephone networks can be viewed as graphs. Often, one would like to build a graph that has a certain property. A natural question then arises:
"How much does one have to spend to build the graph with the desired property?"
We will discuss such a question as asked by Paul Erdos and its solution.
No previous knowledge of graph theory is assumed.
Combo_Seminar/overheads/JohnSchmitttalk.pdf
Date: Thursday, 05/05/05
Time: 3:30 – 4:30 p.m.
Location: SMC Campus, Jeanmarie 362
Title: Characterizations of Unit-Bar Visibility Graphs
Speaker: Alice Dean, Department of Mathematics and Computer Science, Skidmore College
Abstract:
Representations of graphs using horizontal bars for vertices and vertical visibilities for edges have been studied since the mid 1980s, motivated by applications to circuit design and display of data. Graphs that can be represented in this way have been fully characterized, but the bar lengths may differ by impractical amounts. I consider graphs that can be represented using bars all of equal length. These graphs, called unit-bar visibility graphs (or UBVGs), have not been fully characterized. I will discuss results for several classes of graphs, including trees and outerplanar graphs. The final result is a characterization of the triangulated polygons (TPs) that are UBVGs. The characterization uses a character string associated with each TP to determine if a UBV layout exists and if so, to produce such a layout.
This is joint work with E. Gethner and J. Hutchinson and, separately, with N. Veytsel.
Combo_Seminar/overheads/AliceDeanUBVGs.pdf
Date: Wedneday, 07/20/05
Time: 10:00 – 11:00 a.m.
Location: Mathematics Department Conference Room, Lord House, 16 Colchester Ave., UVM campus.
Title: Inside-Out Polytopes and the Geometry of Graph Coloring
Speaker: Tom Zaslavsky, Department of Mathematics, SUNY Binghamton
Abstract:
A rational inside-out polytope consists of a convex polytope P with rational vertices in Eucldean space together with a finite set of rational hyperplanes. The number of 1/t-integral points in the interior of P but not in any of the hyperplanes is a function of t = 1,2,3,... that is given by a quasipolynomial (a cyclically repeating sequence of polynomials).
We -- that is, Matthias Beck and I -- deduce this from Ehrhart's theory of rational polytopes (without hyperplanes).
The theory explains why a graph has one chromatic polynomial but a signed graph has two. It shows that the number of magic squares of fixed size is a quasipolynomial function of the magic sum; the number of antimagic labellings of a fixed graph by integers from 1 to t is a quasipolynomial function of t; and more....
Date: TBA
Time : TBA
Location: math department conference room, Lord house, 16 Colchester Ave
Title: Isotropic systems, DNA sequencing and the interlace polynomial
Speaker: Jo Ellis-Monaghan, department of mathematics, Saint Michael’s College
Abstract:
The interlace polynomial of a graph, described in [R. Arratia, B. Bollob \'as, G. Sorkin, The Interlace Polynomial: a New Graph Polynomial, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, Jan. 2000, 237-245.] as evolving from problems in DNA sequencing, evokes many open questions. By exploiting the machinery of Tutte-Martin polynomials of isotropic systems and a recent paper of Bouchet [A. Bouchet,Graph Polynomials Derived from Tutte-Martin Polynomials, in press] that realizes the interlace polynomial of a graph as a special case of a Tutte-Martin polynomial of an isotropic system, we are able to resolve several open questions presented by Arratia, Bollob\'as and Sorkin. These include the relation between the interlace polynomial and the Tutte polynomial, the computational complexity of the interlace polynomial, and perhaps most importantly, an interpretation of exactly what the interlace polynomial of a graph counts. We conclude by presenting a class of graphs on which the interlace polynomial is polynomial time to compute and which is characterized by an invariant $\gamma$ analogously to the way series parallel graphs are characterized by the $\beta$ invariant.
This talk should be accessible to students who we have some background in elementary graph theory and linear algebra.
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://scripts.uvm.edu/www/map.php3.
Click on the map to zoom in, or use the "locate" button at the bottom to find specific buildings or
parking lots (the Math Department is 16 Colchester, the visitor lot is across College street from Waterman building).
A map of the whole campus with visitor parking colored green is at http://www.uvm.edu/~tpswww/images/oncampus.jpg,
but you need a LARGE monitor to read the labels.
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.